Show HN: Turing machine simulator in C

https://github.com/yedhukrishnan/turing-machine

by yedhukrishnan • 11 years ago

38 13 11 years ago

pflanze• 11 years ago

Any recommendation for literature on turing machines? The wikipedia article seems to be a bit clouded to me. I know turing machines and CPUs with infinite memory are similar in some ways, and that like lambda calculus they can (somewhat equivalently) be used as a basis to think about computation, but I don't know the details and not having a computer science background will probably be missing some context, but would love to get a proper introduction.

liadmat• 11 years ago

Automata and Computability (Kozen)

helloagain57• 11 years ago

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).

p4bl02• 11 years ago

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.

asQuirreL• 11 years ago

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".

geekam• 11 years ago

Second Sipser's "Introduction to the Theory of Computation"

jestinjoy1• 11 years ago

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

p4bl02• 11 years ago

I understand that it may have been fun to program, but I don't see why this is upvoted to the frontpage of HN.

It is just the "Turing machine" keyword? Or is there something that I missed? Because it seems like a very basic program, and not with a particularly interesting implementation (again my point is not to criticize the work, I am just wondering why is it considered of interest to HN).

yedhukrishnan3• 11 years ago

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.

rgawdzik2• 11 years ago

How do you use SampleMultiplication?

yedhukrishnan3• 11 years ago

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

rgawdzik2• 11 years ago

Right, but what sort of operations can you perform? Can you give me an example of how you would do 2*2?

Show HN: Turing machine simulator in C

Related Stories