Talk:Swapping Turing Machine

Not Turing-complete?

I don't think this is Turing-complete(it should be a bounded-storage machine), as it just addresses an index that has an upper bound, which is dynamically updated after each operation. This shows that it addresses only a finite amount of memory. In User:Oerjan's proof of the computational class of Drive-In Window, he stated: "Drive-In Window is a bounded-storage machine, since a program doesn't have access to more bytes than the number of persons in it." Although the number of persons in Drive-In Window can by dynamically updated, it always has an upper bound, which is analogous to the situation of the Swapping Turing Machine. --A (talk) 13:36, 10 June 2019 (UTC)

It is Turing complete, as the register machine conversion shows. While there is an upper bound on the amount of nonblank symbols, there is no upper bound on the size of the tape; as such, symbols can be moved to arbitrary locations, and thus infinite storage can be simulated, for example by measuring the distance between symbols. TuxCrafting (talk) 13:40, 10 June 2019 (UTC)

Unbounded locations cannot be hard-coded into a program in a finite amount of time, especially when the index involves infinity. The programmer cannot type it in a finite amount of time, so it cannot simulate unbounded memory. (Note that a programmer can type a program in the Turing machine that indexes infinity in a finite amount of time, which is always move the tape right.) If this computational model cannot index infinity, it certainly cannot simulate infinite memory. If the user is constantly typing the index, this will never get to the step when the index infinity gets indexed.--A (talk) 13:45, 10 June 2019 (UTC)

But it *can* index infinite memory. In fact it can with a single state: ⟨loop, 0⟩ → ⟨loop, N, R⟩. Remember that this is not just a simple finite state machine; it has access to a tape, and it can arbitrarly move around in that tape. There is no need to specify infinite indices in the transition function if it can loop, which it can. TuxCrafting (talk) 13:51, 10 June 2019 (UTC)

Sorry, I did not completely read the article and thought that it does not support moving the tape head.--A (talk) 13:57, 10 June 2019 (UTC)

Look what Arseniiv said below. "It can’t write arbitrary data on tape, it can only swap what’s already there, so denied to do that, it would be unable to affect the tape at all." So, it is impossible to simulate an infinite loop that can move the tape head to a direction without typing the address, thus it cannot simulate infinite memory. --(this comment by A at 15:06, June 10, 2019 UTC; please sign your comments with ~~~~)

What? Of course it's possible to do an infinite loop that can move the tape head without typing the address. The loop state I gave earlier does just that. And while it is true that it cannot write arbitrary symbols, if the initial state of the tape is definite, it is possible to store data. As my Minsky machine example shows. TuxCrafting (talk) 15:18, 10 June 2019 (UTC)

Turing-completeness via compiling to the Turing machine or via reduction

I have read the page, and as far as I can tell, the Swapping Turing Machine does the similar things as a standard Turing machine, as it can move the tape head arbitarily in a tape(as what TuxCrafting has shown above). In addition, (as far as I can tell) it is an extension of the Turing machine, as its subset conforms the definition of the Turing machine. Can it be used as a possible proof for proving that the Swapping Turing Machine has equivalent computational power with the Turing Machine? --A (talk) 14:23, 10 June 2019 (UTC)

Please read it carefully. It can’t write arbitrary data on tape, it can only swap what’s already there, so denied to do that, it would be unable to affect the tape at all. And it wouldn’t be such an interesting example if it was an extension. arseniiv (talk) 14:26, 10 June 2019 (UTC)

It can simulate an extension... TuxCrafting has said above: "Of course it's possible to do an infinite loop that can move the tape head without typing the address. The loop state I gave earlier does just that. And while it is true that it cannot write arbitrary symbols, if the initial state of the tape is definite, it is possible to store data. As my Minsky machine example shows." --A (talk) 04:04, 11 June 2019 (UTC)