Self-modifying Turing machine

From Esolang
Jump to navigation Jump to search
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 cards, 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. Card index size
  3. Current card 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).

Card 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 cards. The next 3 bits need to be parsed as a binary number and it represents the current card 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 card index is 111, which is 7 when converted to decimal.

Then next 8 cards follow. Each card is defined using bits.

Data pointer

After the last card (that is address (not counting odd bits)), we parse data pointer size and data pointer value in a similar manner as parsing card index size and card 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 card 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

Card structure

Each card 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 card index (3 bits)

In our example, card index is 7, which is the last card. Pointed bit is 0. Here is our card (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 card structure:

  • Xor: 0
  • Move: 0
  • Direction: 0
  • New card 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 card 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 2 or 3 (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 // Card index is represented using 1 bit (total 2 cards)
00 // Current card is the card with index 0
100000 00 000000 00 // Card 0
000000 00 000000 00 // Card 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 card:

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

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