ft_turing – a Turing Machine simulator written in Haskell

• A student project implementing a single-headed, singly-infinite-tape Turing machine in Haskell
• The goal is to
  • parse a machine description (example)
  • validate it
  • run the machine and log all transitions
• For complete instructions please refer to docs

Usage

To use the machine you need to have installed Stack. You can then run

$ stack run <machine> <input>

where

• machine is a file describing the machine
• input is a string of symbols, representing initial tape contents.

Alternatively, you can pull the corresponding Docker image or build your own using the provided Dockerfile.

$ docker pull almayor/ft_turing:latest # or docker build -t ft_turing .
$ docker run almayor/ft_turing:latest <machine> <input>

Machines

A few machines capable of executing simple programs can be found in machines/:

00-unary_sub – performs unary subtraction.

01-unary_add – performs unary addition.

02-palindrome – checks if the input is a palindrome.

03-lang-0n1n – checks if the input is a word in the language

04-lang-02n – checks if the input is a word in the language

Acknowledgements

I'm grateful to the entire team behind School 21 for the opportunity to do these interesting projects. I also thank

• Denis Moskvin for a superb course on functional programming using Haskell
• Léonard Marques for putting a similar project in the public domain; it helped me clarify some important points.
• creators of AnsiToImg – a tool for converting ANSI terminal output to pretty images