# 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:

- Keep a buffer of states generated by
*M*so far. Set the current state to the initial state. - Simulate
*M*, adding each generated state to the buffer, until the current state has been generated. - Execute the current state. Set the current state to the next state.
- If the current state is a halting state, then stop.
- 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 : 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)