Talk:Turinf machine

So, as I understand it, a Turinf machine is any countable sequence of states/transitions which can be output by a Turing machine. (Also, for some reason they don't have initial or halting states. Is that intentional or an oversight?) Naturally, by only accessing a finite number of states, any Turing machine can be reduced to a Turinf machine. However, a Turinf machine defined by a Turing machine M seems trivially reducible to a Turing machine:

1. Keep a buffer of states generated by M so far. Set the current state to the initial state.
2. Simulate M, adding each generated state to the buffer, until the current state has been generated.
3. Execute the current state. Set the current state to the next state.
4. If the current state is a halting state, then stop.
5. If the current state is in the buffer, proceed from step 3; otherwise, proceed from step 2.

The basic idea is that since at most one new state is used per step, we can lazy-evaluate states as they are needed, requiring only finite memory at any given time. Overall, a Turinf machine is exactly equivalent to a Turing machine, and the language is Turing-complete. LegionMammal978 (talk) 13:46, 6 August 2020 (UTC)

The missing syntax for halting states was an oversight, thanks for spotting that. Regarding the Turing-completeness: maybe the specification was not clear enough (I reworded it, hope it is better now), but the whole point is that not all Turinf machines can be output by Turing machines. Some Turinf machines have states that cannot be defined by any algorithm that has a finite number of symbols. Here is an analogy with real numbers on interval $\left[0,1\right)$: since each real number on that interval can be encoded as an infinite string of binary digits, each such real number corresponds to a single Turinf machine program. Some of the real numbers (like Chaitin's constants) are uncomputable (there is no algorithm that outputs their digits), thus there is no Turing machine that can generate some Turinf machines. Being able to directly encode all digits of a Chaitin's constant (which is possible in a Turinf machine) allows us to solve the halting problem for any Turing machine. --Hakerh400 (talk) 15:11, 6 August 2020 (UTC)