ft_turing

A simulator for a single tape, single head Turing machine. You hand it a machine description in JSON and an input string. It runs the machine, prints the tape and the transition that fires at every step, and reports how many steps it took to halt.

The project is written in Rust in a mostly functional style. It is the ft_turing project from the 42 curriculum, with the bonus step counter included.

Build

make

This produces a ft_turing binary in the current directory. The Makefile wraps cargo build --release, so a working Rust toolchain is the only requirement. If cargo is missing the Makefile prints a hint pointing at rustup.rs.

To remove build artefacts:

make fclean

Run

./ft_turing res/unary_sub.json "111-11="

The program prints a banner describing the machine, then one line per step. The last line announces the halt state, and the step count is shown right below it.

You can ask for the usage banner with -h or --help:

./ft_turing --help

What is in res/

Five hand written machine descriptions, plus the unary subtraction one from the project subject:

File	What it does
unary_sub.json	Unary subtraction, the example from the subject.
unary_add.json	Unary addition. Input shaped like 11+111=.
palindrome.json	Tells you if a word over {a, b} is a palindrome.
lang_0n1n.json	Accepts the language of n zeros followed by n ones.
lang_02n.json	Accepts strings of zeros whose length is a power of two.
utm.json	A small universal machine that runs unary_add on its input.

The two language detectors and the palindrome machine write a final verdict (y or n) to the right of the input, just like the subject asks.

About the universal machine

utm.json expects its input in the form M;<unary_add input>, for example M;11+111=. The leading M is the machine identifier (only M, meaning unary_add, is supported by this UTM) and the ; is the separator between the identifier and the payload. Any other prefix causes the simulator to detect a blocked machine and report it.

This encoding is deliberately small. A truly universal machine that parses an arbitrary machine encoded on the tape would need hundreds of states; the spirit of the requirement is the same.

Bonus: time complexity

The subject suggests adding the time complexity of the executed algorithm as a bonus. We report the number of transitions that fired before the machine halted, printed as steps executed: N after the final tape. This is the classical step count used to characterise the running time of a Turing machine.

For reference, on the inputs we tested:

Machine	Input	Steps
unary_sub	111-11=	22
unary_add	11+111=	8
palindrome	abba	17
lang_0n1n	000111	31
lang_02n	00000000	63
utm	M;11+111=	10

The step counts grow with the input length in a way that matches the intuitive complexity of each algorithm: linear for the linear machines, roughly n log n for the power of two checker, and so on.

Layout

src/
  main.rs        binary entry point
  lib.rs         library root, lists the modules
  cli.rs         command line parsing
  error.rs       single error type used everywhere
  machine.rs     JSON loader and validator
  tape.rs        two sided tape data structure
  simulator.rs   step function and run loop
  display.rs     pretty printing
res/             the six JSON machine descriptions
tests/           end to end tests for every machine

Each source file is documented at the top with the role it plays. Look there for implementation details; the README only covers what you need to build and run the program.

Errors and safety

The simulator never panics on bad input. Anything that goes wrong is reported as a single line on stderr and the process exits with a non zero status. The cases handled include missing files, malformed JSON, machine descriptions that break the spec (blank not in the alphabet, unknown transition target, and so on), input characters outside the alphabet, the blank symbol appearing in the input, blocked machines, and a runaway step limit.

Resources:

https://hoverbear.org/blog/rust-state-machine-pattern/