Hacker News new | past | comments | ask | show | jobs | submit login
Addition on Turing Machines (2013) (jeapostrophe.github.io)
25 points by belter on July 10, 2021 | hide | past | favorite | 3 comments



Point #6 skims past what is (IMO) one of the most interesting results in Turing machine theory: adding additional tapes doesn't increase the computational power of the machine.

This is significant because machines at the next-lower level of complexity (pushdown automata) DO get more powerful: a PDA with two stacks is equivalent to a Turing machine!


Tangential: PDA aren’t really the “next-lower” model, just the one that we talk about most often; there’s a whole family of models that are stronger than a PDA but not Turing-complete (e.g. alternating pushdown automata).


One small past thread:

Addition on Turing Machines (2013) - https://news.ycombinator.com/item?id=9075475 - Feb 2015 (2 comments)




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

Search: