Talk:Infinite state machine
Is this a Turing machine?
I don't see how this differs from a normal Turing machine. Or more specifically a "universal" Turing machine. My problem is probably clearer if we replace the use of the word "infinite" with "unbounded". The "tape", or more generally "memory", is unbounded; iterative "tracks" and unary numbers are also unbounded (eg: a Nul terminated string). The tape head of a Turing machine does NOT have an address in it. The normal idea is that it is always "here" and the tape moves up or down as far as required (without bounds); though a "trolley" on a rail track is also suggested.
A universal Turing machine has the FSM placed on the tape and so it uses as much of the tape as required, it can even use a slice of the whole tape so being an "unbounded" portion of the tape.
So in summary you seem to be describing a von Neumann architecture Turing machine. Right? Rdebath (talk) 19:19, 5 May 2024 (UTC)
- I actually don't fully remember what I was thinking when I wrote this. It definitely feels off computationally speaking, looking at it a year later. But it certainly is not a universal Turing machine. The wording is quite confusing. Either way, the machine here is infinite, not unbounded (even though some of the wording implies otherwise?). Turing machines, even ones simulated by a UTM, have a finite state machine controlling the head. So it's not a Turing machine, and also not really equivalent. It's weakly equivalent, I'm pretty sure Wolfram's 2 symbol 3 state universal Turing machine uses similar logic of an infinite input program, but definitely not normally equivalent. Although, I remember reading somewhere that the behavior of a Turing machine on a tape that has been completely initialized (there is no bound to how far the initialization goes) behaves in fundamentally unpredictable, unmodelable ways.