Selfmodifying Turing machine
Paradigm(s)  Imperative 

Designed by  Hakerh400 
Appeared in  2020 
Computational class  Unknown 
Major implementations  Interpreter 
File extension(s)  .txt 
Selfmodifying Turing machine is a sort of Turing machine which uses the same memory for storing states, data, data pointer, input and output.
Contents
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):
 Parity
 State index size
 Current state index
 Data pointer size
 Data pointer value
 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 1
s, 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 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 bits.
Data pointer
After the last state (that is address (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:
 Xor (1 bit)  tells whether the pointed bit will be flipped
 Move (1 bit)  tells whether the data pointer will be altered
 Direction (1 bit)  if Move is
1
, then0
means left and1
means right  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
(binary101
)
Then we perform the next three operations (order is important):
 If Move is
1
, update the data pointer (if Direction is0
, 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.  Write the new state index to the memory location from where it is parsed.
 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 1
s 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.