4 ms·
Then 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 par
by mannykannot 7y ago
Then 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.
- ukj 7y agoAre you sure you aren't mistaken? :-)
- mannykannot 7y agoGo ahead - show me wrong.
- ukj 7y agoI have already done that, what I am unsure of is how to go about convincing you. With compilers - I just fix the bug myself. With humans, I have to convince the human to self-correct. Common problem in distributed systems that - leader election.
- mannykannot 7y agoIt is a general rule that those who avoid answering a question do not have an answer, and this is no exception. Here, You completely misunderstand Chomsky’s hierarchy: By your inverted-hierarchy argument, the simplest regular language would be complex enough that incompleteness would be an issue in its validation.
- ukj 7y agoWell, this looks like abuse of Cunningham's law, but I'll bite. It is a general rule that general rules have exceptions. And you have (incorrectly) asserted that this is not an exception. Q.E.D Even the most powerful languages (Type 0 in the hierarchy) cannot solve the halting problem. Which is equivalent to Godel's incompleteness theorem. https://www.scottaaronson.com/blog/?p=710 https://www.scottaaronson.com/blog/?p=710 If a Type 3 grammar can recursively prove its own correctness, it's not a Type 3 grammar! But if you desperately want to be right, I will happily lie to you (you are right, I am wrong), so I can move on with my life.