6 ms·
> specifying a maximum recursion depth or something similar Doesn't TS do exactly this? It doesn't seem like setting a cap on recursion depth would disqualify
by RussianCow 3y ago
> specifying a maximum recursion depth or something similar
Doesn't TS do exactly this? It doesn't seem like setting a cap on recursion depth would disqualify something from being Turing complete. Or am I misunderstanding your comment?
- explaininjs 3y agoWhen recursion is the only method of iteration, of course it would.
- smacke 3y agoIs the recursion limit an implementation detail of the compiler though, or something statically built into the language? If the former there's nothing to prevent the language itself from being Turing complete. (Similar to how every Turing complete programming language today runs on something technically weaker than a Turing machine due to finite memory.)
- explaininjs 3y agoThere’s no spec so the compiler is the language.
- olalonde 3y agoWhat is the other method of iteration? Also, TypeScript does have a recursion limit[0]. [0] https://herringtondarkholme.github.io/2023/04/30/typescript-magic/ https://herringtondarkholme.github.io/2023/04/30/typescript-...
- CSMastermind 3y agoDo you mean within a state machine or in practice? Iteration (loops) are typically represented as jump or branch instructions while recursion requires the creation of a new stack frame on the call stack.
- olalonde 3y agoNo, in TypeScript's type system. As far as I know, recursion is the only method of iteration but the comment I was replying to seemed to imply otherwise.
- explaininjs 3y agoThe comment does not imply otherwise
- olalonde 3y agoI thought you did because of the "would". So you're saying that TypeScript is not Turing complete?
- deleted 3y ago[deleted]
- explaininjs 3y agoNothing is Turing complete. But it is the stronger form of incomplete where even on a machine with truly unlimited memory it’d still be unable to model some (almost all, formally) executions.