Swapping Turing Machine
A Swapping Turing Machine is a computational model similar to a standard Turing machine, except that instead of being able to mark new symbols on the tape, it can only swap the position of existing symbols.
Description
A swapping Turing machine is a Finite state automaton that has access to an unbounded tape of symbols in a finite alphabet. This finite state automaton can read symbols, move the tape head, and swap the position of symbols using a swap register, which can contain either nothing or a tape position.
The transition function of a swapping Turing machine has the current state and the current tape symbol as inputs, and the next state, swap action, and tape head movement as outputs.
The swap action can be either N, i.e. "no swap", or S, i.e. "swap". The action N means to do nothing, and S that if the swap register is empty, the current tape head position is stored in it; otherwise, the symbol at the current tape head position is swapped with the symbol at the tape head position in the swap register, and the swap register is cleared.
Since the number of non-blank symbols is always the same as it is when the machine starts, it is also necessary to define a minimum tape configuration for a swapping Turing machine to be able to do useful computation.
Minsky machine → Swapping Turing machine conversion
A swapping Turing machine is equivalent in computational power to a standard Turing machine, which can be shown by converting a Minsky machine to a swapping Turing machine.
A Minsky machine is defined as having a fixed number N of unbounded registers being able to store a positive integer, and a finite state machine operating on those registers, with two operations (in addition of a halt state):
- ⟨Inc, R, S′⟩ — Increment register R and change state to S′.
- ⟨DecZ, R, S′1, S′2⟩ — If register R is nonzero, decrement register R and change state to S′1; otherwise, change state to S′2.
A Minsky machine with N registers can be converted to a swapping Turing machine, with the alphabet {0, 1}. The initial state of the tape is 2N 1's, with the tape head pointing to the leftmost such 1.
As a shortcut, tape movements are able to move by any positive integer, indicated with a superscript.
Each state S of the register machine is converted to swapping Turing machine states as follow:
- ⟨Inc, R, S′⟩
- ⟨S, 1⟩ → ⟨Ssearch, N, RR+N⟩
- ⟨Ssearch, 0⟩ → ⟨Ssearch, N, RN⟩
- ⟨Ssearch, 1⟩ → ⟨Sswap, S, RN⟩
- ⟨Sswap, 0⟩ → ⟨Sreturn, S, LN⟩
- ⟨Sreturn, 0⟩ → ⟨Sreturn, N, LN⟩
- ⟨Sreturn, 1⟩ → ⟨S′, N, LR⟩
- ⟨DecZ, R, S′1, S′2⟩
- ⟨S, 1⟩ → ⟨Scheck, N, RR+N⟩
- ⟨Scheck, 0⟩ → ⟨Ssearch, N, RN⟩
- ⟨Scheck, 1⟩ → ⟨S′2, N, LR+N⟩
- ⟨Ssearch, 0⟩ → ⟨Ssearch, N, RN⟩
- ⟨Ssearch, 1⟩ → ⟨Sswap, S, LN⟩
- ⟨Sswap, 0⟩ → ⟨Sreturn, S, LN⟩
- ⟨Sreturn, 0⟩ → ⟨Sreturn, N, LN⟩
- ⟨Sreturn, 1⟩ → ⟨S′1, N, LR⟩
The way this conversion works is by representing each register as a pair of bits: a "start bit" and a "value bit", with the value of the register being the distance between the start bit and its corresponding value bit. Therefore, incrementing is just a matter of swapping the value bit further away, and decrementing of swapping it closer. The bits of the registers are interleaved, to allow for having more than one register in a single tape.
It is also possible to convert a 2-register Minsky machine to a swapping Turing machine using only 3 1 symbols, by having the registers extend left and right instead of interleaving them. This shows that 3 non-blank symbols is all a swapping Turing machine needs for Turing-completeness. Actually doing the conversion is pretty simple and as such will be left as an exercise for the reader.