Turinf machine

From Esolang
Jump to navigation Jump to search
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 3 space separated decimal non-negative integers (for non-halting states): the first one 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.