4 ms·

Show HN: Turing machine simulator in C

38 points by yedhukrishnan 11y ago

pflanze 11y 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 11y ago
  Automata and Computability (Kozen)
- helloagain57 11y 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).
- p4bl0 11y 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 11y 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 11y ago
    Second Sipser's "Introduction to the Theory of Computation"
- jestinjoy1 11y 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
p4bl0 11y 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).
- vegedor 11y ago
  sundays are slow is why. and it's got hacker's spirit
- yedhukrishnan 11y 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.
rgawdzik 11y ago
How do you use SampleMultiplication?
- yedhukrishnan 11y ago
  You can simply call the program with that file name as a commandline argument.
  - rgawdzik 11y ago
    Right, but what sort of operations can you perform? Can you give me an example of how you would do 2*2?
    - yedhukrishnan 11y ago
      Yeah! ./turingmachine SampleMultiplication 11011 You will get output 11110. If you want to multiply 3 & 2, give 111011. You will get 111111.
apverma 11y ago
dude I recently heard death of C. http://techcrunch.com/2015/05/02/and-c-plus-plus-too/ http://techcrunch.com/2015/05/02/and-c-plus-plus-too/

38 points by yedhukrishnan 11y 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 11y ago
Automata and Computability (Kozen)
helloagain57 11y 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).
p4bl0 11y 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 11y 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 11y ago
  Second Sipser's "Introduction to the Theory of Computation"
jestinjoy1 11y 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

p4bl0 11y 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).

vegedor 11y ago
sundays are slow is why. and it's got hacker's spirit
yedhukrishnan 11y 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.

rgawdzik 11y ago

How do you use SampleMultiplication?

yedhukrishnan 11y ago
You can simply call the program with that file name as a commandline argument.
- rgawdzik 11y ago
  Right, but what sort of operations can you perform? Can you give me an example of how you would do 2*2?
  - yedhukrishnan 11y ago
    Yeah! ./turingmachine SampleMultiplication 11011 You will get output 11110. If you want to multiply 3 & 2, give 111011. You will get 111111.

apverma 11y ago

dude I recently heard death of C. http://techcrunch.com/2015/05/02/and-c-plus-plus-too/ http://techcrunch.com/2015/05/02/and-c-plus-plus-too/