Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

# The Halting Problem proofs have a fatal flaw

6 views

### olcott

Sep 21, 2022, 2:22:18 PM9/21/22
to
computation that halts … the Turing machine will halt whenever it enters
a final state. (Linz:1990:234)

When the copy of Linz H that is embedded within Linz Ĥ is a simulating
halt decider applied to ⟨Ĥ⟩ ⟨Ĥ⟩ the correctly simulated ⟨Ĥ⟩ would never
reach its final state of ⟨Ĥ⟩.qy or ⟨Ĥ⟩.qn in 1 to ∞ steps of correct
simulation.

I added this material from the Peter Linz text to address the Turing
machine proofs. I paraphrased the Linz encoding because the Linz version
has two start states.

Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy
If the correctly simulated input ⟨Ĥ⟩ ⟨Ĥ⟩ to H would reach its own final
state of ⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩.

Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
If the correctly simulated input ⟨Ĥ⟩ ⟨Ĥ⟩ to H would never reach its own
final state of ⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩.

Ĥ.q0 copies its input then invokes its embedded copy of the original
Linz H...

computation that halts … the Turing machine will halt whenever it enters
a final state. (Linz:1990:234)

Because we can see that replacing H with a UTM would cause Ĥ to become
stuck in infinitely recursive simulation we can see that the input
correctly simulated by H would never reach the final state of this
simulated input, thus never halts.

Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company. (317-320)

--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

### Richard Damon

Sep 21, 2022, 7:04:29 PM9/21/22
to

On 9/21/22 2:22 PM, olcott wrote:
> computation that halts … the Turing machine will halt whenever it enters
> a final state. (Linz:1990:234)
>
> When the copy of Linz H that is embedded within Linz Ĥ is a simulating
> halt decider applied to ⟨Ĥ⟩ ⟨Ĥ⟩ the correctly simulated ⟨Ĥ⟩ would never
> reach its final state of ⟨Ĥ⟩.qy or ⟨Ĥ⟩.qn in 1 to ∞ steps of correct
> simulation.

WRONG. The CORRECT (and thus COMPLETE) simulation of the input WILL
reach the final state if H <H^> <H^> goes to H.Qn

If H <H^> <H^> doesn't go to H.Qn or H.Qy, then it fails to be a decider.

We see this at the path of the CORRECT (and thus complete) simulation if
the input to H will be: (here <H^> is wM from

The input to H <H^> <H^> represents H^ <H^>
that starts at q0 <H^> then goes to
H^.q0 <H^> <H^> after duplicating the input.
this is where the copy of H's q0 <H^> <H^> is
since we know that H <H^> <H^> is ending up at is y1 qn y2 we know the
copy will end up at H^ y1 qn y2
And this is defined as a final state.

Please point out the error here.

>
>
> I added this material from the Peter Linz text to address the Turing
> machine proofs. I paraphrased the Linz encoding because the Linz version
> has two start states.
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy
> If the correctly simulated input ⟨Ĥ⟩ ⟨Ĥ⟩ to H would reach its own final
> state of ⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩.
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
> If the correctly simulated input ⟨Ĥ⟩ ⟨Ĥ⟩ to H would never reach its own
> final state of ⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩.
>
> Ĥ.q0 copies its input then invokes its embedded copy of the original
> Linz H...

Which was STIPULATED to end up at H's qn in finite time.

Thus we KNOW that this H can't just unconditionally simulate its input,
or it does get stuck in this loop.

>
> computation that halts … the Turing machine will halt whenever it enters
> a final state. (Linz:1990:234)
>
> Because we can see that replacing H with a UTM would cause Ĥ to become
> stuck in infinitely recursive simulation we can see that the input
> correctly simulated by H would never reach the final state of this
> simulated input, thus never halts.

So, does your H have a condition in its simulation to stop its
simulaiton and return its answer to the machine it is embedded in, and
thus H^ doesn't get stuck in an infinite loop, or does H get stuck in
this loop and NEVER give an answer.

>
> Linz, Peter 1990. An Introduction to Formal Languages and Automata.
> Lexington/Toronto: D. C. Heath and Company. (317-320)
>

FAIL.

### olcott

Sep 21, 2022, 7:53:22 PM9/21/22
to
On 9/21/2022 6:04 PM, Richard Damon wrote:
>
> On 9/21/22 2:22 PM, olcott wrote:
>> computation that halts … the Turing machine will halt whenever it
>> enters a final state. (Linz:1990:234)
>>
>> When the copy of Linz H that is embedded within Linz Ĥ is a simulating
>> halt decider applied to ⟨Ĥ⟩ ⟨Ĥ⟩ the correctly simulated ⟨Ĥ⟩ would
>> never reach its final state of ⟨Ĥ⟩.qy or ⟨Ĥ⟩.qn in 1 to ∞ steps of
>> correct simulation.
>
> WRONG. The CORRECT (and thus COMPLETE) simulation of the input WILL
> reach the final state if H <H^> <H^> goes to H.Qn
>

Yet another attempt to get away with the strawman deception.

The question is: Can the correctly simulated ⟨Ĥ⟩ reaches its own
simulated final state of ⟨Ĥ⟩.qy or ⟨Ĥ⟩.qn?

### Richard Damon

Sep 21, 2022, 8:17:02 PM9/21/22
to
On 9/21/22 7:53 PM, olcott wrote:
> On 9/21/2022 6:04 PM, Richard Damon wrote:
>>
>> On 9/21/22 2:22 PM, olcott wrote:
>>> computation that halts … the Turing machine will halt whenever it
>>> enters a final state. (Linz:1990:234)
>>>
>>> When the copy of Linz H that is embedded within Linz Ĥ is a
>>> simulating halt decider applied to ⟨Ĥ⟩ ⟨Ĥ⟩ the correctly simulated
>>> ⟨Ĥ⟩ would never reach its final state of ⟨Ĥ⟩.qy or ⟨Ĥ⟩.qn in 1 to ∞
>>> steps of correct simulation.
>>
>> WRONG. The CORRECT (and thus COMPLETE) simulation of the input WILL
>> reach the final state if H <H^> <H^> goes to H.Qn
>>
>
> Yet another attempt to get away with the strawman deception.
>
> The question is: Can the correctly simulated ⟨Ĥ⟩ reaches its own
> simulated final state of ⟨Ĥ⟩.qy or ⟨Ĥ⟩.qn?
>

No, that just shows that you don't understand the definiton of a Halt
Decider:

H wM w -> Qy Iff M w Halts, and Qn iff M w will never halt.

In English, H needs to decide if the machine/input that its input
describes will halt when run as an independent machine.

It is the behavior of the machine the input represents, executed as an
independent machine that is the key.

NOT "can H simulate its input to a final state?"

Just proves you are a ignorant pathological lying idiot that doesn't
know what you are talking about.

FAIL.

### olcott

Sep 22, 2022, 11:18:21 AM9/22/22
to
On 9/21/2022 7:16 PM, Richard Damon wrote:
> On 9/21/22 7:53 PM, olcott wrote:
>> On 9/21/2022 6:04 PM, Richard Damon wrote:
>>>
>>> On 9/21/22 2:22 PM, olcott wrote:
>>>> computation that halts … the Turing machine will halt whenever it
>>>> enters a final state. (Linz:1990:234)
>>>>
>>>> When the copy of Linz H that is embedded within Linz Ĥ is a
>>>> simulating halt decider applied to ⟨Ĥ⟩ ⟨Ĥ⟩ the correctly simulated
>>>> ⟨Ĥ⟩ would never reach its final state of ⟨Ĥ⟩.qy or ⟨Ĥ⟩.qn in 1 to ∞
>>>> steps of correct simulation.
>>>
>>> WRONG. The CORRECT (and thus COMPLETE) simulation of the input WILL
>>> reach the final state if H <H^> <H^> goes to H.Qn
>>>
>>
>> Yet another attempt to get away with the strawman deception.
>>
>> The question is: Can the correctly simulated ⟨Ĥ⟩ reaches its own
>> simulated final state of ⟨Ĥ⟩.qy or ⟨Ĥ⟩.qn?
>>
>
> No, that just shows that you don't understand the definiton of a Halt
> Decider:

It is an axiom that the correctly simulated input to a halt decider
derives the actual behavior specified by this input otherwise the notion
of a UTM is baselessly rejected out-of-hand.

### Richard Damon

Sep 22, 2022, 6:35:38 PM9/22/22
to
On 9/22/22 11:18 AM, olcott wrote:
> On 9/21/2022 7:16 PM, Richard Damon wrote:
>> On 9/21/22 7:53 PM, olcott wrote:
>>> On 9/21/2022 6:04 PM, Richard Damon wrote:
>>>>
>>>> On 9/21/22 2:22 PM, olcott wrote:
>>>>> computation that halts … the Turing machine will halt whenever it
>>>>> enters a final state. (Linz:1990:234)
>>>>>
>>>>> When the copy of Linz H that is embedded within Linz Ĥ is a
>>>>> simulating halt decider applied to ⟨Ĥ⟩ ⟨Ĥ⟩ the correctly simulated
>>>>> ⟨Ĥ⟩ would never reach its final state of ⟨Ĥ⟩.qy or ⟨Ĥ⟩.qn in 1 to ∞
>>>>> steps of correct simulation.
>>>>
>>>> WRONG. The CORRECT (and thus COMPLETE) simulation of the input WILL
>>>> reach the final state if H <H^> <H^> goes to H.Qn
>>>>
>>>
>>> Yet another attempt to get away with the strawman deception.
>>>
>>> The question is: Can the correctly simulated ⟨Ĥ⟩ reaches its own
>>> simulated final state of ⟨Ĥ⟩.qy or ⟨Ĥ⟩.qn?
>>>
>>
>> No, that just shows that you don't understand the definiton of a Halt
>> Decider:
>
> It is an axiom that the correctly simulated input to a halt decider
> derives the actual behavior specified by this input otherwise the notion
> of a UTM is baselessly rejected out-of-hand.
>
>

The correctly AND COMPLETELY simulate input to a halt decider.

Since H doesn't do one (at least not the one that gives an answer), we
need to look at the UTM simulation of the input.

If H(P,P) returns 0, then UTM(P,P) will halt.

THIS HAS BEEN PROVEN.

Thus your statememt above just PROVES that ANY H that returns 0 for
H(P,P) where P has been built on that H is incorrect.

YOU HAVE FAILED.

### olcott

Sep 22, 2022, 7:28:35 PM9/22/22
to
On 9/22/2022 5:35 PM, Richard Damon wrote:
> On 9/22/22 11:18 AM, olcott wrote:
>> On 9/21/2022 7:16 PM, Richard Damon wrote:
>>> On 9/21/22 7:53 PM, olcott wrote:
>>>> On 9/21/2022 6:04 PM, Richard Damon wrote:
>>>>>
>>>>> On 9/21/22 2:22 PM, olcott wrote:
>>>>>> computation that halts … the Turing machine will halt whenever it
>>>>>> enters a final state. (Linz:1990:234)
>>>>>>
>>>>>> When the copy of Linz H that is embedded within Linz Ĥ is a
>>>>>> simulating halt decider applied to ⟨Ĥ⟩ ⟨Ĥ⟩ the correctly simulated
>>>>>> ⟨Ĥ⟩ would never reach its final state of ⟨Ĥ⟩.qy or ⟨Ĥ⟩.qn in 1 to
>>>>>> ∞ steps of correct simulation.
>>>>>
>>>>> WRONG. The CORRECT (and thus COMPLETE) simulation of the input WILL
>>>>> reach the final state if H <H^> <H^> goes to H.Qn
>>>>>
>>>>
>>>> Yet another attempt to get away with the strawman deception.
>>>>
>>>> The question is: Can the correctly simulated ⟨Ĥ⟩ reaches its own
>>>> simulated final state of ⟨Ĥ⟩.qy or ⟨Ĥ⟩.qn?
>>>>
>>>
>>> No, that just shows that you don't understand the definiton of a Halt
>>> Decider:
>>
>> It is an axiom that the correctly simulated input to a halt decider
>> derives the actual behavior specified by this input otherwise the
>> notion of a UTM is baselessly rejected out-of-hand.
>>
>>
>
> The correctly AND COMPLETELY simulate input to a halt decider.

Since we can see that the correctly and completely simulated input to
embedded_H never reaches its final state we know that every other
simulation also never reaches its final state, thus this input never halts.

### Richard Damon

Sep 22, 2022, 9:18:01 PM9/22/22
to
Who says it doesn't?

You have posted the CORRECT and COMPLETE simulation of the input to H /
embedded_H and it reaches a final state.

Remember, a simulation that is aborted does not show that the simultion
would be non-halting.

You need to run an INDEPENDENT simulation of that input by a UTM, and
that has been shown to be halting.

You keep on looking at the WRONG input, because you change the
definition of H abd thus make your "PROOF" just a LIE.

You are proving your ignorance of the subject, that you only know how to
lie, and that you are just an idiot for thinking people can't see

FAIL.

### olcott

Sep 22, 2022, 10:35:11 PM9/22/22
to
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy
If the correctly simulated input ⟨Ĥ⟩ ⟨Ĥ⟩ to H would reach its own final
state of ⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩.

Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
If the correctly simulated input ⟨Ĥ⟩ ⟨Ĥ⟩ to H would never reach its own
final state of ⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩.

When we replace H with a UTM we can see that Ĥ never stops running.

From this we can determine
For every definition of simulating halt decider of H none of the
correctly simulated inputs ever reach their own final state ⟨Ĥ.qy⟩ or
⟨Ĥ.qn⟩.

From this we can determine that
The input to H never halts, thus is correctly determined to be non-halting.

That I have to keep repeating these things to you would seem to indicate
that you either have brain damage or are dishonest, another alternative
is that these things are much more difficult for you than they are for me.

### Richard Damon

Sep 22, 2022, 11:09:46 PM9/22/22
to
Almost, the COMPLETELY (and correctly) simulated input to H would reach
its own final state.

>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
> If the correctly simulated input ⟨Ĥ⟩ ⟨Ĥ⟩ to H would never reach its own
> final state of ⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩.
>

Almost, the COMPLETELY (and correctly) simulate input to H would NEVER,
after an unbounded number of steps

> When we replace H with a UTM we can see that Ĥ never stops running.

But then this "input" isn't H^ any more, so the logic is incorrect.

You are just proving your ignorance, stupidity, and deceit.

FFFFF A IIIII L
F A A I L
F A A I L
FFFFF AAAAA I L
F A A I L
F A A I L
F A A IIIII LLLLL

Unless you are going to claim that your H actually IS a UTM, but then
all you have done is show that your H will never answer, and thus also fail,

>
> From this we can determine
> For every definition of simulating halt decider of H none of the
> correctly simulated inputs ever reach their own final state ⟨Ĥ.qy⟩ or
> ⟨Ĥ.qn⟩.

Since the input you are looking at isn't H^ anymore, your logic is unsound.

>
> From this we can determine that
> The input to H never halts, thus is correctly determined to be non-halting.

No, you have proved that something that wasn't the input to H to be
non-halting, and that you are an idiot.

>
> That I have to keep repeating these things to you would seem to indicate
> that you either have brain damage or are dishonest, another alternative
> is that these things are much more difficult for you than they are for me.
>

You are just proving your stupditiy.

You logic is based on fallacious arguements, and incorrect operation.

We have shown you the CORRECT complete simulation of the ACTUAL input to
H, and that halts.

### olcott

Sep 23, 2022, 11:30:17 AM9/23/22
to
If it is not simulated by H then it is not input to H.

Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy
When ⟨Ĥ⟩ ⟨Ĥ⟩ correctly simulated by H reaches its own final state of
⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩.

Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
When ⟨Ĥ⟩ ⟨Ĥ⟩ correctly simulated by H would never reach its own final
state of ⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩.

### Richard Damon

Sep 23, 2022, 6:43:55 PM9/23/22
to
Why do you say That?

The "Input" to H is EXACTLY the finite string.

The behavior of the string being defined as the UTN Simulation is a
precisely defined property.

Note, by YOUR definition, it is IMPOSSIBLE to even define a Halt Decider
by the required definition, so they are simple proven to not exist.

FAIL.

>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy
> When ⟨Ĥ⟩ ⟨Ĥ⟩ correctly simulated by H reaches its own final state of
> ⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩.
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
> When ⟨Ĥ⟩ ⟨Ĥ⟩ correctly simulated by H would never reach its own final
> state of ⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩.
>
>

Which isn't the definitions from your source, so you are just admitting
that you aren't working on the Halting Problem.

This means you are aditting that you have wasted the last 18 years of

YOU HAVE FAILED.

There is NO requirement that the simulation be by the decider.