Turinf machine
| Paradigm(s) | Imperative |
|---|---|
| Designed by | User:Hakerh400 |
| Appeared in | 2020 |
| Computational class | Unknown |
| Major implementations | Unimplemented |
| File extension(s) | .txt |
Turinf machine is a Turing machine that has infinitely, but countably, many states.
Overview
Memory model is the same as in ordinary Turing machine (infinite tape of bits). The only difference is that a Turinf machine program is allowed to have infinitely many states, but the number of states must be countable.
It is important to note that the set of all Turinf machine programs is uncountable. That means that some of them we have no way to represent in a finite number of characters. For some Turinf machine programs, we can define all the states by creating an ordinary Turing machine that generates all the states. However, the set of all ordinary Turing machines is countable, so the number of Turinf machine programs generated in such manner would be countable. Therefore, some Turinf machine programs cannot be an output of an ordinary Turing machine.
Syntax
Syntax is implementation dependent. If a formal syntax is required (for this to be a programming language), let the source code be an array of states separated by new lines and each state is represented either as the "HALT" string (for halting states), or as two groups of 3 space-separated decimal non-negative integers enclosed in parentheses (for non-halting states) - the first group is for the current pointed bit being 0 and the second is for 1. In each group, the first number is 0 or 1 (0 - do not invert the memory bit, 1 - invert the memory bit), the second one is 0 or 1 (0 - go left, 1 - go right), and the third one is the next state (0-indexed). The initial state is the state with index 0.
Computational class
It is debatable what the computational class of this programming language is. On the one hand, since we have no way to represent some of the possible programs, we may consider Turinf machine uncountable. On the other hand, a Turinf machine program is not capable of solving the halting problem for an ordinary Turing machine on itself. However, since we have infinitely many states, we can encode all bits of a Chaitin's constant, effectively encoding solutions to halting problems for all possible ordinary Turing machines.