Hacker News new | past | comments | ask | show | jobs | submit login

Closest thing I could find was involved in proving the finite version of Ramsey's Theorem from the infinite version as a compactness argument.


That being said, I'm a little curious as to why one would want to prove something is Turing complete. I tend to assume something is Turing complete unless shown otherwise. For instance, I would never have gambled MTG wasn't Turing complete.

At the very least, proving that a game is Turing complete can be as entertaining a challenge as playing it.

One case where Turing completeness was useful was in proving wrong those programmers who claimed that there were some programs that just could not be written using structured programming. Also, if we did not know about Turing completeness, there would be constant futile research trying to find alternative architectures and languages that could solve problems that cannot be solved with what we have.

I think it is probably more useful to prove that something isn't Turing complete, and explain why. Finding things that are Turing complete is the basically the same task through a complementary lens.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact