Cyclic Tag System implementation in TypeScript type-level function

CTS.ts

type Step<Input extends string, Program extends string[]> =
  Program extends [infer ProgramHead extends string, ...infer ProgramTail]
    ? Input extends `0${infer Rest}`
      ? [Rest, [...ProgramTail, ProgramHead]]
      : Input extends `1${infer Rest}`
        ? [`${Rest}${ProgramHead}`, [...ProgramTail, ProgramHead]]
        : [Input, Program]
    : [Input, []];

type StepN<Input extends string, Program extends string[], N extends number, Counter extends 0[] = []> =
  Counter['length'] extends N
    ? Input
    : Step<Input, Program> extends [infer NextInput extends string, infer NextProgram extends string[]]
      ? StepN<NextInput, NextProgram, N, [0, ...Counter]>
      : never;

type CTS<Input extends string, Program extends string[]> = StepN<Input, Program, -1>;