Show HN: Turing machine simulator in C

Automata and Computability (Kozen)

The important point is that a TM is capable to calculate everything that is considered to be decidable. It is _the_ computation machine in theoretical CS and different models (eg lambda calculus) are equivalent in computational power. Implementations are a proof-of-concept to show/visualize their power and can be seen as compilers for basic languages.

Their exact mathematical description differs from source to source but the interesting thing is that just a small program (the TM) is capable of calculating everything (efficiency is not the question here).

Depending on your background you may prefer to start with primitive recursive function (and then partial recursive function) or finite-state machine. Some books on computability/decidability theory start with those and introduce Turing machines only after.

Kozen's book that has been mentioned is very good. I also recommend Sipser's "Introduction to the Theory of Computation".

It goes from Deterministic Finite Automata (equivalent in power to regular expressions in their purest sense, as opposed to POSIX regexps) to Context-Free Grammars and then finally Turing Machines. So this will give an idea of the hierarchy that TMs sit in.

Also, there are plenty of variations of Turing Machines with lots of cool properties. If you want to have a look, try searching for "Non-Deterministic Turing Machines", "Probabilistic Turing Machines", or "Alternating Turing Machines".

You can think of it as a theoretical machine introduced by Alan Turing which can compute anything that can be computed. If something cannot be computed by Turing machine, then it means that it cannot be computed at all. An important aspect is that it is defined as a simple machine with infinte length tape and a moving head, which can move in any direction. Tape is made up of cells where inputs/outputs are stored. There is also another related proof that says problems are uncountable and programs are countable which means there exist some problems which cannot be solved at all. I would recommend the book Introduction to Automata Theory, Languages, and Computation by Ullman et al. It explains from very simple machine called finite automata to Turing machine. For a beginners introduction Wikipedia entry is still good

You can simply call the program with that file name as a commandline argument.

I don't know :) I did this 2 years back while I was in my college. Just thought about posting it in HN today. Why it is considered of interest, it is entirely up to the community.