Logic and
Language

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

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

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.

Interested in supporting this site?

You can help by sharing the site with others. You can also donate at where there are full details.

As site owner I reserve the right to keep my comments sections as I deem appropriate. I do not use that right to unfairly censor valid criticism. My reasons for deleting or editing comments do not include deleting a comment because it disagrees with what is on my website. Reasons for exclusion include:
Comments with excessive number of different points.
Questions about matters that do not relate to the page they post on. Such posts are not comments.
Comments with a substantial amount of mathematical terms not properly formatted will not be published unless a file (such as doc, tex, pdf) is simultaneously emailed to me, and where the mathematical terms are correctly formatted.

Reasons for deleting comments of certain users:
Bulk posting of comments in a short space of time, often on several different pages, and which are not simply part of an ongoing discussion. Multiple anonymous user names for one person.
Users, who, when shown their point is wrong, immediately claim that they just wrote it incorrectly and rewrite it again - still erroneously, or else attack something else on my site - erroneously. After the first few instances, further posts are deleted.
Users who make persistent erroneous attacks in a scatter-gun attempt to try to find some error in what I write on this site. After the first few instances, further posts are deleted.

Difficulties in understanding the site content are usually best addressed by contacting me by e-mail.

Based on HashOver Comment System by Jacob Barkdull

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