Hacker News Reader

We discussed the Turing completeness of C a while ago on HN ( https://news.ycombinator.com/item?id=4795542 ). Also the following was produced around that time:

https://tdotc.wordpress.com/2012/11/20/on-the-turing-complet...

View on HN

When you say "C" and "Turing machine" in the same sentence, you should immediately think of how you would go about explaining a proof of, say, the fact that a one tape TM can simulate a k tape TM using C. C is just one of many languages in which you can express the state transition diagram of a TM.

The point being you can't, due to the finiteness of c's abstract memory model, both for the heap (the tape) and stack (state transition graph)

No, any undergraduate CS major at a top 5 university should be able to do this. It's possible to do this for any programming language. If you need help then it's on p. 161 Theorem 7.2 of Hopcroft and Ullman (1979).

Reply on news.ycombinator.com