Hypothesis: if you can write a compiler in a given programming language, then that language must be Turing-complete.
To be Turing complete, it is not necessary that you can produce arbitrary output symbols. It is sufficient that the output can be interpreted as the result of an arbitrary computation. Parsing will require conditions, loops and “practically” unbounded state space, so...
-
-
Yes. The whole idea of a compiler is to translate a program into another program and this is all finite. If the input language isn't too weird and the compiler doesn't attempt crazy optimizations, you can have a compiler that provably terminates.
-
So, there we can have a reasonable, useful "compile" instruction (in my original example) which is guaranteed to terminate, and this makes it not Turing-complete. (e.g. we can't make the compiler print something that can be interpreted as the sequence of all natural numbers)
- 1 more reply
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.