Smallfuck interpreter built using TypeScript's type system for this article: https://itnext.io/typescript-and-turing-completeness-ba8ded8f3de3

Smallfuck.ts

//
// ------- General utilities ---
//
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;

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;

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;

type FlipBit<B extends Bit> = B extends 0 ? 1 : 0;

type FlipBitAtPos<T extends Tape, P extends number> = Increment<P> extends number
    ? [...Slice<T, 0, P>, FlipBit<T[P]>, ...Slice<T, Increment<P>>]
    : never;

//
// ------- Smallfuck utilities ---
//
type Command = '>' | '<' | '*' | '[' | ']'
type Bit = 0 | 1;
type Tape = Bit[];
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];

type MaybeFastForward<
    CS extends Command[],
    CPos extends number,
    T extends Tape,
    P extends number
> = T[P] extends 0 ? FastForward<CS, CPos> : CPos;

//
// ------- Smallfuck interpreter ---
//
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;

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;

type Smallfuck<CS extends Command[], T extends Tape> = Evaluate<[CS, 0, T, 0]>;

//
// ------- Tests ---
//

 // '*>*>*'
type Test1 = Smallfuck<['*', '>', '*', '>', '*'], [0, 0, 0, 0, 0, 0]>;

// '*[]'
type Test2 = Smallfuck<['*', '[', ']'], [0, 0, 0, 0, 0, 0]>; // Type instantiation is excessively deep and possibly infinite.

//  '*[>*]'
type Test3 = Smallfuck<['*', '[', '>', '*', ']'], [0, 0, 0, 0, 0, 0]>;

// '>*>*>*[*<]'
type Test4 = Smallfuck<['>', '*', '>', '*', '>', '*', '[', '*', '<', ']'], [0, 0, 0, 0, 0, 0]>;

// '*[>>*[<*]]'
type Test5 = Smallfuck<['*', '[', '>', '>', '*', '[', '<', '*', ']', ']'], [0, 0, 0, 0, 0, 0]>;

Thanks for the great blog post. The SomeGeneric<...> extends number ? ... : never construct is interesting. I agree that it's unfortunate that it's needed in the first place, but I think we could make this quite a bit cleaner by defining a AsNumber<T> generic, which acts as a type assertion. Like this:

type AsNumber<T> = T extends number ? T : never;

type _Increment<T extends number> = [...ArrayFromNumber<T>, any]['length'];
type _Decrement<T extends number> = ArrayFromNumber<T> extends [...(infer U), any] ? U['length'] : never;

type Increment<T extends number> = AsNumber<_Increment<T>>;
type Decrement<T extends number> = AsNumber<_Decrement<T>>;

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 ']'
        ? Rewind<Arr, Decrement<I>, Increment<Depth>>
        : 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>
        : FastForward<Arr, Increment<I>, Decrement<Depth>>
    : Arr[I] extends '['
        ? FastForward<Arr, Increment<I>, Increment<Depth>>
        : FastForward<Arr, Increment<I>, Depth>;

...

Additionally, I think that using unknown instead of any throughout the code would be cleaner.