Re:TypeScripts Type System Is Turing Complete
by icebraining on Wednesday August 02, 2017 @03:49AM
(#14908688)
It's not impossible, the error message will just be "timeout".
[ Parent
| on HN ]
Re:TypeScripts Type System Is Turing Complete
by klodolph on Wednesday August 02, 2017 @11:31AM
(#14911329)
That's redefining the problem—if you add a timeout, you are explicitly making the language not Turing complete any more.
Re:TypeScripts Type System Is Turing Complete
by icebraining on Wednesday August 02, 2017 @11:38AM
(#14911398)
The language still is, just not the environment in which it runs. Much like a language can be Turing-complete without having infinite tape/memory to run on.
Re:TypeScripts Type System Is Turing Complete
by klodolph on Wednesday August 02, 2017 @07:33PM
(#14915636)
When people say "Turing-complete" it's usually assumed that we are talking about computational models which could emulate Turing machines given infinite memory. But we don't have infinite memory.
Adding time limits radically changes things.
Re:TypeScripts Type System Is Turing Complete
by chongli on Wednesday August 02, 2017 @04:28AM
(#14908865)
Then you get valid programs timing out when they would have compiled otherwise.
Re:TypeScripts Type System Is Turing Complete
by cestith on Wednesday August 02, 2017 @02:40PM
(#14913384)
Even if it's technically valid it's not likely to be a useful program if it has an unhalting loop in its data type declarations and enforcement.
Re:TypeScripts Type System Is Turing Complete
by chongli on Wednesday August 02, 2017 @02:43PM
(#14913413)
It doesn't have to loop forever, it could just take a few minutes to calculate. There are plenty of useful, real-world projects that take hours to compile (see: any large project in C++). To reject these programs due to an arbitrary timeout is a non-starter.