> Second part of this definitions says that one has to simulate turing machine (and uses the word 'alternatively' so basically it has to be the same but I can g

> Second part of this definitions says that one has to simulate turing machine (and uses the word 'alternatively' so basically it has to be the same but I can go anyway). I think that 'simulate' in this context mean 'producing same output' rather than 'doing step by step the same'. Internal tape states at certain point in time should not matter because while running they might change (or if they matter we could just return list of pair {state,time} at the end). > There is no doubt that non-halting turing machines exists but I'm not sure if that apply to this particular problem anyhow since they are not computing anything. The exact steps of a Turing Machine don't need to be emulated exactly, only the output needs to be the same. However, it's trivial to turn your back-and-forth example into a Turing-computable function: Let's call your back-and-forth machine "M1" and, without loss of generality, let's say it starts at cell 0, moves to cell 1, then back to cell 0. We can then define a new machine "M2" which outputs a list of M1's head positions at each step, based on a direct simulation of M1. In other words, M2 will output 01010101010101.... forever, never halting. The C preprocessor cannot simulate M2, precisely because it cannot simulate M1. Also, note that we don't need to wait for a Turing machine to halt before we read its output. There are many useful programs which should not halt, like servers and operating systems.