TypeScripts Type System is Turing Complete

This is not really a bug report and I certainly don't want TypeScripts type system being restricted due to this issue. However, I noticed that the type system in its current form (version 2.2) is turing complete. Turing completeness is being achieved by combining mapped types, recursive type definitions, accessing member types through index types and the fact that one can create types of arbitrary size. In particular, the following device enables turing completeness: ```typescript type MyFunc<TArg> = { "true": TrueExpr<MyFunction, TArg>, "false": FalseExpr<MyFunc, TArg> }[Test<MyFunc, TArg>]; ``` with `TrueExpr`, `FalseExpr` and `Test` being suitable types. Even though I didn't formally prove (edit: in the meantime, I did - see below) that the mentioned device makes TypeScript turing complete, it should be obvious by looking at the following code example that tests whether a given type represents a prime number: ```typescript type StringBool = "true"|"false"; interface AnyNumber { prev?: any, isZero: StringBool }; interface PositiveNumber { prev: any, isZero: "false" }; type IsZero<TNumber extends AnyNumber> = TNumber["isZero"]; type Next<TNumber extends AnyNumber> = { prev: TNumber, isZero: "false" }; type Prev<TNumber extends PositiveNumber> = TNumber["prev"]; type Add<T1 extends AnyNumber, T2> = { "true": T2, "false": Next<Add<Prev<T1>, T2>> }[IsZero<T1>]; // Computes T1 * T2 type Mult<T1 extends AnyNumber, T2 extends AnyNumber> = MultAcc<T1, T2, _0>; type Mult

Posted by hediet on Mar 24, 2017, 3:14 AM

Tags

• github (Other)

Related issues

• struct's lifetime requirements can be bypassed via covariant field assignment
• Proposal to Reorganize the Moderation Team and Review Moderation Policies
• Progressive FPS degradation appears to be related to dota2.com — blocking the domain prevents the performance loss
• proposal: container/...: generic collection types
• Better Custom Endpoint BYOK
• A concrete policy for backward compatibility until Godot 5.0