4 ms·
I take the strict view. Nothing in the list is Turing-complete because they don't have infinite tape it its equivalent. Since memory is finite they are all fi
by oldgradstudent 4y ago
I take the strict view.
Nothing in the list is Turing-complete because they don't have infinite tape it its equivalent.
Since memory is finite they are all finite state machines and therefore can only accept regular languages.
(Except Peano arithmetic and the like which are purely theoretical)
- linschn 4y agoThis is useless pedantry: by this metric absolutely nothing in the universe can be Turing Complete, and it's only a theoretical construct. Turing completeness is a useful tool for the analysis of actual, real life computers and their programs, despite their finitude.
- oldgradstudent 4y agoOf course. That was supposed to be a sarcastic response to pedantry in the thread. Turing completeness is a model, not reality. Choosing the right model is a judgment call.
- linschn 4y agoI am sorry, I completely missed the sarcasm. Textual communication is hard. Your imitation of hn pedantry was so good that I fell for it.