4 ms·

Constructing the sentence is algorithmic. The key part is asserting that the sentence is true. For instance ZFC will prove that A:(ZFC cant prove GodelStatement

by enugu 9y ago

Constructing the sentence is algorithmic. The key part is asserting that the sentence is true. For instance ZFC will prove that A:(ZFC cant prove GodelStatement(ZFC) OR ZFC is inconsistent).GodelStatement is an algorithmic function which takes a list of axioms in some formal framework. Now, lets make ZFC' which is ZFC + 'ZFC is consistent'. ZFC' can prove A(as it contains ZFC) and uses the consistency of ZFC to prove A':(ZFC cant prove Godel(ZFC)) . Similarly, a program decides a set of problems(like does this Turing machine halt or does this diophantine equation have solutions) with access to its source code will be able to algorithmically generate the problem instance on which it will not halt. You can modify the program to create a new program which will use this information, but it will be a new program.

lisper 9y ago
> Constructing the sentence is algorithmic. No, it isn't. But it's a non-trivial point. > Similarly, a program decides a set of problems(like does this Turing machine halt or does this diophantine equation have solutions) with access to its source code will be able to algorithmically generate the problem instance on which it will not halt. You can modify the program to create a new program which will use this information, but it will be a new program. So this all depends on what you consider a "new program". Suppose we write a program that actually does this: analyzes its own code, algorithmically produces the Godel sentence for that code, then modifies its code to include that as an axiom, forever. That program is a program, and that program will also have a Godel sentence, but one which it cannot construct using that algorithm. You need a different algorithm to construct Godel sentences for programs that constructs Godel sentences on programs that don't construct Godel sentences. The result is a hierarchy of Godel-sentence constructors. At any level in the hierarchy the procedure is algorithmic, but going from one level to the next is not. It's similar to the process of constructing the hierarchy of ordinals, which is also provably non-algorithmic.
- enugu 9y ago
  There is a program, G, which will take as input the source code of the program, P (in some fixed language) and output Turing machine, T which doesnt halt, such that either P will fail to say T doesnt halt, or P has mistakes(claims halting for some Turing machines when they dont halt). Some programs P can algorithmically run P', P'' etc, but as long as that process is part of the source code of P, G will work.
  - lisper 9y ago
    Sure. So? How does that in any way refute what I said?
    - enugu 9y ago
      Point in my first post was that G is algorithmic. What you are referring to is the repeated extension of G which gets into issues of ordinals.
      - lisper 9y ago
        Yes, but I'm the one who made the original claim that "there is no algorithm for constructing a Godel sentence". So I'm the one who gets to say what I meant by that :-)

by enugu 9y ago

lisper 9y ago

> Constructing the sentence is algorithmic. No, it isn't. But it's a non-trivial point. > Similarly, a program decides a set of problems(like does this Turing machine halt or does this diophantine equation have solutions) with access to its source code will be able to algorithmically generate the problem instance on which it will not halt. You can modify the program to create a new program which will use this information, but it will be a new program. So this all depends on what you consider a "new program". Suppose we write a program that actually does this: analyzes its own code, algorithmically produces the Godel sentence for that code, then modifies its code to include that as an axiom, forever. That program is a program, and that program will also have a Godel sentence, but one which it cannot construct using that algorithm. You need a different algorithm to construct Godel sentences for programs that constructs Godel sentences on programs that don't construct Godel sentences. The result is a hierarchy of Godel-sentence constructors. At any level in the hierarchy the procedure is algorithmic, but going from one level to the next is not. It's similar to the process of constructing the hierarchy of ordinals, which is also provably non-algorithmic.

enugu 9y ago
There is a program, G, which will take as input the source code of the program, P (in some fixed language) and output Turing machine, T which doesnt halt, such that either P will fail to say T doesnt halt, or P has mistakes(claims halting for some Turing machines when they dont halt). Some programs P can algorithmically run P', P'' etc, but as long as that process is part of the source code of P, G will work.
- lisper 9y ago
  Sure. So? How does that in any way refute what I said?
  - enugu 9y ago
    Point in my first post was that G is algorithmic. What you are referring to is the repeated extension of G which gets into issues of ordinals.
    - lisper 9y ago
      Yes, but I'm the one who made the original claim that "there is no algorithm for constructing a Godel sentence". So I'm the one who gets to say what I meant by that :-)