News for hackers. Stuff that matters.
Re:TypeScripts Type System Is Turing Complete by naasking on Wednesday August 02, 2017 @04:09AM (#14908790)
> Sure, typescript program may never finish compiling, although it will still halt: Just `kill -9`. The halting problem solved! ;-)

The problem is that you can't really tell when a long compile is an infinite or just a really long one. You want non-Turing completeness because your tools need to be reliable.

Re:TypeScripts Type System Is Turing Complete by flashmob on Wednesday August 02, 2017 @07:04AM (#14909559)
Turing complete means that it's a simulation of a Turing machine, but not actually one. A TM is something purely abstract that was invented to prove the halting problem, and infinity of the tape is arguably the most crucial concept. Computers do not have infinite memory / power / time so the halting problem doesn't really make sense unless you talk about a pure Turing machine with infinite tape.

In most cases, you know something is wrong once your typescript compilation takes more than a few seconds. At most, it could be an interesting DOS attack, but most continuous integration systems should have a limit on how much seconds they can run the compiler for. So it's really not a problem if you have constraints on resources...

Re:TypeScripts Type System Is Turing Complete by naasking on Thursday August 03, 2017 @10:33AM (#14919907)
Except you know no such thing, that's the point. That could very well be the intended and correct behaviour of the compiler for that input.
Re:TypeScripts Type System Is Turing Complete by flashmob on Saturday August 05, 2017 @08:00PM (#14938771)
Sure, I can see your point. It's a problem for computer scientists, and good to know as an anecdote. I'm talking about it in practice - when using TypeScript the 'halting problem' has never been an issue. I was joking about the 'kill -9' but also meant it in a half-hearted way!

So, if not turing complete, what kind of automata would you use to accept your language, say if you were designing your own language?

Re:TypeScripts Type System Is Turing Complete by k__ on Wednesday August 02, 2017 @05:39AM (#14909201)
Isn't that irrelevant in that case?

If the type checker takes too long, sonething isn't right.

Re:TypeScripts Type System Is Turing Complete by naasking on Wednesday August 02, 2017 @06:52AM (#14909504)
How could you possibly quantify "too long" when you can perform arbitrary computation at compile-time? How do you know the library you're using doesn't need you to compute and embed the first N primes in the final output?

At least if your type checker weren't Turing complete, you know it will finish at some point.

Re:TypeScripts Type System Is Turing Complete by k__ on Wednesday August 02, 2017 @08:23AM (#14909912)
But if you got a deadline, everything over it is bad.
Re:TypeScripts Type System Is Turing Complete by naasking on Friday August 04, 2017 @04:14AM (#14927180)
Sure, but "not fast enough for me because X" and simply "wrong/incorrect" are completely different claims.
Re:TypeScripts Type System Is Turing Complete by amelius on Wednesday August 02, 2017 @05:23AM (#14909122)
Yes, but you want your tools to be powerful at the same time.
Re:TypeScripts Type System Is Turing Complete by naasking on Wednesday August 02, 2017 @05:33AM (#14909166)
There's plenty of power below Turing completeness. Turing completeness is overrated.
Re:TypeScripts Type System Is Turing Complete by amelius on Wednesday August 02, 2017 @05:43AM (#14909230)
That's an opinion, of course.
Re:TypeScripts Type System Is Turing Complete by naasking on Wednesday August 02, 2017 @06:58AM (#14909533)
What's not an opinion is that most programs we write are more easily and compactly expressed with general recursion, but often don't need general recursion to reproduce the same output.

Seems like a non-opinionated classification of "overrated".

Or we could go even more meta, since no physical system is Turing complete due to the Bekenstein bound, so any expressible system is necessarily at most an FSA.