(1) Grace sent you a message
| Paradigm(s) | Imperative |
|---|---|
| Designed by | Hakerh400 |
| Appeared in | 2020 |
| Computational class | Turing complete |
| Major implementations | Unimplemented |
| File extension(s) | .txt |
(1) Grace sent you a message is a Turing-complete brainfuck derivative which is based on linear bounded automata.
Overview
Input is an ASCII string and the output is a single bit.
Source code consists of two identical structures. Each structure starts with two positive numbers and then a brainfuck program follows. For example:
2 3 ,[+.,] 11 5 >+<-[.[-.],]
Each of the two structures represents a linear bounded automaton. Let the first number be and the second be , the memory size of the brainfuck program in that structure is equal to , where is the size of the input (not the actual input, but internal input, it is explained in the next paragraph).
There is an internal state, which is an ASCII string. The internal state in initially empty (zero-length string). First, interpreter picks one of the two brainfuck programs and executes it, providing the internal state as its input. When (if) the brainfuck program halts, the output of that program is the new internal state. The interpreter then picks the same or the other program, executes it with the current state and sets its output as the new state.
If there is a sequence that leads to the actual user input (internal state becomes the user input), then interpreter outputs 1 and halts. If there is no such sequence, interpreter either does not halt, or outputs 0 and halts.
Computational class
A TM can be encoded as a string (states, current state, memory, data pointer). LBA can simulate a single TM step. Therefore, iteratively applying an LBA to a TM state can simulate its computation. Since a TM can determine whether an LBA halts, we can write a Grace program that takes a TM and expected output as the input (we encode it somehow) and prints 1 iff the TM halts producing the expected output, prints 0 iff the TM halts producing some other output and loops forever iff the TM does not halt.
Interpreters
Unimplemented.