3 ms·
> This is a proof by construction that the language is computationally complete. The definition of Turing completeness in the article is not correct. A languag
by wyager 10y ago
> This is a proof by construction that the language is computationally complete.
The definition of Turing completeness in the article is not correct. A language being able to execute programs written in itself is not a sufficient condition of Turing completenes. Trivial example: define a language with one pre-defined term, x, which is a routine that takes as input a string, checks if it's "x", and executes it if it is. The empty language is a counter-example as well, but that's cheating.
I'm also not sure if the use of the phrase "fixed point" is a misunderstanding of the definition of a fixed point or just an unfortunate use of a term that already has great significance in LISP.
- zodiac 10y agoI agree...I think a real "proof by construction that the language is [Turing] complete" would just be an interpreter for Turing machine programs written in Lisp, which is pretty boring.
- deleted 10y ago[deleted]