5 ms·

> you can write a valid TypeScript program that will never finish compiling Sure, typescript program may never finish compiling, although it will still halt:

• naasking 9y ago
  > 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.
  • amelius 9y ago
    Yes, but you want your tools to be powerful at the same time.
    • naasking 9y ago
      There's plenty of power below Turing completeness. Turing completeness is overrated.
      • amelius 9y ago
        That's an opinion, of course.
        • naasking 9y ago
          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.
  • k__ 9y ago
    Isn't that irrelevant in that case? If the type checker takes too long, sonething isn't right.
    • naasking 9y ago
      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.
      • k__ 9y ago
        But if you got a deadline, everything over it is bad.
        • naasking 9y ago
          Sure, but "not fast enough for me because X" and simply "wrong/incorrect" are completely different claims.
  • flashmob 9y ago
    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...
    • naasking 9y ago
      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.
      • flashmob 9y ago
        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?
• JD557 9y ago
  >CSS + HTML AFAIK, CSS + HTML is not Turing complete, but CSS + HTML + "Human pumping tab and space" is, which makes infinite loops less of a problem.
  • flashmob 9y ago
    Aha! I had a look to confirm, and you are right! In essence, html + css is not. However if we have a human hitting tabs and spaces for a long enough time, then for all intents and purposes, perhaps it is? Anyhow, it's still very impressive that we can do a lot of complex computations simply by hitting tabs and spaces!