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

If a program can only be represented by an unending list of real numbers, then it isn't uncountably infinite. (If it can be represented by a finite list of real numbers, those can be put into correspondence with a single countable series of digits, so it's countably infinite).

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.

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.