Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

[flagged]


The 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.


> 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.


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.


[flagged]


Godel incompleteness only applies to sufficiently powerful formal systems.


Indeed. Type 0 Grammars are the most powerful grammars we have.

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.


And which programming language did you have in mind?


All of them.

"Type-0 grammars include all formal grammars. They generate exactly all languages that can be recognized by a Turing machine."


I see - you have the complexity relation the wrong way round.


Are you sure you aren't mistaken? :-)


Go ahead - show me wrong.


I 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.


It 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.


Well, 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

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.


Your second paragraph is just a direct begging-of-the-question.

More significantly, verifying that sentences are well-formed in some language is not the same as proving the language’s correctness.

As a response to you argument, consider this regular language:

A


Curry-Howard isomorphism.

Proving that a sentences are “well-formed” is the same as implementing an algorithm which takes a string and returns a Boolean.

You can call this function “is_well_formed?”

I await your proof in the regular language you have specified above.


Please also stop.


Please stop.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: