TypeScript and Turing Completeness
Throughout this article, we will see a common construction of SomeGeneric<...> extends number ? ... : never. This is because some of our generic types operate in such a way that TypeScript cannot be sure that the result is numeric despite the fact we know that it is. Without this check, we cannot pass SomeGeneric<...> into another generic type that expects a number. This type guard allows us to provide that information to the type checker. Any use throughout the code below is merely an appeasement of TypeScript and not a logical requirement of what we are trying to build.
In a prior article I showed how we could use the type system in TypeScript to produce a basic arithmetical system. A natural question follows from that implementation regarding what is and is not able to be calculated from that system or some more complex system built on top of it. In other words: what can our type system compute or not compute? Can it compute anything? Or is it inherently limited in some computational aspect?
Once we start asking these types of questions we enter the realm of computability theory and, more specifically, Turing completeness. Rather than giving an exhaustive discussion of what we mean by the phrase “Turing completeness,” I will give only a high-level overview that pertains to the rest of the article and refer the reader to another article that deals with the matter much more deeply.
Broadly speaking, when we say a system is Turing complete we mean that it can handle any computation that can be described in a finite number of steps with a finite number of inputs. Essentially it is powerful enough to generically encode algorithms. Such systems can be general programming languages, Turing machines, the lambda calculus, and cellular automata. The manner in which such algorithms are specified and executed can look quite different, as we can see from the fact that all our examples themselves look quite different from one to the other.
Most programming languages are known to be Turing complete, and even some type systems (such as Rust’s) have been proved Turing complete. So, what about TypeScript? Obviously the part of TypeScript that is JavaScript is Turing complete, so we will focus on just the type system of TypeScript (since it cannot inherit computability from JavaScript) and show that it is, indeed, also Turing complete.
To prove this there are three general approaches we could take:
- Show that any Turing machine can be translated to TypeScript.
- Show that TypeScript can implement a universal Turing machine.
- Show that TypeScript can implement another known-Turing complete system.
The approach we will take in our endeavor is the third. We will do this by implementing an interpreter for the Turing complete esoteric programming language called Smallfuck.
Smallfuck
Architecturally, Smallfuck operates on a finite-length tape of bits (initialized as all 0s) with the ability to scan one bit on that tape at a time. Due to this architecture it has very few operations; in fact it has exactly five symbols in its language, three of which correspond to an action involving that tape while the remaining two involving conditionally jumping around the program’s instruction set based on the value of the current bit.
These symbols are:
*: Flip current bit<: Move left one bit>: Move right one bit[: Jump forward one position past matching]if current bit is0]: Jump backward to matching[
Also, when a Smallfuck interpreter executes the < or > operations, it must also consider the bounds of the tape. It cannot go left when it is at the beginning of the tape or right when at then end. Any such attempt will result in immediate termination of the program.
We will create a small set of representative programs to illustrate various features of this language and which we will need our interpreter to be able to execute properly. These programs are:
*>*>*: flip three bits in a row, terminating on the final flipped bit>*>*>*[*<]: flip three bits in a row to1, then loop backwards over those bits and flip back to0*[]: flip the bit to1and then infinitely loop between the two bracket characters — this program will never terminate*[>*]: loop across the tape, flipping each bit to1before terminating when it goes out of bounds of the tape*[>>*[<*]]: flip a bit then enter a loop to move around the tape before entering a sub-loop to move backward flipping bits
It would be helpful to give a full step-by-step evaluation of a program in order to elucidate the steps our own interpreter must take to properly evaluate an arbitrary program. To do this we will choose the second one listed above (>*>*>*[*<]).
1. Initialize a tape with the first bit and first instruction "in scope" v v
Tape: 00000000 Instructions: >*>*>*[*<]2. Evaluate `>` and move to next instruction v v
Tape: 00000000 Instructions: >*>*>*[*<]3. Evaluate `*` and move to next instruction v v
Tape: 01000000 Instructions: >*>*>*[*<]4. Evaluate `>` and move to next instruction v v
Tape: 01000000 Instructions: >*>*>*[*<]5. Evaluate `*` and move to next instruction v v
Tape: 01100000 Instructions: >*>*>*[*<]6. Evaluate `>` and move to next instruction v v
Tape: 01100000 Instructions: >*>*>*[*<]7. Evaluate `*` and move to next instruction v v
Tape: 01110000 Instructions: >*>*>*[*<]8. Evaluate `[`. Since the current bit is not `0`, move to next instruction v v
Tape: 01110000 Instructions: >*>*>*[*<]9. Evaluate `*` and move to next instruction v v
Tape: 01100000 Instructions: >*>*>*[*<]10. Evaluate `<` and move to next instruction v v
Tape: 01100000 Instructions: >*>*>*[*<]11. Evaluate `]` and move to matching `[` v v
Tape: 01100000 Instructions: >*>*>*[*<]12. Evaluate `[`. Since the current bit is not `0`, move to next instruction v v
Tape: 01100000 Instructions: >*>*>*[*<]13. Evaluate `*` and move to next instruction v v
Tape: 01000000 Instructions: >*>*>*[*<]14. Evaluate `<` and move to next instruction v v
Tape: 01000000 Instructions: >*>*>*[*<]15. Evaluate `]` and move to matching `[` v v
Tape: 01000000 Instructions: >*>*>*[*<]16. Evaluate `[`. Since the current bit is not `0`, move to next instruction v v
Tape: 01000000 Instructions: >*>*>*[*<]17. Evaluate `*` and move to next instruction v v
Tape: 00000000 Instructions: >*>*>*[*<]18. Evaluate `<` and move to next instruction v v
Tape: 00000000 Instructions: >*>*>*[*<]19. Evaluate `]` and move to matching `[` v v
Tape: 00000000 Instructions: >*>*>*[*<]20. Evaluate `[`. Since the current bit is `0`, move to next instruction after matching `]` v v
Tape: 00000000 Instructions: >*>*>*[*<]
After twenty steps our program has consumed every instruction (indicated by the instruction pointer trying to look at a non-existent instruction) and halts. Halting, however, is not a requirement for Turing completeness, and we can use the same step-by-step technique to show that our third program (*[]) never will.
Smallfuck Interpreter
Preliminaries
Before we begin implementing the guts of the interpreter, it would serve us well to reflect on the evaluation above and get an idea of what we are trying to build.
We can see that to properly evaluate a Smallfuck program we need to keep track of four pieces of information:
- The state of the tape
- Which bit on the tape is currently in scope
- The instruction set
- Which instruction is currently being executed
We can use tuples quite naturally to represent the tape and the instructions. This allows us to represent the pointers to the current bit and instruction as numbers.
Get Ryan Dabler’s stories in your inbox
Join Medium for free to get updates from this writer.
With these four pieces of information comprising our execution state, our main task is to implement each of the five actions listed above. However, none of these actions can be implemented as is without having some utility operations to build upon. So we will first put in place these prerequisites and build upon them to construct the core interpreter. These are the preliminary actions we will need to support:
- incrementing a number (one time or until a termination condition is met)
- decrementing a number (one time or until a termination condition is met)
- slicing an array
- flipping a bit (both in general but also at a particular location on the tape)
Incrementing/decrementing numbers is very similar to what we covered in my prior article on implementing arithmetic and so we will put them here without much explanation.
type ArrayFromNumber<
N extends number,
A extends any[] = []
> = A['length'] extends N ? A : ArrayFromNumber<N, [...A, any]>;type Increment<T extends number> =
[...ArrayFromNumber<T>, any]['length'];type Decrement<T extends number> =
ArrayFromNumber<T> extends [...(infer U), any]
? U['length']
: never;
This takes care of the simple case of doing a known number of increment/decrement operations but not the case of an arbitrary amount. After all there is no way to tell how many characters a ] is ahead of its matching [ without simply scanning each character in between. So we will write a generic rewind and fast forward operation.
type Rewind<
Arr extends any[],
I extends number
> = Arr[I] extends '[' ? I : Rewind<Arr, Decrement<I>>;type FastForward<
Arr extends any[],
I extends number
> = Arr[I] extends ']'
? Increment<I>
: Increment<I> extends number
? FastForward<Arr, Increment<I>>
: never;
These two types take an array (which will be our instruction set) and an index pointing to our current instruction in that array. What will then happen is we will ask if whatever instruction is at Arr[I] equals the termination character and if so, we return the index number. If not, we move our index one position and try again.
Note that FastForward gives a number that is one past the position of the character it terminated on. So if it advanced the program [***]>* from position 1 (=[) to 5 (=]) it will return position 6 (=>). This is because if we were given position 5, the next execution of our interpreter would rewind us back to the opening bracket, and we would infinitely loop between the two rather than break out of the loop as was intended.
These two types are not strong enough for our needs, though. A Smallfuck program could have nested loops (such as *[>*[>*]>*]*) and if we use what we just built to advance from the first [ to its matching ] , we will advance to the first occurrence of ] and not the matching occurrence. So we will advance from our start of position 2 to 8 rather than 11. This means we need to augment our Rewind and FastForward types to handle depth.
type Rewind<
Arr extends any[],
I extends number,
Depth extends number = 0
> = Arr[I] extends '['
? Depth extends 0
? I
: Rewind<Arr, Decrement<I>, Decrement<Depth>>
: Arr[I] extends ']'
? Increment<Depth> extends number
? Rewind<Arr, Decrement<I>, Increment<Depth>>
: never
: Rewind<Arr, Decrement<I>, Depth>;type FastForward<
Arr extends any[],
I extends number,
Depth extends number = 0
> = Arr[I] extends ']'
? Depth extends 0
? Increment<I>
: Increment<I> extends number
? FastForward<Arr, Increment<I>, Decrement<Depth>>
: never
: Arr[I] extends '['
? Increment<Depth> extends number
? Increment<I> extends number
? FastForward<Arr, Increment<I>, Increment<Depth>>
: never
: never
: Increment<I> extends number
? FastForward<Arr, Increment<I>, Depth>
: never;
Accounting for depth, we can see, exploded the complexity of our operations. The general gist, though, is this: when progressing through the array of commands, we are looking for a particular symbol to terminate on. If we see that symbol, we must make sure we are a depth of 0 (which indicates that this symbol is the appropriate matching symbol). If we are not at depth 0, we keep moving, but we subtract 1 from our depth. If all the brackets are properly balanced we will eventually be at depth 0 when we come across a terminating symbol. If, however, we come across the terminating symbol’s opposite we are entering a nested loop and so we need to increase our depth by 1 so as not to prematurely stop when we come across the terminating symbol that closes this nested loop.
Because TypeScript does not have an assignment operation in its type system, we cannot do something like Arr[I] = SomeType. If we want to change a type at some index I of an array we need to create a brand new array with all the contents to the left of I unchanged, the Ith position updated, and then all contents to the right of I unchanged. This restriction makes for a verbose way of modifying an array type, but with a Slice utility we can make it elegant.
type Slice<
T extends any[],
S extends number = 0,
E extends number = T['length'],
A extends any[] = []
> = S extends E
? A
: Increment<S> extends number
? Slice<T, Increment<S>, E, [...A, T[S]]>
: never;Slice takes for parameters the original array T, a start index S, an end index E, and an accumulating array A. Slice will then check to see if our start index is equal to our end index and return the accumulated array if so. Otherwise, it increments our start position, adds the item at T[S] to our accumulator array, and recursively checks again using those updated values.
One of the simplest actions we have to do is flipping a bit.
type FlipBit<B extends Bit> = B extends 0 ? 1 : 0;So to flip a bit at any position in our tape we simply need to utilize our Slice operation above the get
type FlipBitAtPos<T extends Tape, P extends number> =
Increment<P> extends number
? [
...Slice<T, 0, P>,
FlipBit<T[P]>,
...Slice<T, Increment<P>>
]
: never;Writing the Interpreter
Now it is time to begin establishing the pieces that do the heavy lifting.
There are a couple types that will serve as necessary building blocks for the interpreter:
type Command = '>' | '<' | '*' | '[' | ']'
type Bit = 0 | 1;
type Tape = Bit[];The way we will design the interpreter is we want it to receive an array of Commands which we want to execute on a given tape of 0s. Each step of the evaluation will manipulate the tape (or our position on it) as well as move our pointer to the next command to execute. The result of each evaluation will be the combined state of our commands and tape, and we will recursively call our evaluator on this result until we get to a point where the evaluation necessarily stops.
So our last building block will be
type ExecutionState = [
commands: Command[],
commandPosition: number,
tape: Tape,
tapePosition: number
];type GetCommands<T extends [any, ...any[]]> = T[0];
type GetCommandPtr<T extends [any, any, ...any[]]> = T[1];
type GetTape<T extends [any, any, any, ...any[]]> = T[2];
type GetTapePtr<T extends [any, any, any, any, ...any[]]> = T[3];
Because ExecutionState is a 4-tuple, we also have some convenience getters to extract specific pieces of that tuple.
Using these, let’s build the interpreter, starting at the user-facing entry point and working backward into the mechanisms that do the evaluation.
type Smallfuck<
CS extends Command[],
T extends Tape
> = Evaluate<[CS, 0, T, 0]>;Smallfuck will take a list of commands to evaluate and a fixed-length tape and then build an initial ExecutionState to pass into Evaluate.
Evaluate itself will act as our program runner. It will take the current state of the program, execute it, take the result of that execution, and do it again ad infinitum until the last instruction has been executed. Evaluate will look like
type Evaluate<S extends ExecutionState> =
GetCommands<S>[GetCommandPtr<S>] extends undefined
? S
: Execute<
GetCommands<S>,
GetCommandPtr<S>,
GetTape<S>,
GetTapePtr<S>
> extends ExecutionState
? Evaluate<
Execute<
GetCommands<S>,
GetCommandPtr<S>,
GetTape<S>,
GetTapePtr<S>
>
>
: never;Our base case for the recursive type is when our index for the command to execute is outside the bounds of the list of commands. This represents the situation our interpreter is in in step #20 above where it is trying to read a command that simply does not exist.
Because our Execute type is fairly complex, TypeScript cannot properly infer that its return type is an ExecutionState type, so we must add the extends ExecutionState check for the same reason we have to sometimes do the extends number check discussed at the beginning of this article.
Our Execute type will do the main work of making the appropriate mutations to our ExecutionState based on each command. Essentially what it will do is take the current command and funnel it through a series of case statements that make the appropriate change to our execution state and return the updated version.
The manipulations required for the commands *, <, > and ] are all fairly straightforward, so we will list a partial Execute type and then discuss the special treatment for the [ command.
type Execute<
CS extends Command[],
CPos extends number,
T extends Tape,
TPos extends number
> =
CS[CPos] extends '*'
? [CS, Increment<CPos>, FlipBitAtPos<T, TPos>, TPos]
:
CS[CPos] extends '>'
? [CS, Increment<CPos>, T, Increment<TPos>]
:
CS[CPos] extends '<'
? [CS, Increment<CPos>, T, Decrement<TPos>]
:
CS[CPos] extends ']'
? [CS, Rewind<CS, Decrement<CPos>>, T, TPos]
:
never;Every time we see a command, we will always have to increment our command pointer to the next command. The other manipulations simply perform the straightforward action of flipping a bit at a point on our tape, incrementing/decrementing the pointer for our tape, or going back through our command list to find the matching [ command.
However, our implementation of > and < are incomplete. Remember that because our tape is finite it is possible to try to go beyond its bounds. Under such circumstances our program should halt. We need to augment these two commands with a check to see if we are about to go out of bounds and, if so, immediately move our command pointer to be out of bounds without changing anything about the tape. This will trigger the Evaluate type to abort any more executions.
type Execute<
CS extends Command[],
CPos extends number,
T extends Tape,
TPos extends number
> =
CS[CPos] extends '*'
? [CS, Increment<CPos>, FlipBitAtPos<T, TPos>, TPos]
:
CS[CPos] extends '>'
? TPos extends Decrement<T['length']>
? [CS, CS['length'], T, TPos]
: [CS, Increment<CPos>, T, Increment<TPos>]
:
CS[CPos] extends '<'
? TPos extends 0
? [CS, CS['length'], T, TPos]
: [CS, Increment<CPos>, T, Decrement<TPos>]
:
CS[CPos] extends ']'
? [CS, Rewind<CS, Decrement<CPos>>, T, TPos]
:
never;The final command (our [ instruction) is a conditional fast forward. So we have to implement the logic to determine whether the interpreter jumps all the way to the matching ] command or simply goes to the next one. We will call this our MaybeFastForward type.
type MaybeFastForward<
CS extends Command[],
CPos extends number,
T extends Tape,
P extends number
> = T[P] extends 0 ? FastForward<CS, CPos> : CPos;If our current bit is 0 we do not enter the loop so need to advance past our matching ]. Otherwise we do enter the loop and go to the first command in that loop. Note that we simply return CPos in the event that we enter the loop rather than increment it. We will see why below.
Our final Execute type will be
type Execute<
CS extends Command[],
CPos extends number,
T extends Tape,
TPos extends number
> =
CS[CPos] extends '*'
? [CS, Increment<CPos>, FlipBitAtPos<T, TPos>, TPos]
:
CS[CPos] extends '>'
? TPos extends Decrement<T['length']>
? [CS, CS['length'], T, TPos]
: [CS, Increment<CPos>, T, Increment<TPos>]
:
CS[CPos] extends '<'
? TPos extends 0
? [CS, CS['length'], T, TPos]
: [CS, Increment<CPos>, T, Decrement<TPos>]
:
CS[CPos] extends ']'
? [CS, Rewind<CS, Decrement<CPos>>, T, TPos]
:
CS[CPos] extends '['
? Increment<CPos> extends number
? [
CS,
MaybeFastForward<CS, Increment<CPos>, T, TPos>,
T,
TPos
]
: never
: never;We can see in our implementation of [ that we increment CPos already when we pass it into MaybeFastForward (and hence we we return it unchanged from that action). This is because of how we track depth; if we start our fast forwarding starting on the same command we just executed (viz. [) we would immediately add a level of depth to our routine. This will cause the fast forward operation to jump beyond the actual matching bracket ] it should be looking for.
Testing the Interpreter
Unfortunately it is impossible to see the step by step actions TypeScript takes when evaluating a program, but we can at least compare the output of our interpreter’s tape to that of another interpreter. We will use the programs we listed above and either compare the final state of the tape (for those that terminate) or determine if both produce some kind of error/infinite loop (for those that would not terminate).
The outside interpreter we will use as a comparison will be this one (interestingly written in TypeScript — just not purely within its own type system). It exposes a function called interpreter which takes a string of commands as well as a string of zeros for the initial tape. While our interpreter returns the entire execution context we can easily grab out the tape for evaluation by wrapping each Smallfuck call with a GetTape<...> call.
/**
* Evaluate '*>*>*' on tape 000000
*/
type Test1 = GetTape<
Smallfuck<
['*', '>', '*', '>', '*'],
[0, 0, 0, 0, 0, 0]
>
>; // [1, 1, 1, 0, 0, 0]const test1 = interpreter('*>*>*', '000000'); // '111000'/**
* Evaluate '*[]' on tape 000000
*/
type Test2 = GetTape<
Smallfuck<
['*', '[', ']'],
[0, 0, 0, 0, 0, 0]
>
>; // Type instantiation is excessively deep and possibly infinite.const test2 = interpreter('*[]', '000000'); // Environment hangs/**
* Evaluate '*[>*]' on tape 000000
*/
type Test3 = GetTape<
Smallfuck<
['*', '[', '>', '*', ']'],
[0, 0, 0, 0, 0, 0]
>
>; // [1, 1, 1, 1, 1, 1]const test3 = interpreter('*[>*]', '000000'); // '111111'/**
* Evaluate '>*>*>*[*<]' on tape 000000
*/
type Test4 = GetTape<
Smallfuck<
['>', '*', '>', '*', '>', '*', '[', '*', '<', ']'],
[0, 0, 0, 0, 0, 0]
>
>; // [0, 0, 0, 0, 0, 0]const test4 = interpreter('>*>*>*[*<]', '000000'); // '000000'/**
* Evaluate '*[>>*[<*]]' on tape 000000
*/
type Test5 = GetTape<
Smallfuck<
['*', '[', '>', '>', '*', '[', '<', '*', ']', ']'],
[0, 0, 0, 0, 0, 0]
>
>; // [0, 1, 1, 0, 0, 0]const test5 = interpreter('*[>>*[<*]]', '000000'); // '011000'
Remarks
We can see that for the sample programs above, our interpreter’s output matches that of another. While that is a far cry from proving the two will always give the same output it gives us some validation that we have written our interpreter properly. Fortunately Smallfuck is a simple language so if we can get it working for a handful of programs illustrating the major features of the language it is unlikely we would find a more complex case that breaks the interpreter.
Our actual implementation of Smallfuck, being entirely in the type system of TypeScript, means we can never be sure that any Type instantiation is excessively deep and possibly infinite. error indicates an infinitely looping program. Since recursive types have performance concerns for the type checker, TypeScript has a strict recursion limit preventing extraordinarily recursive types from being evaluated. In our situation that means both actually infinite programs and programs of sufficient complexity will both end up being terminated once the recursive limit is reached.
This article started with the question of whether TypeScript had a Turing complete type system. We have shown through our implementation of a Smallfuck interpreter that the answer is yes, although with a few qualifications.
For starters TypeScript has a recursion limit such that we can never evaluate complex programs. Furthermore, even without this limit, TypeScript has the same limitations as any other programming language which are not present in Turing machines (viz. finite memory and a physical lifespan making it impossible to execute a program whose time would take a million years to complete). However, these limitations are implementation limitations and are not inherent in the logic of our interpreter, so if we could lift them we would have a bona fide Turing complete type system.
An interesting feature of our proof that TypeScript can compute anything is that its computational framework looks nothing like the arithmetical system we implemented in a prior article (which performed more “functional” computations we are used to seeing). This is due to the fact that “computation” really denotes an abstract term and there are many different concrete ways to compute the same thing. Our interpreter takes one of those concrete approaches (in our case something akin to a Turing machine) and gives it flesh; had we decided to implement recursive functions or the lambda calculus it would have looked different yet.
This is also not the only attempt to prove Turing completeness in TypeScript. There was an earlier attempt years ago to show that. Our proof looks nothing like that one since we utilize recent features of TypeScript in our proof that were not available five years ago.
Here is a link to the TypeScript playground with the interpreter fully implemented as well as a Gist of the same code.
