FT_TURING, Jan 2016

Deterministic Turing machine in Ocaml. (group project)

Grade (125/100) (125/125)*

Team: fbuoro / ngoguey.

Goals:

• Create a deterministic, single headed and single tape Turing machine(TM).
• Read a TM description from a json file.
• Code in OCaml or Haskell, any version, library or tools authorized.
• Write 5 turing machines in json form (see below)
• Write an universal turing machine(TM5) able to run TM1

Recommended bonus:

• Compute time complexity of a given TM

Our work:

• Deep study of theory of computation (see Useful links below)
  
  
• Study of core/batteries-included libraries (used core/list, core/dequeue, core/array)
• Small functional wrapper (YojsonTreeMatcher.ml) for yojson, that unfolds two recursive variants side by side with callbacks.
• Loop detection (LoopGuard.ml) when TM act as a LBA.
• option (-c) to convert a json-turing-machine and its input to TM5's input format
• Use of log-log plotting (Complexity_classes.ml), linear regression (Order.ml) and gnuplot to compute time complexity of TMs. See Below.
  
  
• Conception of a pseudo-asm language to describe TMs, compilable to .json format (compiler)
• Advanced TM5 (utm.s) able to run any other TM (including itself)
• TM3 (0n1n.s) running in O(Nlog(N)) and preserving input
• more TM (see below)

Mandatory Turing Machines in ./machines:

• TM0: machines/unary_sub.json given in subject.pdf as an example
• TM1: machines/unary_add.s
• TM2: machines/palindrome.json
• TM3: machines/0n1n.s
• TM4: machines/zero_power_2n.json
• TM5: machines/utm.s universal turing machine

Turing Machines in ./machines optimized for complexity calculation:

• machines/abs.s O(1)
• machines/unary_add_unsec.s O(n)
• machines/0n1n_unsec.s O(nlogn)
• machines/unary_sub_unsec.s O(n^2)
• machines/is_palindrome2_unsec.s O(n^2)
• machines/split_input_unsec.s O(n^2)
• machines/binary_increment_unsec.s O(2^n)

More Turing Machines in ./machines:

• machines/has_0011.s
• machines/minsky_utm.s 1967 Minsky's universal turing machine
• machines/split_input.s separate input with blanks in O(3n^2)
• machines/is_palindrome2.s version 2
• machines/binary_divisable_by3.s
• machines/zero_second_to_last.s

Use

# Install through brew: opam ocamlfind ocaml core.113.00.00 yojson gnuplot gnuplot-ocaml
make install_libs

# Project compilation
make

# Compile machines/*.s files to machines/*.json:
python compiler/main.py machines/*.s

# Run a json-turing-machine on a given input
./ft_turing machines/is_palindrome2.json "ABA"

# Translate a json-turing-machine and its input to a Universal-Turing-Machine input
./ft_turing -c machines/unary_sub.json "1111-1="

# Run the above input on the universal turing machine
 ./ft_turing machines/utm.json $(./ft_turing -c machines/unary_sub.json "1111-1=")

# Compute an html file through gnuplot reflecting the complexity of a given json-turing-machine
./ft_turing -O machines/0n1n_unsec.json

Useful links:

Small presentation:

• https://www.youtube.com/watch?v=7dpFeXV_hqs

18h of theory of computation (math oriented, accessible):

• https://www.youtube.com/user/hhp3/playlists

Linear regression:

• http://www.dummies.com/how-to/content/how-to-calculate-a-regression-line.html
• https://www.youtube.com/watch?v=w2FKXOa0HGA

Misc:

• http://www.wolframscience.com/nksonline/toc.html
• http://www.cba.mit.edu/events/03.11.ASE/docs/Minsky.pdf

*
- A grade of 85 was required to validate the project.
- A maximum grade of 125 was reachable.
- Second sessions are organised for failed projects.

unary add:

is input a palindrome:

is input of form 0^2n:

machines/utm.s encoding (universal turing machine):

0n1n_complexity:

unary_sub_complexity: