- 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
- Compute time complexity of a given TM
- 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)
- 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
- 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)
- 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
# 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
- http://www.dummies.com/how-to/content/how-to-calculate-a-regression-line.html
- https://www.youtube.com/watch?v=w2FKXOa0HGA
- 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.
