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 fi

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...