3 ms·

I would look at it a slightly different way. It's not that the definition of Turing completeness explicitly says that a language must be able to simulate "infin

I would look at it a slightly different way. It's not that the definition of Turing completeness explicitly says that a language must be able to simulate "infinite" algorithms. It's that it must be able simulate what a Turing machine can do. Turing machines are quite capable of running non-halting algorithms, so the language must be able to as well. Contrived example: One algorithm a Turing machine could perform would be to write the characters "TM" every two cells on its entire tape. The tape is unbounded, so this algorithm is, colloquially speaking, infinite. Clearly, you cannot simulate this with a halting machine like the C preprocessor.

ithinkso 13y ago
This is exactly the problem I was talking about. In every definition I've read there was strict condition that set of all possible states Q is non-empty (and finite). But there is difference in definition of set of final states. In [1] there is a comparison - in columns labeled "Peter Linz" and "Wikipedia" F is defined as subset of Q. This implies that it also could be empty, although in column labeled "Michael Sipser" there is a special state q_accept that explicitly exist in Q, therefore F is not-empty. Unfortunately there is no information if q_accept has to be reachable from start state. But consider this: How one could say that this machine is actually writing "TM" every two cells? If you investigate tape states while machine is still running it might change (on meta-level you my expect that this is actually true but you might for example make some bug that you're not aware of). The only way to be able to see that "TM" has been written is after the machine halts. [1] http://www.cis.upenn.edu/~matuszek/cit596-2012/NewPages/turing-machine-definitions.html http://www.cis.upenn.edu/~matuszek/cit596-2012/NewPages/turi...

3 ms·

I would look at it a slightly different way. It's not that the definition of Turing completeness explicitly says that a language must be able to simulate "infin

by throwaway82740 13y ago

ithinkso 13y ago
This is exactly the problem I was talking about. In every definition I've read there was strict condition that set of all possible states Q is non-empty (and finite). But there is difference in definition of set of final states. In [1] there is a comparison - in columns labeled "Peter Linz" and "Wikipedia" F is defined as subset of Q. This implies that it also could be empty, although in column labeled "Michael Sipser" there is a special state q_accept that explicitly exist in Q, therefore F is not-empty. Unfortunately there is no information if q_accept has to be reachable from start state. But consider this: How one could say that this machine is actually writing "TM" every two cells? If you investigate tape states while machine is still running it might change (on meta-level you my expect that this is actually true but you might for example make some bug that you're not aware of). The only way to be able to see that "TM" has been written is after the machine halts. [1] http://www.cis.upenn.edu/~matuszek/cit596-2012/NewPages/turing-machine-definitions.html http://www.cis.upenn.edu/~matuszek/cit596-2012/NewPages/turi...