Deadfish TM

Deadfish TM is a sequel to Deadfish PDA by User:BoundedBeans, both derivatives of Deadfish. Deadfish PDA describes push-down automata, while Deadfish TM describes Turing machines.

Description

The accumulator in Deadfish is equivalent to the state in Deadfish TM, except that the square command cannot be used to increase the state beyond 256. This means there are a total of 256 states in Deadfish TM, having values from 0-255. If the state is ever below 0 or above 255, the program halts. Deadfish TM also has a tape that is unbounded in both directions, containing symbols which can be any character that is:

• Printable
• Not a control character
• In Unicode range 0000-FFFF (in the basic multilingual plane)
• Not whitespace or a hashtag

It also has a head which points to one symbol at a time, and can move left or right.

There are two aspects to check in every iteration:

1. State
2. Currently pointed symbol

Unlike Deadfish PDA, input is not given at every iteration. Instead, there are two ways to input. One is that the initial tape from the starting point and to the right of it is specified by input. One line of input is taken in and stripped of any disallowed symbols such as spaces and hashtags. Starting at position 0, input is put into the tape character-by-character, moving right at each step. Another way is to use the "c" command in the deadfish code of a transition, which will input a character onto the tape, changing to "!" if the character is invalid.

Execution

The program takes one line of input to initialize the tape, stripping any invalid characters. The rest of the tape is filled with the symbol "!". The program then searches through the cases to find a match with the current state and symbol. If it finds a match, it runs the corresponding condition. If it doesn't, it runs the default transition.

Syntax

Programs start with the default transition, then a newline, then a repeated pattern of:

1. A case
2. A newline
3. The transition for the case
4. Another newline

The last transition does not need to have a newline.

Optionally, after a transition or case, a space followed by anything may be written to notate a comment. This must be on the same line as a valid case or transition, if you want to write a comment in a form that doesn't relate to any case or transition, just make an explicit case and transition that will never be used. For example, if you don't use the apostrophe or colon as symbols, you can write:

0 ' ***This is a comment (note the asterisks are not necessary, just look nice)***
# ' L 1
1 ' ***Another comment***
# ' L 1
2 ' ***A third comment***
# ' L 1
3 ' Asterisks are not necessary
# ' L 1
4 ' Simply count up in states
# ' L 1
255 ' If you run out of states
# ' L 1
0 : Use a different symbol you aren't using
# : L 1

Case syntax

When writing a case, you should type the following, in order:

1. The numerical state to check, if multiple, separate by commas, with no spaces
2. A space
3. The symbol(s) to check, if multiple, do not use a separator.

Alternatively you can separate exactly two numerical states by a hyphen to specify a range. If there is a range there should be no other numbers.

A few examples:

Check if the state is 8 and the symbol is "J":

8 J

Check if the state is between 17 and 29, inclusive, and the symbol is "N", "{", ">", or "q":

17-29 N{>q

Check if the state is 81, 155, 156, or 209 and the symbol is any capital letter:

81,155,156,209 ABCDEFGHIJKLMNOPQRSTUVWXYZ

Invalid examples:

5-17,28 j (range and comma in the same case)
7 # (symbol is a hashtag)
8-2 Hu (invalid range)
10-10 @ (invalid range)

Transition syntax

Transitions should be written with the following syntax:

1. The deadfish code to run. It may contain one or more of the following commands
   • i - Increment the state
   • d - Decrement the state
   • s - Square the state
   • o - Output the state numerically
   • a - Output the state as an ascii value
   • c - Input a character onto the current tape cell
   • # - A no-op
2. A space
3. The character to change the cell to
4. Another space
5. L to move the pointer left, R to move it right (it cannot be anything else)
6. Another space
7. 1 to halt, 0 to not halt, 2 to halt and output the tape, 3 to output the tape without halting (anything else is an error)

Examples:

Increment, square, decrement, output the accumulator, and decrement the accumulator 6 times, change the symbol to "Y", move right, don't halt:

isdodddddd Y R 0

Do nothing to the accumulator, change the symbol to "[", move left, don't halt:

# [ L 0

Halt:

# ! L 1

Computational class

256 states and thousands of symbols is enough to emulate many universal Turing machines. Only using states 0-4 and symbols !abcd is enough to emulate any Turing machine given certain input. Deadfish TM also maps almost completely directly to Turing machines. Therefore, Deadfish TM is Turing-complete.

Examples

Hello world

(Input must be empty)

# ! L 1
0 !
iiiiiiiisiiiiiiiia ! L 0
72 !
iiiiiiiiiiiiiiiiiiiiiiiiiiiiia ! L 0
101 !
iiiiiiia ! L 0
108 !
ai ! L 0
109 !
iia ! L 0
111 !
ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddda ! L 0
32 !
ddddddddddddddddddddddsiiiiiiiiiiiiiiiiiiia ! L 0
119 !
ddddddddai ! L 0
112 !
iia ! L 0
114 !
ddddddaii ! L 0
110 !
dddddddddda ! L 0
100 !
ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddda ! L 1

Truth-machine

# ! L 1
0 0
o 0 L 1
0 1
iisiiiisddddddddddddddd 1 L 0
49 !
a ! L 0

Unary adder

(Input two numbers input in unary with 1's, separated by a 0)

# ! L 1
0 1
# 1 R 0
0 0
i 0 R 0
1 !
# ! L 2
1 1
i 0 L 0
2 0
dd 1 R 0

Interpreter

• Common Lisp implementation of the Deadfish TM programming language.