Self-modifying Turing machine

Self-modifying Turing machine

Paradigm(s)	Imperative
Designed by	Hakerh400
Appeared in	2020
Computational class	Unknown
Major implementations	Interpreter
File extension(s)	.txt

Self-modifying Turing machine is a sort of Turing machine which uses the same memory for storing states, data, data pointer, input and output.

Overview

Memory is unbounded tape of bits. Unlike in regular Turing machine, here memory has only positive addresses.

Source code consists only of bits. All the bits from the source code are placed at the beginning of the memory.

Input and output are also sequences of bits. Before the program starts, each input bit is prepended with bit 1 and concatenated to the source code. The rest of the memory are zeros. Then the program starts.

For example, given the following source code:

001011101

and input string:

00000000110

memory will initially look like this:

0010111011010101010101010111110000000000000000000000000000000000000000000000000000000000...

Program execution

Program halts when the first bit of the memory (bit with index 0) becomes 1. If it is 1 initially, then the program halts immediately.

While the first bit of the memory is 0, parse the following information (each data structure is colored using different color to make understanding easier):

1. Parity
2. State index size
3. Current state index
4. Data pointer size
5. Data pointer value
6. Memory bit being pointed

We explain all of these on this sample source code (new lines and spaces added for readability):

00
101000
101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 100010 000000 101000
1010101000
0000001010

Parity

The second bit of the memory (bit with index 1) tells us whether we consider odd or even bits when parsing data structures. If this bit is 0, we consider only even bits, otherwise we consider only odd bits.

00
101000
101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 100010 000000 101000
1010101000
0000001010

In our example it is 0, so we parse the remaining data structures by ignoring odd bits (odd bits are colored in gray).

State index

We start from the first bit after the parity bit and count the number of consecutive 1s, including the first 0 after them:

00
101000
^ ^ ^
| | |
First bit 1
  | |
  Second bit 1
    |
    First bit 0 after them

Thus, total count is 3 (two bits 1 plus the 0 after them). It means that there is total number of $2^{\color {maroon}3}=8$ states. The next 3 bits need to be parsed as a binary number and it represents the current state index:

00
101000
101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 100010 000000 101000
1010101000
0000001010

Current state index is 111, which is 7 when converted to decimal.

Then next 8 states follow. Each state is defined using $c=2\cdot \left({\color {maroon}3}+3\right)$ bits.

Data pointer

After the last state (that is address $1+2\cdot {\color {maroon}3}+c\cdot 2^{\color {maroon}3}$ (not counting odd bits)), we parse data pointer size and data pointer value in a similar manner as parsing state index size and state index value:

00
101000
101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 100010 000000 101000
1010101000
0000001010

We see that data pointer size is 5 and data pointer value is 3 (binary 00011).

When resolving the pointed bit, we consider both odd and even bits and we count bits from the beginning of the memory. The third bit is 0 (it is also the unused (unused for parsing) bit after the first bit of the state index size):

00
101000
101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 100010 000000 101000
1010101000
0000001010

State structure

Each state has two parts with identical structure: one part for the case when the pointed bit is 0 and the other for the case when the pointed bit is 1. Each part has the following structure:

1. Xor (1 bit) - tells whether the pointed bit will be flipped
2. Move (1 bit) - tells whether the data pointer will be altered
3. Direction (1 bit) - if Move is 1, then 0 means left and 1 means right
4. Next state index (3 bits)

In our example, state index is 7, which is the last state. Pointed bit is 0. Here is our state (the relevant part is marked):

00
101000
101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 101010 000000 101010
000000 100010 000000 101000
1010101000
0000001010

Now we parse the state structure:

• Xor: 0
• Move: 0
• Direction: 0
• New state index: 5 (binary 101)

Then we perform the next three operations (order is important):

1. If Move is 1, update the data pointer (if Direction is 0, then decrement it, otherwise increment it) and save it to the memory location from where it is parsed. If overflow occurs, keep only lower bits.
2. Write the new state index to the memory location from where it is parsed.
3. If Xor is 1, flip the pointed bit.

Note: If Xor is 1 and the pointed bit is modified in steps 1 or 2, the new value of the pointed bit (after step 3) is inverted value of the pointed bit before step 1. So, if the pointed bit was 0, then in step 1 modified to 1 and in step 2 unchanged, then if Xor is 1, the pointed bit will not be flipped again, because it is already 1. This applies only if Xor is 1. If Xor is 0 and the pointed bit is modified in steps 1 or 2 (note that it cannot be modified in both steps), it will not be reverted to the original value in step 3.

Output

After the program halts, parse the output starting from the first address after the data pointer. Output format is the same as the input format (while there are 1s at even positions (this has nothing to do with the parity defined by the second memory bit) output bits from corresponding odd positions).

Examples

Cat

Source code:

000000100000000000000000000000000000000000

Same program, but with proper formatting:

00 // Parity is 0
00 // State index is represented using 1 bit (total 2 states)
00 // Current state is the state with index 0
100000 00 000000 00 // State 0
000000 00 000000 00 // State 1
00 // Data pointer is represented using a single bit
00 // Data pointer points to the first bit of the memory (bit with index 0)

Then we parse the state:

100000 00
^ ^ ^  ^
| | |  |
Flip the pointed bit
  | |  |
  Do not alter data pointer
    |  |
    Direction left (ignored, since Move is 0)
       |
       Go to the 0th state

After this instruction, the only change in the memory will be flipping the first bit, so the program will halt. Because the source code ends directly after the data pointer, we parse the output string from the same location in which the input string is located, so it is identical to the input string.

Note: This program halts in 1 instruction. We could also modify the source code to replace the first bit of the memory with 1. It would also be the Cat program, but it would halt in 0 instructions.

Computational class

Lacking formal TC proof.

Interpreters

Interpreter