Binary Turing Machine!?

Binary Turing Machine!? is an esoteric programming language created by User:Largejamie in August 2022 whose programs create and then run input on a Turing machine.

Overview

Binary Turing Machine programs only use the characters 01!? and newline.

Each line of the program will do something different, depending on the last character of the line:

Character	Description
!	Create a new part of a rule for the Turing machine
?	Create a new symbol that is initially written onto the tape (part of the Turing machine's input)

If a line ends in !, it will create a new part of the rule for the Turing machine. The rules are created in the following order:

1. Current state
2. Current symbol
3. New state
4. New symbol
5. Direction (Right if even, Left if odd).

So the following 5 lines:

0!
1!
10!
11!
100!

Would mean that when the Turing machine is in state 0 and reads the character 1, it will change to state 2, write the character 3, and then move to the right (since 4 is even).

If a line ends in ?, it will create a new part of the input for the Turing machine, meaning what appears on the initial tape. So the following 3 lines:

1?
10?
11?

Would mean that the initial tape of the Turing machine looks like:

| 1 | 2 | 3 | B | B | B | ...

Where B indicates blank.

When a BTM program is finished being read, it will run the Turing machine that has been created on the input that has been specified. Some particulars about the Turing machine:

• The Turing machine's initial state is state 0
• Blanks are represented by 0
• The tape of the Turing machine is infinite in one direction, meaning that it has a leftmost end. Attempting to move left past the end of the tape will result in no movement occurring.
• The Turing machine includes two "special" states to allow the programs to input and output:
  • State 1, which represents input. This state will write a user input to the current location of the tape, change to state 0, and move to the right.
  • State 2, which represents output. This state will print the value on the tape and move to the right until it encounters a blank, at which point it will change to state 0 and move to the right.
• Once the Turing machine does not have a specified rule for a particular state/input, it will halt.

Examples

Hello, world!

0!
1!
10!
0!
0!
1?
1001000?
1100101?
1101100?
1101100?
1101111?
101100?
100000?
1110111?
1101111?
1110010?
1101100?
1100100?
100001?
1010?

Binary cat

A user may input 1s and 0s as many times as they would like. Once they input a new line, the program will print out all the 1s and 0s that they input as a single string.

0!
0!
11!
0!
0!
11!
0!
100!
0!
0!
100!
0!
1!
1!
1!
0!
1!
101!
1!
1!
101!
0!
111!
0!
0!
101!
110000!
110!
110000!
0!
101!
110001!
110!
110001!
0!
110!
1!
100!
1!
0!
111!
1!
111!
0!
1!
111!
0!
1000!
1010!
0!
1000!
0!
1001!
0!
0!
1001!
0!
1010!
10!
1!
1010!
0!
1011!
0!
1!
1011!
0!
10!
0!
0!
1011!
110000!
1011!
110000!
1!
1011!
1010!
1011!
1010!
1!
1011!
110001!
1011!
110001!
1!

It works by generating a Turing Machine with the following transition function:

(0, 0) => (3, 0, 0)
(0, 1) => (5, 1, 1)
(3, 0) => (4, 0, 0)
(4, 0) => (1, 1, 1)
(5, 48) => (6, 48, 0)
(5, 49) => (6, 49, 0)
(5, 0) => (7, 0, 0)
(6, 1) => (4, 1, 0)
(7, 1) => (7, 0, 1)
(7, 0) => (8, 10, 0)
(8, 0) => (9, 0, 0)
(9, 0) => (10, 2, 1)
(10, 0) => (11, 0, 1)
(11, 0) => (2, 0, 0)
(0, 1) => (5, 1, 1)
(11, 48) => (11, 48, 1)
(11, 49) => (11, 49, 1)

And running on a blank tape.

Computational Class

Binary Turing Machine!?, as its name suggest, has the same power as a Turing machine.

Interpreters

Interpreter in Python