3 ms·

Indeed. 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/C

by ukj 7y ago

Indeed. 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 ago
And which programming language did you have in mind?
- ukj 7y ago
  All of them. "Type-0 grammars include all formal grammars. They generate exactly all languages that can be recognized by a Turing machine."
  - mannykannot 7y ago
    I see - you have the complexity relation the wrong way round.
    - ukj 7y ago
      Are you sure you aren't mistaken? :-)
      - mannykannot 7y ago
        Go ahead - show me wrong.
        ukj 7y ago
        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.
        mannykannot 7y ago
        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.
        ukj 7y ago
        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 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.
        mannykannot 7y ago
        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
        dang 7y ago
        Please also stop.
        ukj 7y ago
        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.
        7y ago

by ukj 7y ago

mannykannot 7y ago

And which programming language did you have in mind?

ukj 7y ago
All of them. "Type-0 grammars include all formal grammars. They generate exactly all languages that can be recognized by a Turing machine."
- mannykannot 7y ago
  I see - you have the complexity relation the wrong way round.
  - ukj 7y ago
    Are you sure you aren't mistaken? :-)
    - mannykannot 7y ago
      Go ahead - show me wrong.
      - ukj 7y ago
        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.
        mannykannot 7y ago
        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.
        ukj 7y ago
        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 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.
        mannykannot 7y ago
        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
        dang 7y ago
        Please also stop.
        ukj 7y ago
        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.
        7y ago