An extended Turing machine implementation

The AlanZ80X is an idea that takes the concept of a Turing machine to a new level. It may be possible, but it’s not certain that it will succeed. It might get made, but it's not certain. But I can say that it's great for fun. And to be challenging in the fun, it has to fit into 64kB.

This state machine differs from Turing's original model in several ways: it has four general and two special I/O tapes and some registers. But differs from traditional multi-tape machine, because it always handles only two tapes (and/or registers). It reads the one specified in the previous tuple and writes the one specified in the current tuple. The purpose and access mode of the general tapes are not specified. The machine will return to this setting after restarting.

The recommended setup defines a user data and program tape, a temporary tape, and a results tape. The machine has two additional special-purpose tapes: the stack and the other representing one of the standard output devices. Machine can write to output device: CON:, AUX:, LST:, PRN:, TRM: and if you are very lucky, how do you have PUN: instead of or in addition tape. But it can also be used as a pair of tapes, one as the data tape and the other as the marker tape for the data tape. You can also configure the way the tapes are accessed and the feedback method for failed readings. The tapes are represented by text files that are updated after each step.

One register can be used arbitrarily and the others provide information about the current state of the machine. The purpose and permissions of the registers are predefined. The registers store data as a string of symbols, and can be specified in the tuple instead of a tape.

The machine also has a simple interrupt handling. The interrupt request is initiated by a keystroke.

The machine works only based on the status table. The machine's basic program (tuples), settings, and commands required for automated execution contained in t36 file. In the state change table, the basic program is divided into parts according to the number of instruction codes and interrupts on the program tape.

The framework is command-line controlled. The help provides information about the commands available on the command line. We can change the program's breakpoint, tracking, number of steps, symbol set, and the association of tapes and files. We can get various information about the machine, tapes, and registers. We can load the t36 file and run the machine even step by step.

Its operation is generally simple: the loaded t36 file contains all the data required for the machine to operate. After starting the machine, it determines the symbol to be printed and the next state based on the scanned symbol and the current state.

This process is not that simple in the default setting: after the machine starts, it starts reading the program tape (t₂), then reads the corresponding data from the data tape (t₁). The program and data tape now are read-only. During operations, the stack tape (t₅), which acts as a traditional stack, the temporary tape (t₄) and the accumulator register (r₀) can also be used. The result tape (t₃) is used to print the result. It is also possible to write to the console, but this is always write-only.

The state vectors for commands and interrupts are placed in two rows of the state table (jump tables). When an interrupt request is detected, the basic program jumps to the appropriate state and then acts accordingly.

Copyright (C) 2025 Pozsár Zsolt pozsarzs@gmail.com

Startup screen

Number Shift #1

Number Shift #2

$$ M = (Q, T, R, S, D, q_0, \delta), \text{ where the: } $$

• Q: finite state set,
• T: finite tape set,
• R: finite register set,
• S: finite symbol set,
• D: finite head moving direction set,
• q₀: initial state and
• $\delta$: transition function.

$$ \delta: (Q \times (T \cup R) \times S) \rightarrow Q \times (T \cup R) \times S \times D $$

Input: current state, a selected data source (tape or register), and the symbol read from it.
Output: new state, selected data target (tape or register), symbol to be written, and head movement.

These are the machine's sets in alphabetical order, with indexed elements. Most elements of a set are abstract identifiers, but any elements that have a value are specified. This value is used in the t36 file and in program messages.

Finite set of head movement directions is as follows:

$$ D = \{ d_0, d_1, d_2 \}, \text{ where the: } $$

• d₀ = L, it is the left direction,
• d₁ = S, it is the stay here,
• d₂ = R, it is the right direction.

Left/right moves must be specified for all registers and tapes, but for some they are ineffective. The stack head moves independently, for single-symbol registers the head cannot move, for standard output it always moves right.

The finite set of registers and the symbol chains on them are as follows:

$$ R = \{ r_0, \dots, r_9 \} \text{ and } w(t_n) \in S^*, \text{ where the: } $$

• r₀: Accumulator (ACC) - char type,
• r₁: t₁ Tape Position (1TP) - integer type,
• r₂: t₂ Tape Position (2TP) - integer type,
• r₃: t₃ Tape Position (3TP) - integer type,
• r₄: t₄ Tape Position (4TP) - integer type,
• r₅: Stack Tape Position (STP) - integer type,
• r₆: Program Step Counter (PSC) - integer type,
• r₇: Bottomless Register (BLR) - char type,
• r₈: Command Vector Register (CVR) - char type,
• r₉: Interrupt Vector Register (IVR) - char type,
• w: Symbol chain in the register.

All register value are stored as string. Reading and writing is done in the same way as with tape. The bottomless register swallows the symbol written into it and always returns '_' when read.

The state is called an m-configuration in Turing terminology. The finite set of states is as follows:

$$ Q = \{ q_0, \dots, q_{127} \}, \text{ where the: } $$

• q₀, is the default initial state,
• q₁-q₁₂₄ are the free space,
• q₁₂₅ is the command vector area,
• q₁₂₆ is the interrupt vector area,
• q₁₂₇ is the mandatory final state.

Finite set of tape symbols is as follows:

$$ S = \{ s_0, \dots, s_{39} \}, \text{ where the: } $$

• s₀ is the mandatory blank character (_),
• s₁ is the mandatory end character (#),
• s₂ is the mandatory command character (@),
• s₃-s₄₀ are optional symbols.

The set must have at least three elements. To use registers, decimal numbers must also be included in the symbol set. Default symbol set is '_#@.-ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'.

The tape files store data in human-readable form. Their content is updated with every change in status.

The finite set of tapes and the symbol chains on them are as follows:

$$ T = \{ t_0, \dots, t_5 \} \text{ and } w(t_n) \in S^*, \text{ where the: } $$

• t₀: standard output device of the OS (CON:, LST:, ...),
• t₁-t₄: general purpose tapes,
• t₅: stack tape,
• w: Symbol chain on the tape.

By recommended setup:

• t₀: redirected to the CON: device,
• t₁: data tape,
• t₂: program tape,
• t₃: result tape,
• t₄: temporary tape and
• t₅: stack tape.

The operation of the machine is based on state transitions, which can be described by tuples, in the form below. Operating modes determine the direction of read and write operations.

Notes:

• d_j is the head moving direction over the input data carrier, d_j $\in$ D,
• d_k is the head moving direction over the result data carrier, d_k $\in$ D,
• d_j and d_k cannot be 'S' at the same time,
• q_i is the actual state, q_i $\in$ Q,
• q_m is the next state, q_m $\in$ Q,
• r_j is the register from which the machine reads a symbol, r_j $\in$ R,
• r_k is the the register to which the machine writes a symbol, r_j $\in$ R,
• r_m is the next register from which the machine reads a symbol, t_m $\in$ R,
• s_j is the actual symbol read from the data carrier, s_j $\in$ S,
• s_k is the symbol to be written to the data carrier, s_k $\in$ S,
• t_j is the tape from which the machine reads a symbol, t_j $\in$ T,
• t_k is the tape to which the machine writes a symbol, t_j $\in$ T,
• t_m is the next tape from which the machine reads a symbol, t_m $\in$ T.

This file type is used to load the Turing machine's (base) program, define initial settings, and automate execution. The following table follows the structure of the file and provides a brief description of the lines.

Note:

• This file type has limited use with the previous version of the Turing machine, the table provides guidance.
• If the starting symbols specified in the CONF section is not '_#@', then they will be inserted.
• The default value of the INIT option in TAPE section is 2 (tape t₂).
• The line length of the t36 file is maximum 1024 characters.
• Tape access modes: LO/LS/SO/NN Load only/Load and save/Save only/None.
• The 9-tuples must be specified in the following form:

ST000 R7_RST2000 ..., where the:

'STnnn' is the state, where nnn is the state number. The following groups are tuples for state nnn. Meaning of the characters in the first tuple:

• q_i = 000, it is the initial state,
• t_j = not specified, at the start t_j=t₀, in the following it is the same as the t_m of the previous tuple.,
• r_k = R7, it is the bottomless register (BLR),
• s_j = not specified, the symbol number is the same as the tuple number in this status line,
• s_k = '_', it is the symbol to be written to result tape,
• d_j = R, it is the head moving direction over t_j tape,
• d_k = S, it is the head moving direction in r_k register,
• t_m = T2, it is the 2nd general tape,
• q_m = 000, it is the final state.

The example program increments and decrements the digits of the numbers on the data tape according to the instructions on the program tape.

The program is represented by the files ns.t36 and the tapes are represented by the files ns_*.tap.

The program can be controlled with the following command line commands.