4 ms·
That does not really apply. A compiler can compile itself, it can check if its own code is valid.
by Iv 7y ago
That does not really apply. A compiler can compile itself, it can check if its own code is valid.
- ukj 7y agoYou are necessarily claiming that a compiler is incapable of false negatives. e.g incorrectly validating its own code. Beware of bugs in the above code; I have only proved it correct, not tried it --Donald Knuth
- mannykannot 7y agoThe fact that someone might make a mistake in doing something does not show it cannot be done. More generally, You seem to be mistaking validating a program's source with the question of whether it performs its intended purpose. These are different things, and attempting to conflate them will only lead to confusion.
- ukj 7y ago> You seem to be mistaking validating a program's source with the question of whether it performs its intended purpose. In general, that is a useful distinction to make, but you forgot about the edge case where the distinction is meaningless. A self-hosting compiler's intended purpose is to validate its own source code.
- mannykannot 7y agoThen your mistake appears to be in failing to see that your perceived edge case does not invalidate the first sentence of my reply. If the sole purpose of a parser is to syntactically validate its own source (which is not the case for a compiler's parser, by the way, not even if we expand 'its own source' to 'arbitrary input'), then if it does that correctly, that's all there is to it.
- ukj 7y agoYour mistake appears to be - ignoring the alternative hypothesis. You are mistaken, not me. The consequences of Godel's incompleteness theorem are such that a mathematical system (such as a compiler) cannot prove its own correctness. It can only prove that it is free from known errors. Once you define what an "error" is.
- mannykannot 7y agoGodel incompleteness only applies to sufficiently powerful formal systems.
- ukj 7y agoIndeed. Type 0 Grammars are the most powerful grammars we have. https://en.wikipedia.org/wiki/Chomsky_hierarchy#Type-0_grammars https://en.wikipedia.org/wiki/Chomsky_hierarchy#Type-0_gramm... In this type of grammar Godel's incompleteness theorem is equivalent to the Halting problem.
- mannykannot 7y agoAnd which programming language did you have in mind?
- ukj 7y agoAll of them. "Type-0 grammars include all formal grammars. They generate exactly all languages that can be recognized by a Turing machine."
- mannykannot 7y agoI see - you have the complexity relation the wrong way round.
- 7y ago