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

Re: Infinitely Recursive input on HP Proofs

2 views
Skip to first unread message

olcott

unread,
May 16, 2021, 5:00:08 PM5/16/21
to
On 5/16/2021 3:21 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> Any genius knowing the theory of computation quite well can easily
>> confirm that Ĥ(Ĥ) specifies the non halting behavior pattern of
>> [infinitely_nested_simulation] to every simulating halt decider.
>> This equally applies to all of the halting problem instances.
>>
>> Ĥ(Ĥ) is short-hand for:
>> Now Ĥ is a Turing machine, so that it will have some description in Σ*,
>> say ŵ. This string, in addition to being the description of Ĥ can also be used
>> as input string. We can therefore legitimately ask what would happen if Ĥ is
>> applied to ŵ. (Linz:1990:320)
>>
>> Linz, Peter 1990. An Introduction to Formal Languages and
>> Automata. Lexington/Toronto: D. C. Heath and Company. (315-320)
>
> Nonsense. H is the name given in Linz to a non-existent Turing
> machine. H^, derived from it, also does not exit. Anyone who has read
> that book should know that H^([H^]) specifies no behaviour at all.
>
> You have constructed a poor-man's partial decider that gets the "hat"
> case wrong, but you can't justify the wrong answer by appeal Linz.
>
> Your "infinitely nested simulation" explanation for your decider giving
> the wrong answer can be put on a more formal basis, but you can't do by
> re-using the names of nonexistent TM's from Linz.
>

Well I won't say that you are not a genius or that you don't know the
theory of computation very well.

The actual Ĥ(<Ĥ>) does specify [infinitely_nested_simulation] to every
simulating halt decider. This [infinitely_nested_simulation] is more
complex than the one that Halts recognizes.

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn

The above is adapted from (Linz:1990:319).
It shows that Turing machine Ĥ copies its input at (q0) and begins
executing an embedded copy of the original halt decider with this input
at (qx).

The (qy) state indicates that the halt decider decides that its input
would halt. The ((qn)) state indicates the input would not halt. The
appended (qa) and (qb) states cause Ĥ to infinitely loop if the halt
decider decides that its input would halt.

It can be understood from the above specification that when the embedded
halt decider @Ĥ.qx bases its halting decision on simulating its input,
and it has (Ĥ, Ĥ) as its input that:
Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with
this copy then
Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with
this copy then
Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with
this copy...
unless and until the halt decider @Ĥ.qx stops simulating its input.

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

So it seems to be the same as it was more than four years ago you are so
biased against either me or my position (or both) that you simply won't
pay enough attention to see that I am right.

The key evidence that I am right and you just don't see it is the lack
of any correct rebuttal.

That the actual Ĥ(<Ĥ>) does specify [infinitely_nested_simulation] to
every simulating halt decider can't be refuted simply because <it is>
the case.


--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

olcott

unread,
Sep 27, 2021, 2:23:16 PM9/27/21
to
On 3/11/2017 3:13 PM, peteolcott wrote:
> http://LiarParadox.org/HP_Infinite_Recursion.pdf
>
> As this page 319 of An Introduction to Formal Languages and Automata
> by Peter Linz 1990 indicates
>
> From H' we construct another Turing machine H-Hat. This new machine takes as input Wm, copies it then behaves exactly like H'.
>
> q0 Wm |-* H-Hat q0 Wm Wm...
>
> Page 320 indicates that we apply H-Hat to itself as input.
>
> The problem is that every H-Hat needs a pair of inputs.
>
> H-Hat takes an H-Hat as input and copies it so that it
> can analyze how its input H-hat would analyze the copy
> of H-Hat that it just made.
>
> The input H-Hat would have to copy its own input H-Hat
> so that it can analyze what its own input H-Hat would
> do on its own input, on and on forever...
>
> Copyright 2016 and 2017 Pete Olcott.
>

This post is my earliest USENET post regarding this key insight:

The halting theorem counter-examples present infinitely nested
simulation (non-halting) behavior to every simulating halt decider.

Here is the original published reference (August 2016) to this same idea:

It looks like the original specification provided
in the Linz text may be infinitely recursive in that
each TM requires its own input. We fix this by providing
simple input that definitely halts.

https://www.researchgate.net/publication/307509556_Self_Modifying_Turing_Machine_SMTM_Solution_to_the_Halting_Problem_concrete_example
0 new messages