Logic and Language
Load the menuLoad the menu


Copyright   James R Meyer    2012 - 2020 https://www.jamesrmeyer.com

Note: Full functionality of this website requires JavaScript to be enabled in your browser.
 

Oh no ! Yet Another Flawed Incompleteness Proof

From the collection of obviously flawed incompleteness proofs, here is yet another:

A Flawed Incompleteness Proof by Sebastian Oberhoff

Sebastian Oberhoff has published a paper Incompleteness Ex Machina on arXiv which includes what he claims are proof of incompleteness. Oberhoff states at the outset that he will proceed to prove incompleteness by two different methods.

 

We analyze Oberhoff’s claims below.

Other obviously flawed incompleteness proofs can be seen at:

By Bernd Buldt

By Francesco Berto

By Dan Gusfield

By Byunghan Kim

By Arindama Singh

By Antti Valmari

 

Oberhoff’s first proof “method”

Oberhoff’s first “method” isn’t really Oberhoff’s method, it is simply a reference to almost all of Gödel’s proof. Oberhoff remarks that Gödel proved in his incompleteness paper that in his formal system F there is a specific sentence that Oberhoff calls G, and for which Oberhoff claims that one can apply the interpretation “I am not provable in F ”.

 

All that Oberhoff is doing is asking us to accept Gödel’s work up to the point where Gödel describes that expression (17 Gen r). But at that point in Gödel’s proof, Gödel has practically finished his (first) incompleteness proof anyway and it only requires a few further lines for Gödel to complete it. Instead Oberhoff writes several long paragraphs to attach his own version of a completion of Gödel’s proof.

 

What he is doing, despite his proclamation at the outset that “…we’ll prove Gödel’s incompleteness theorems…” is essentially writing a cursory description of Gödel’s proof. He is not writing a proof of incompleteness, since for anyone to accept his proof, they first have to examine Gödel’s proof and satisfy themselves that Gödel proved what Oberhoff claims he proved. But an examination of Gödel’s proof demonstrates that Gödel actually failed to prove a crucial proposition in his paper (his Proposition V), and since that is the case, then Oberhoff’s claims also cannot be considered proven. He hasn’t created a rigorous proof. He might as well simply assert, as an unproven assumption, that there is an expression in the formal system that states “I am not provable in F ”.

 

Oberhoff’s second method

His second method states:

Theorem 4 (First Incompleteness Theorem—Original Version By Computation). Let F be an honest Turing complete formal system. Then F is incomplete.

and his “proof” of this is:

 

For a formal system to be Turing complete simply means that it can reason about algorithms. Suppose F was complete. Then we could solve the Halting Problem using the following algorithm (where “A(A)” denotes an algorithm A running on its own source code)

for x ∈ all possible strings

if x proves «A(A) doesn’t halt»

reject

if x proves «A(A) halts»

accept

 

Because F is complete this search will eventually hit upon a proof of either «A(A) halts» or «A(A) doesn’t halt». And because F is honest we’ll be able to trust its judgment. That determines whether or not A(A) halts. But, as we saw only a moment ago, it’s impossible to solve the Halting Problem. So F couldn’t have been complete.

 

Oberhoff says that his formal system F is a system that can reason about algorithms, and his algorithm above refers to his system F reasoning about algorithms halting or not halting.

 

But algorithms don’t halt - they don’t start and they don’t stop. They are simply expressions that might be termed instructions, so that some thing, such as a human or a machine can follow these instructions. Such a thing can start following an algorithm, and depending on the algorithm, they may come to a point where there are no further instructions to be followed.

 

This means that any expression that refers to the notion of halting or not halting must also refer in some way to an entity for which the halting or not halting applies. And that means that Oberhoff’s “Turing complete formal system” would need to be able to not only reason about algorithms, but also to reason about things that follow the instructions of algorithms. But Oberhoff gives no indication of how one would define such a system. His sketchy outline, which includes various hidden assumptions, whatever else it is, it is not, by any stretch of the imagination, a proof.

section divider

Also see Errors in incompleteness proofs and Analysis of incompleteness proofs.

 

Other obviously flawed incompleteness proofs can be seen at:

An Incompleteness Proof by Bernd Buldt

An Incompleteness Proof by Francesco Berto

An Incompleteness Proof by Dan Gusfield

An Incompleteness Proof by Byunghan Kim

An Incompleteness Proof by Arindama Singh

An Incompleteness Proof by Antti Valmari

section divider

 

 

Diverse opinions and criticisms are welcome, but messages that are frivolous, irrelevant or devoid of logical basis will be blocked. Difficulties in understanding the site content are usually best addressed by contacting me by e-mail. Note: you will be asked to provide an e-mail address - any address will do, it does not require verification. Your e-mail will only be used to notify you of replies to your comments - it will never be used for any other purpose and will not be displayed. If you cannot see any comments below, see Why isn’t the comment box loading?.

section divider
 

Copyright   James R Meyer    2012 - 2020
https://www.jamesrmeyer.com