Transfinite program

A transfinite program is a program that is not finite.

The vast majority of programs in conventional computer science are considered to be finite objects. (see, e.g. Knuth's definition of an algorithm as a finite number of steps). One plausible reason behind this is that they are generally considered to be syntactic objects, and such objects are generally considered to be intrinsically finite.

Such considerations are not held as strongly in esoteric programming language circles.

This page aims to chronicle some of the cases where programs arguably fail to be finite. But note that this refers to individual programs; it is quite common for the set of all programs in some programming language to be (countably) infinite. It is also quite common for a finite program (or "initial configuration") to result in an infinite loop, possibly along with an infinitely-expanding allocation of storage; this is also not what we mean here.

Uncountably infinite programs

Programs consisting of any countable amount of irrational real numbers (finite or countably infinite) contain countably infinite data. This is because the digits of the base expansion, or the denominators of the continued fraction, or any other representation, can be put into correspondence with the naturals. You can do this in a number of ways, but using a common pairing function is the most straightforward. Note that each irrational real number has countably infinite digits, it can be put in correspondence with $\mathbb {N}$, meaning $|\mathbb {N} |$ many digits. A countably infinite amount of irrational real numbers is $|\mathbb {N} |$ numbers, each with $|\mathbb {N} |$ digits, or $|\mathbb {N} |\times |\mathbb {N} |=|\mathbb {N} \times \mathbb {N} |$ digits in total. Since there are functions $f:\mathbb {N} \times \mathbb {N} \rightarrow \mathbb {N}$ (like Cantor's pairing function), meaning $|\mathbb {N} \times \mathbb {N} |=|\mathbb {N} |$, the cardinality is countably infinite.

In order for a program to have uncountably infinite data it would have to be encoded using the entirety of some uncountable set, like the irrational real numbers.

Countably infinite programs

Some languages admit the possibility of a countably infinite program in that language.

Collections of real numbers as programs

Any language where the program can only be represented by a finite list of real numbers.

Note that if the program consists of even only one real number, and that real number is allowed to be an uncomputable real number, it might make the question "Is this programming language Turing-complete?" meaningless, in the following way: an interpreter for the language can simply produce output based on bits from the program, without doing any computational processing on them at all, yet still be able to produce outputs that no Turing-machine ever could. An interesting point this question and answer misses is the concept of a hyper computer. In my eyes, this would produce a hyper computer where the outputs of the hyper computer and the outputs of a Turing machine are disjoint.

Note that if the program consists of even only one real number, and that real number is allowed to be any computable real number, a weaker version of the above still applies, because there is a computable real number (let's call it N) which encodes in itself every possible computation, and the interpreter could simply pick one of the computations out of N and parrot it without doing any computation of its own. See discussion on The Waterfall Model.

"Real number" can be replaced by "countably infinite sequence of digits" (and indeed, "digits" can be replaced by "symbols drawn from a finite set of possible symbols"), to generalize the statements above.

Sequential tag systems

A Sequential tag system is sometimes the simplest way to prove a language Turing complete – if the language accepts an infinitely long input program. This definition of Turing-completeness is quite controversial, due to the introduction of infinity. However, because a Cyclic tag program compiles into a sequential tag program that repeats indefinitely, then in many cases, this will lead to an infinitely repeating program in the language whose computational class is being examined, something that most (but not all) mathematicians will accept as a legitimate initialization.

Cellular automata

Initial forms of infinite size may be considered for cellular automaton. For example, in John Conway's Game of Life, it is possible to specify a barber pole which is infinitely long; unlike a finite barber pole, it does not require "caps" on the ends.

In addition, proofs of Turing-completeness for some cellular automata stipulate that the infinite playfield is initially filled with some pattern. Models which require an infinite non-blank initial configuration can be called weakly Turing-complete.

SMETANA

Consider a SMETANA program with n steps. Since SMETANA is not explicit about the limits of n, we can technically take it to be either finite or infinite. It has been taken to be infinite at least once when considering its computational class. However, certain issues arise when doing so. See the SMETANA article for more information. SMETANA To Infinity! is an extension of SMETANA which has a way of specifying infinitely many steps, however the input program itself remains finite.

Unbounded programs

With an expanded notion of "program" there may be subtler cases as well. For example, even in conventional computer science, REPLs are intended to run a loop which interactively accepts a "command entry" on each iteration, which may incrementally build and refine a program, and in theory this loop may run forever, building a program using an unbounded number of command entries.

Computability

If a transfinite program can be simulated on a classically defined Turing machine, it is considered computable. Certain transfinite programs are not computable for the same reason that certain initial configurations and therefore operations of Turing machines are uncomputable. This is related to the concept of weak universality, which is a universal machine which is only universal if its input is encoded in some infinitely long manner. As noted on the page, certain infinite initial configurations are computable, like all periodic sequences and many aperiodic sequences. Not all infinite initial configurations are computable, however. Initial configurations/numbers/inputs which are constructed using uncomputable functions (like Chaitin's constant) are not computable. Therefore, in order to be computable, a transfinite program must be able to be generated using a typical Turing machine.

A sequential tag system that has been produced from a cyclic tag system is computable, since the Turing machine which simulates both models can be identical without having the effect of the simulated machine differ.