How to Prove JavaScript and TypeScript Are Turing‑Complete Using Partial Recursive Functions

How to Prove

Turing‑completeness and the ability to implement partial recursive functions are equivalent. The definition of partial recursive functions can be followed through a series of videos, which provide a clear and simple explanation.

Partial Recursive Functions 1: What's a function?

Partial Recursive Functions 2: The basic functions

Partial Recursive Functions 3: Composition

Partial Recursive Functions 4: Primitive Recursion

Partial Recursive Functions 5: Minimisation

Since the videos are hosted on YouTube, interested readers can search for them themselves.

Because Turing‑completeness and implementing partial recursive functions are equivalent, we can prove a language is Turing‑complete by showing it can implement partial recursive functions. An interesting theorem states that any partial recursive function can be obtained from a primitive recursive function by a single minimisation step; therefore, when writing programs, encountering more than two nested infinite loops should raise suspicion of a logical error.

Definition of Partial Recursive Functions

In this field there are three basic functions—zero, successor, and projection—and three basic operations—composition, primitive recursion, and minimisation. All computable problems can be expressed by combining these basic functions and operations. Functions obtained by primitive recursion are called primitive recursive functions; applying minimisation to a primitive recursive function yields a partial recursive function.

Basic Functions

Zero Function

The zero function with any number of arguments always returns 0.

Intuitive Memory

It can be understood as setting the content at a memory address to 0.

Successor Function

The successor function adds 1 to its argument, effectively implementing a simple adder.

Intuitive Memory

It can be understood as incrementing the value stored at a memory address.

Projection Function

The projection function with n arguments returns the i ‑th argument.

Intuitive Memory

It can be understood as reading the value at a specific memory address.

Basic Operations

Composition

Given functions h and f₁,…,fₖ, the composition produces a new function that applies each fᵢ to the arguments and then applies h to the results.

Intuitive Memory

It corresponds to function calls or function composition.

Primitive Recursion

Given a base function g and a step function h, primitive recursion defines a new function that uses g for the base case (usually when the first argument is 0) and h to compute the next value from the previous one.

Intuitive Memory

It supports recursion.

Minimisation

Given a function f, minimisation searches for the smallest non‑negative integer i such that f(i, …) = 0. The resulting function is called a partial recursive function.

Intuitive Memory

It can be used to implement a while‑loop.

Role of Partial Recursive Functions

Any computable problem can be expressed by combining the basic functions and operations. Examples include:

Addition

Addition can be defined using primitive recursion with the zero function as the base case and the successor function as the recursive step.

Predecessor Function

The predecessor function can also be expressed via primitive recursion.

Subtraction

Subtraction is obtained by primitive recursion using the predecessor function.

Zero Test (isZero)

The zero‑test function can be defined by primitive recursion using the zero function and composition with the successor.

Less‑Than-or‑Equal (isLessEqualThan)

It can be built by composing the zero‑test with subtraction.

Multiplication

Multiplication is defined by primitive recursion that repeatedly adds the first argument.

Division

Division can be implemented by minimisation of a function that checks whether (i+1)·b ≤ a.

JS Is Turing‑Complete

Below is a JavaScript implementation of the basic functions, composition, primitive recursion, and minimisation, followed by concrete definitions of addition, subtraction, zero‑test, less‑than, multiplication, and division.

// basic functions
// zero function
function zero(...args) { return 0; }
// successor function
function succ(n) { return n + 1; }
// projection function
function getProjFunc(n) { return (...args) => args[n]; }
const projN1 = getProjFunc(1);
// basic operations
// composition
function compose(h, ...funcs) {
  return function (...args) {
    return h(...funcs.map(f => f(...args)));
  };
}
// primitive recursion
function primitiveRecursion(g, h) {
  return function __primitiveRecursion(n, ...args) {
    if (0 === n) {
      let resp = g(...args);
      return resp;
    }
    let last = __primitiveRecursion(n - 1, ...args);
    let resp = h(n - 1, last, ...args);
    return resp;
  };
}
// minimisation
function getMinimizationFunction(f) {
  return function (...args) {
    let i = 0;
    while (i < Number.POSITIVE_INFINITY) {
      if (f(i, ...args) === 0) {
        return i;
      }
      i++;
    }
    return undefined;
  };
}
// addition
const add = primitiveRecursion(getProjFunc(0), compose(succ, getProjFunc(1)));
const pred = primitiveRecursion(zero, getProjFunc(0));
const sub = primitiveRecursion(getProjFunc(0), compose(pred, getProjFunc(1)));
const isZero = primitiveRecursion(
  zero,
  compose(succ, compose(zero, getProjFunc(0)))
);
const isLessThan = compose(isZero, sub);
const mul = primitiveRecursion(
  zero,
  compose(add, getProjFunc(1), getProjFunc(2))
);
const div = getMinimizationFunction(
  compose(
    isLessThan,
    compose(mul, compose(succ, getProjFunc(0)), getProjFunc(2)),
    getProjFunc(1)
  )
);
console.log(add(3, 4)); // 7
console.log(pred(1), pred(2), pred(0)); // 0, 1, 0
console.log(sub(1, 3), sub(2, 3), sub(3, 3), sub(4, 3)); // 2, 1, 0, 0
console.log(isZero(0), isZero(3)); // 0, 1
console.log(isLessThan(3, 4), isLessThan(4, 3), isLessThan(4, 2)); // 1, 0, 0
console.log(mul(3, 4)); // 12
console.log(div(6, 4)); // 1

TS Type‑Level Programming Is Turing‑Complete

The same construction can be expressed at the type level in TypeScript, using conditional types and recursive type definitions to model zero, successor, projection, composition, primitive recursion, and minimisation.

// basic functions
// zero function
type Zero<A, B, C, D, E, F, G> = 0;
// successor function (type‑level)
type IntSeq<N, S extends any[] = []> = S["length"] extends N ? S : IntSeq<N, [...S, S["length"]]>;
type Succ<N> = [...IntSeq<N>, 1]["length"];
// projection function
type Proj31<A, B, C> = A;
// basic operations
// composition (placeholder example)
type H<A, B, C> = 0;
type G<A, B, C> = 0;
type ComposedType<A, B, C> = H<G<A, B, C>, G<A, B, C>, G<A, B, C>>;
// primitive recursion (using type recursion)
type Pop<T extends any[]> = T extends [...(infer I), infer _] ? I : never;
type Pred<N> = Pop<[...IntSeq<N>]>["length"];
type PG<A, B, C> = 0;
type HG<N, Y, A, B, C> = 0;
type PrimitiveFunc<N, A, B, C> = N extends 0 ? PG<A, B, C> : HG<N, PrimitiveFunc<Pred<N>, A, B, C>, A, B, C>;
// minimisation
type MF<A, B, C, I> = 0;
type Minimize<A, B, C, I> = MF<A, B, C, I> extends 0 ? I : Minimize<A, B, C, Succ<I>>;
type Minimized<A, B, C> = Minimize<A, B, C, 0>;
// addition example
type Proj11<A> = A;
type Proj32<A, B, C> = B;
type SuccComposedProj<A, B, C> = Succ<Proj32<A, B, C>>;
type Add<X, Y> = Y extends 0 ? Proj11<X> : SuccComposedProj<X, Add<X, Pred<Y>>, Y>;
type R = Add<3, 4>; // 7

References

Partial recursive functions equivalence: https://ncatlab.org/nlab/show/partial+recursive+function

Partial Recursive Functions 1: What's a function? – https://www.youtube.com/watch?v=yaDQrOUK-KY

Partial Recursive Functions 2: The basic functions – https://www.youtube.com/watch?v=_cswfIQg0Ss

Partial Recursive Functions 3: Composition – https://www.youtube.com/watch?v=twHp7IrPJEs

Partial Recursive Functions 4: Primitive Recursion – https://www.youtube.com/watch?v=cjq0X-vfvYY

Partial Recursive Functions 5: Minimisation – https://www.youtube.com/watch?v=bFkU-qV2Ioo