On Sunday, 20 June 2021 at 11:49:46 UTC+1, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>
> > On Sunday, 20 June 2021 at 01:39:09 UTC+1, Ben Bacarisse wrote:
> >> Malcolm McLean <malcolm.ar...@gmail.com> writes:
> >>
> >> > On Sunday, 20 June 2021 at 00:00:28 UTC+1, Ben Bacarisse wrote:
> >> >> Malcolm McLean <malcolm.ar...@gmail.com> writes:
> >> >>
> >> >> > On Friday, 18 June 2021 at 17:22:20 UTC+1, Ben Bacarisse wrote:
> >> >> >> Malcolm McLean <malcolm.ar...@gmail.com> writes:
> >> >> >>
> >> >> >> > or as a lesser but still impressive achievement can you show that no proof that
> >> >> >> > halting is undecidable is possible?
> >> >> >> What is impressive about that? What exactly is it you think would be
> >> >> >> would be impressive to prove?
> >> >> >>
> >> >> > We define the "confounding property" such that we can clearly say
> >> >> > whether any machine has "the confounding property". We then remove
> >> >> > these machines from our set of all Turing machines. However we maybe
> >> >> > still can't write a halt decider which decides this set, which is what
> >> >> > we really want. What we can maybe do, however, is show that every
> >> >> > proof that a universal decider is not possible relies on example
> >> >> > machines with the confounding property, and no proof that doesn't rely
> >> >> > on this can be offered. I'd settle for that if I was working on this
> >> >> > problem.
> >> >>
> >> >> What about Linz's real proof of HP -- the one where it is just a
> >> >> corollary of theorem 11.5: that there exist recursively enumerable
> >> >> languages that are not recursive? What about the proof using Radó's
> >> >> original proof that the busy beaver function is not TM-computable?
> >> >>
> >> >> Do these proofs rely on what you might consider this "confounding
> >> >> property"? If the property is one of halting problem instances that it
> >> >> seems clear that there are proof that don't rely on it in any way.
> >> >>
> >> >> As for halting problem instances that might have this property, if it is
> >> >> an "interesting" one (c.f. Rice) then the set of instances with that
> >> >> property is undecidable. If it's boring and the set is decidable
> >> >> (roughly-speaking, it's a purely syntactic property) then the set of
> >> >> remaining instances is not decidable.
> >> >>
> >> > This can't be right. Say we declare the "confounding property" to be
> >> > loops in the state graph. Clearly these are decidable (it's a "boring"
> >> > property). Clearly we can also decide the remaining machines (all
> >> > must halt).
> >> Yes, you are right. The problem is that the decidable properties are
> >> not the interesting ones. There are any number of ways to split the
> >> instances into two boring groups. But that can't be what you meant by
> >> something impressive was it?
> >>
> >> What I should have said is that to be "impressive", I would have thought
> >> that one or other group (the included of excluded instances) has to be
> >> interesting in the sense of Rice's theorem.
> >> > Clearly also that "confounding property" removes too many machines.
> >> > No-one's going to be very impressed with our decider. But we can maybe
> >> > draw the "confounding property" tighter.
> >> Of course. There is always an endless chain of better partial deciders
> >> in the sense that a better one decides a larger set of halting instances
> >> without ever incorrectly including any non-halting instances. One
> >> obvious such chain is S_n that only simulates for n steps.
> >>
> > Yes, we can easily split the set of all machines into two groups, for which
> > one determining halting is straightforwards. But that's not really what we
> > are after.
> Yes, splitting instances into "I know this halts" and the "the rest" is
> trivial. And simulation is not the only way to get an "I know this
> halts" set of instances.
> > The confounding property has to be something like "has unstable expanding
> > state". But how you would define, much less decide that, I don't know.
> So you think there may be some decidable set of non-halting instances
> that would be, non the less, interesting to identify? If that's what
> you are saying, why call it "the confounding property"? I can't see the
> link you are making with the proof method.
>
The "confounding property" means "our halt decider can't decide these cases".
They won't all be non-halting, or it wouldn't be confounding. Nor will all the
cases we can decide necessarily be halting, though they were for a particular
example of a "confounding property" I gave.

If the "confounding property" is broad such that most non-trivial machines have
it, it's not really much progress. But as you say, it can be made narrower and
narrower. For instance part of the confounding property may be that the
machine runs for more than N steps. We can then push N as high as we like
by adding to the maximum counter value for a simulation. Unfortunately,
as the busy beaver theorem shows, we can't calculate the maximum number of
steps from the machine size, so we can't reduce the confounding cases to zero.

In reality, to be useful the confounding property would have to be something
like "has unstable expanding state". You can eyeball this by running the machine
and watching what happens to the tape. But actually putting it on a more
mathematical basis is likely to be challenging.

On 6/20/21 3:20 PM, Malcolm McLean wrote:
> On Sunday, 20 June 2021 at 11:49:46 UTC+1, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>
>>> On Sunday, 20 June 2021 at 01:39:09 UTC+1, Ben Bacarisse wrote:
>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>
>>>>> On Sunday, 20 June 2021 at 00:00:28 UTC+1, Ben Bacarisse wrote:
>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>
>>>>>>> On Friday, 18 June 2021 at 17:22:20 UTC+1, Ben Bacarisse wrote:
>>>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>>>
>>>>>>>>> or as a lesser but still impressive achievement can you show that no proof that
>>>>>>>>> halting is undecidable is possible?
>>>>>>>> What is impressive about that? What exactly is it you think would be
>>>>>>>> would be impressive to prove?
>>>>>>>>
>>>>>>> We define the "confounding property" such that we can clearly say
>>>>>>> whether any machine has "the confounding property". We then remove
>>>>>>> these machines from our set of all Turing machines. However we maybe
>>>>>>> still can't write a halt decider which decides this set, which is what
>>>>>>> we really want. What we can maybe do, however, is show that every
>>>>>>> proof that a universal decider is not possible relies on example
>>>>>>> machines with the confounding property, and no proof that doesn't rely
>>>>>>> on this can be offered. I'd settle for that if I was working on this
>>>>>>> problem.
>>>>>>
>>>>>> What about Linz's real proof of HP -- the one where it is just a
>>>>>> corollary of theorem 11.5: that there exist recursively enumerable
>>>>>> languages that are not recursive? What about the proof using Radó's
>>>>>> original proof that the busy beaver function is not TM-computable?
>>>>>>
>>>>>> Do these proofs rely on what you might consider this "confounding
>>>>>> property"? If the property is one of halting problem instances that it
>>>>>> seems clear that there are proof that don't rely on it in any way.
>>>>>>
>>>>>> As for halting problem instances that might have this property, if it is
>>>>>> an "interesting" one (c.f. Rice) then the set of instances with that
>>>>>> property is undecidable. If it's boring and the set is decidable
>>>>>> (roughly-speaking, it's a purely syntactic property) then the set of
>>>>>> remaining instances is not decidable.
>>>>>>
>>>>> This can't be right. Say we declare the "confounding property" to be
>>>>> loops in the state graph. Clearly these are decidable (it's a "boring"
>>>>> property). Clearly we can also decide the remaining machines (all
>>>>> must halt).
>>>> Yes, you are right. The problem is that the decidable properties are
>>>> not the interesting ones. There are any number of ways to split the
>>>> instances into two boring groups. But that can't be what you meant by
>>>> something impressive was it?
>>>>
>>>> What I should have said is that to be "impressive", I would have thought
>>>> that one or other group (the included of excluded instances) has to be
>>>> interesting in the sense of Rice's theorem.
>>>>> Clearly also that "confounding property" removes too many machines.
>>>>> No-one's going to be very impressed with our decider. But we can maybe
>>>>> draw the "confounding property" tighter.
>>>> Of course. There is always an endless chain of better partial deciders
>>>> in the sense that a better one decides a larger set of halting instances
>>>> without ever incorrectly including any non-halting instances. One
>>>> obvious such chain is S_n that only simulates for n steps.
>>>>
>>> Yes, we can easily split the set of all machines into two groups, for which
>>> one determining halting is straightforwards. But that's not really what we
>>> are after.
>> Yes, splitting instances into "I know this halts" and the "the rest" is
>> trivial. And simulation is not the only way to get an "I know this
>> halts" set of instances.
>>> The confounding property has to be something like "has unstable expanding
>>> state". But how you would define, much less decide that, I don't know.
>> So you think there may be some decidable set of non-halting instances
>> that would be, non the less, interesting to identify? If that's what
>> you are saying, why call it "the confounding property"? I can't see the
>> link you are making with the proof method.
>>
> The "confounding property" means "our halt decider can't decide these cases".
> They won't all be non-halting, or it wouldn't be confounding. Nor will all the
> cases we can decide necessarily be halting, though they were for a particular
> example of a "confounding property" I gave.
>
> If the "confounding property" is broad such that most non-trivial machines have
> it, it's not really much progress. But as you say, it can be made narrower and
> narrower. For instance part of the confounding property may be that the
> machine runs for more than N steps. We can then push N as high as we like
> by adding to the maximum counter value for a simulation. Unfortunately,
> as the busy beaver theorem shows, we can't calculate the maximum number of
> steps from the machine size, so we can't reduce the confounding cases to zero.
>
> In reality, to be useful the confounding property would have to be something
> like "has unstable expanding state". You can eyeball this by running the machine
> and watching what happens to the tape. But actually putting it on a more
> mathematical basis is likely to be challenging.
>
>

Actually there IS a well defined 'confounding property' which if it
actually was detectable and was the only case where the decider couldn't
make the right answer might justify giving the problem a third answer of
confounding, and that would be that the machine's algorith is derived
from the deciders algorithm and does the opposite of it to make the
decider wrong. I.E. H^.

THe problem, as has been pointed out, is that actually reliably
detecting this in actual Turing Machines is impossible, and this is NOT
the only class of problems that can't be decided (just the simplest to
show). Since that possible useful case is just a unicorn, it isn't
really interesting.

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Sunday, 20 June 2021 at 11:49:46 UTC+1, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>
>> > On Sunday, 20 June 2021 at 01:39:09 UTC+1, Ben Bacarisse wrote:
>> >> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>> >>
>> >> > On Sunday, 20 June 2021 at 00:00:28 UTC+1, Ben Bacarisse wrote:
>> >> >> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>> >> >>
>> >> >> > On Friday, 18 June 2021 at 17:22:20 UTC+1, Ben Bacarisse wrote:
>> >> >> >> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>> >> >> >>
>> >> >> >> > or as a lesser but still impressive achievement can you show that no proof that
>> >> >> >> > halting is undecidable is possible?
>> >> >> >> What is impressive about that? What exactly is it you think would be
>> >> >> >> would be impressive to prove?
>> >> >> >>
>> >> >> > We define the "confounding property" such that we can clearly say
>> >> >> > whether any machine has "the confounding property". We then remove
>> >> >> > these machines from our set of all Turing machines. However we maybe
>> >> >> > still can't write a halt decider which decides this set, which is what
>> >> >> > we really want. What we can maybe do, however, is show that every
>> >> >> > proof that a universal decider is not possible relies on example
>> >> >> > machines with the confounding property, and no proof that doesn't rely
>> >> >> > on this can be offered. I'd settle for that if I was working on this
>> >> >> > problem.
>> >> >>
>> >> >> What about Linz's real proof of HP -- the one where it is just a
>> >> >> corollary of theorem 11.5: that there exist recursively enumerable
>> >> >> languages that are not recursive? What about the proof using Radó's
>> >> >> original proof that the busy beaver function is not TM-computable?
>> >> >>
>> >> >> Do these proofs rely on what you might consider this "confounding
>> >> >> property"? If the property is one of halting problem instances that it
>> >> >> seems clear that there are proof that don't rely on it in any way.
>> >> >>
>> >> >> As for halting problem instances that might have this property, if it is
>> >> >> an "interesting" one (c.f. Rice) then the set of instances with that
>> >> >> property is undecidable. If it's boring and the set is decidable
>> >> >> (roughly-speaking, it's a purely syntactic property) then the set of
>> >> >> remaining instances is not decidable.
>> >> >>
>> >> > This can't be right. Say we declare the "confounding property" to be
>> >> > loops in the state graph. Clearly these are decidable (it's a "boring"
>> >> > property). Clearly we can also decide the remaining machines (all
>> >> > must halt).
>> >> Yes, you are right. The problem is that the decidable properties are
>> >> not the interesting ones. There are any number of ways to split the
>> >> instances into two boring groups. But that can't be what you meant by
>> >> something impressive was it?
>> >>
>> >> What I should have said is that to be "impressive", I would have thought
>> >> that one or other group (the included of excluded instances) has to be
>> >> interesting in the sense of Rice's theorem.
>> >> > Clearly also that "confounding property" removes too many machines.
>> >> > No-one's going to be very impressed with our decider. But we can maybe
>> >> > draw the "confounding property" tighter.
>> >> Of course. There is always an endless chain of better partial deciders
>> >> in the sense that a better one decides a larger set of halting instances
>> >> without ever incorrectly including any non-halting instances. One
>> >> obvious such chain is S_n that only simulates for n steps.
>> >>
>> > Yes, we can easily split the set of all machines into two groups, for which
>> > one determining halting is straightforwards. But that's not really what we
>> > are after.
>> Yes, splitting instances into "I know this halts" and the "the rest" is
>> trivial. And simulation is not the only way to get an "I know this
>> halts" set of instances.
>> > The confounding property has to be something like "has unstable expanding
>> > state". But how you would define, much less decide that, I don't know.
>> So you think there may be some decidable set of non-halting instances
>> that would be, non the less, interesting to identify? If that's what
>> you are saying, why call it "the confounding property"? I can't see the
>> link you are making with the proof method.
>>
> The "confounding property" means "our halt decider can't decide these
> cases".

I don't like using words like "can't" for algorithms or TMs. Every TM
does one of three things with every input: accept, reject or fail to
terminate. The inputs it gets wrong, and those for which it fails to
terminate, are the cases it "can't decide". At least that's the only
meaning I can give to your "can't".

Thus every TM is a partial halt decider, and every TM has a "confounding
set" -- the cases it gets wrong. This may not be what you mean, but
it's the only meaning I can attribute to you definition.

> They won't all be non-halting, or it wouldn't be confounding. Nor will
> all the cases we can decide necessarily be halting, though they were
> for a particular example of a "confounding property" I gave.
>
> If the "confounding property" is broad such that most non-trivial
> machines have it, it's not really much progress. But as you say, it
> can be made narrower and narrower. For instance part of the
> confounding property may be that the machine runs for more than N
> steps. We can then push N as high as we like by adding to the maximum
> counter value for a simulation. Unfortunately, as the busy beaver
> theorem shows, we can't calculate the maximum number of steps from the
> machine size, so we can't reduce the confounding cases to zero.
>
> In reality, to be useful the confounding property would have to be
> something like "has unstable expanding state". You can eyeball this by
> running the machine and watching what happens to the tape. But
> actually putting it on a more mathematical basis is likely to be
> challenging.

Why do you think it might be worth accepting the challenge? I don't
think it's obvious that the cases any one TM gets wrong are going to be
interesting. This may be a case where I'd change my mind when someone
comes up with a definition and it just turns out to be interesting in
some as yet unforeseen sense, but I can't see that happening right now
(as is to be expected of unforeseen occurrences).

--
Ben.

On 21/06/2021 00:10, Ben Bacarisse wrote:
> [...] I don't
> think it's obvious that the cases any one TM gets wrong are going to be
> interesting. This may be a case where I'd change my mind when someone
> comes up with a definition and it just turns out to be interesting in
> some as yet unforeseen sense, but I can't see that happening right now
> (as is to be expected of unforeseen occurrences).

If we take the "one TM" to be a TM that always halts with the
answer "HALTS", then the cases it gets wrong are precisely the cases
that don't halt. That's interesting, as there is a simple proof that
there is no TM that can determine just those cases [tho' there are
TMs that determine supersets of them]. Perhaps that's not quite what
you meant?

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Belliss

On Monday, 21 June 2021 at 10:47:53 UTC+1, Andy Walker wrote:
> On 21/06/2021 00:10, Ben Bacarisse wrote:
> > [...] I don't
> > think it's obvious that the cases any one TM gets wrong are going to be
> > interesting. This may be a case where I'd change my mind when someone
> > comes up with a definition and it just turns out to be interesting in
> > some as yet unforeseen sense, but I can't see that happening right now
> > (as is to be expected of unforeseen occurrences).
> If we take the "one TM" to be a TM that always halts with the
> answer "HALTS", then the cases it gets wrong are precisely the cases
> that don't halt. That's interesting, as there is a simple proof that
> there is no TM that can determine just those cases [tho' there are
> TMs that determine supersets of them]. Perhaps that's not quite what
> you meant?
>
There seems to be a misunderstanding here.
The idea is that you have a three state decider - halts, non-halting and
"don't know"
If you insist that a Turing machine must "accept or reject" and do nothing
else, you need two machines, one which calculates the "don't know"s.

You can write trivial deciders which adhere to this system. The question
is whether you can define the "don't know" s in an interesting way.

Andy Walker <anw@cuboid.co.uk> writes:

> On 21/06/2021 00:10, Ben Bacarisse wrote:
>> [...] I don't
>> think it's obvious that the cases any one TM gets wrong are going to be
>> interesting. This may be a case where I'd change my mind when someone
>> comes up with a definition and it just turns out to be interesting in
>> some as yet unforeseen sense, but I can't see that happening right now
>> (as is to be expected of unforeseen occurrences).
>
> If we take the "one TM" to be a TM that always halts with the
> answer "HALTS", then the cases it gets wrong are precisely the cases
> that don't halt. That's interesting, as there is a simple proof that
> there is no TM that can determine just those cases [tho' there are
> TMs that determine supersets of them]. Perhaps that's not quite what
> you meant?

Yup. That's not what I meant by interesting. Malcolm seems to think
there may be some as yet unidentified set that would be worth
categorising.

--
Ben.

On 6/21/2021 5:10 AM, Malcolm McLean wrote:
> On Monday, 21 June 2021 at 10:47:53 UTC+1, Andy Walker wrote:
>> On 21/06/2021 00:10, Ben Bacarisse wrote:
>>> [...] I don't
>>> think it's obvious that the cases any one TM gets wrong are going to be
>>> interesting. This may be a case where I'd change my mind when someone
>>> comes up with a definition and it just turns out to be interesting in
>>> some as yet unforeseen sense, but I can't see that happening right now
>>> (as is to be expected of unforeseen occurrences).
>> If we take the "one TM" to be a TM that always halts with the
>> answer "HALTS", then the cases it gets wrong are precisely the cases
>> that don't halt. That's interesting, as there is a simple proof that
>> there is no TM that can determine just those cases [tho' there are
>> TMs that determine supersets of them]. Perhaps that's not quite what
>> you meant?
>>
> There seems to be a misunderstanding here.
> The idea is that you have a three state decider - halts, non-halting and
> "don't know"
> If you insist that a Turing machine must "accept or reject" and do nothing
> else, you need two machines, one which calculates the "don't know"s.
>
> You can write trivial deciders which adhere to this system. The question
> is whether you can define the "don't know" s in an interesting way.
>

I made the don't knows obsolete years ago.
https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ

--
Copyright 2021 Pete Olcott

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

On 6/21/2021 4:47 AM, Andy Walker wrote:
> On 21/06/2021 00:10, Ben Bacarisse wrote:
>> [...] I don't
>> think it's obvious that the cases any one TM gets wrong are going to be
>> interesting.  This may be a case where I'd change my mind when someone
>> comes up with a definition and it just turns out to be interesting in
>> some as yet unforeseen sense, but I can't see that happening right now
>> (as is to be expected of unforeseen occurrences).
>
>     If we take the "one TM" to be a TM that always halts with the
> answer "HALTS", then the cases it gets wrong are precisely the cases
> that don't halt.  That's interesting, as there is a simple proof that
> there is no TM that can determine just those cases [tho' there are
> TMs that determine supersets of them].  Perhaps that's not quite what
> you meant?
>

// Simplified Linz Ĥ (Linz:1990:319)
void P(u32 x)
{ u32 Input_Halts = H(x, x);
if (Input_Halts)
HERE: goto HERE;
}

int main()
{ u32 Input_Halts = H((u32)P, (u32)P);
Output("Input_Halts = ", Input_Halts);
}

In the above case no instance of P ever sees any return value from H.

Halting problem undecidability and infinitely nested simulation

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

--
Copyright 2021 Pete Olcott

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

On 6/21/21 9:46 AM, olcott wrote:
> On 6/21/2021 4:47 AM, Andy Walker wrote:
>> On 21/06/2021 00:10, Ben Bacarisse wrote:
>>> [...] I don't
>>> think it's obvious that the cases any one TM gets wrong are going to be
>>> interesting.  This may be a case where I'd change my mind when someone
>>> comes up with a definition and it just turns out to be interesting in
>>> some as yet unforeseen sense, but I can't see that happening right now
>>> (as is to be expected of unforeseen occurrences).
>>
>>      If we take the "one TM" to be a TM that always halts with the
>> answer "HALTS", then the cases it gets wrong are precisely the cases
>> that don't halt.  That's interesting, as there is a simple proof that
>> there is no TM that can determine just those cases [tho' there are
>> TMs that determine supersets of them].  Perhaps that's not quite what
>> you meant?
>>
>
> // Simplified Linz Ĥ (Linz:1990:319)
> void P(u32 x)
> {
>   u32 Input_Halts = H(x, x);
>   if (Input_Halts)
>     HERE: goto HERE;
> }
>
> int main()
> {
>   u32 Input_Halts = H((u32)P, (u32)P);
>   Output("Input_Halts = ", Input_Halts);
> }
>
> In the above case no instance of P ever sees any return value from H.
>
> Halting problem undecidability and infinitely nested simulation
>
> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
>
>
>

Only because H make a mistake and does try to find out what really happens.

Change main to:

int main()
{ P(9u32)P);
}

and the P that main calls DOES get the return value from H (or you syste
is proved to be fradulent) and then halt and H is proved wrong.

Since this is the machine that the Halting Problem is asking about, that
is the important one.

On 6/21/2021 6:48 PM, Richard Damon wrote:
> On 6/21/21 9:46 AM, olcott wrote:
>> On 6/21/2021 4:47 AM, Andy Walker wrote:
>>> On 21/06/2021 00:10, Ben Bacarisse wrote:
>>>> [...] I don't
>>>> think it's obvious that the cases any one TM gets wrong are going to be
>>>> interesting.  This may be a case where I'd change my mind when someone
>>>> comes up with a definition and it just turns out to be interesting in
>>>> some as yet unforeseen sense, but I can't see that happening right now
>>>> (as is to be expected of unforeseen occurrences).
>>>
>>>      If we take the "one TM" to be a TM that always halts with the
>>> answer "HALTS", then the cases it gets wrong are precisely the cases
>>> that don't halt.  That's interesting, as there is a simple proof that
>>> there is no TM that can determine just those cases [tho' there are
>>> TMs that determine supersets of them].  Perhaps that's not quite what
>>> you meant?
>>>
>>
>> // Simplified Linz Ĥ (Linz:1990:319)
>> void P(u32 x)
>> {
>>   u32 Input_Halts = H(x, x);
>>   if (Input_Halts)
>>     HERE: goto HERE;
>> }
>>
>> int main()
>> {
>>   u32 Input_Halts = H((u32)P, (u32)P);
>>   Output("Input_Halts = ", Input_Halts);
>> }
>>
>> In the above case no instance of P ever sees any return value from H.
>>
>> Halting problem undecidability and infinitely nested simulation
>>
>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
>>
>>
>>
>
> Only because H make a mistake and does try to find out what really happens.
>
> Change main to:
>
> int main()
> {
> P(u32)P);
> }
>
> and the P that main calls DOES get the return value from H (or you syste
> is proved to be fradulent) and then halt and H is proved wrong.
>

// Simplified Linz Ĥ (Linz:1990:319)
void P(u32 x)
{ u32 Input_Halts = H(x, x);
if (Input_Halts)
HERE: goto HERE;
}

Whenever P calls H(P,P) H must abort its simulation of P. The above
computation P(P) calls H(P,P) which is the first invocation of an
infinite sequence of invocations.

Everyone that is not dumber than a box of rocks knows that when any
invocation of an infinite sequence of invocations is terminated then the
entire sequence halts.

In the computation P(P) the third element of the infinite sequence of
invocations is terminated.

> Since this is the machine that the Halting Problem is asking about, that
> is the important one.
>

--
Copyright 2021 Pete Olcott

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

On 6/21/21 8:00 PM, olcott wrote:
> On 6/21/2021 6:48 PM, Richard Damon wrote:
>> On 6/21/21 9:46 AM, olcott wrote:
>>> On 6/21/2021 4:47 AM, Andy Walker wrote:
>>>> On 21/06/2021 00:10, Ben Bacarisse wrote:
>>>>> [...] I don't
>>>>> think it's obvious that the cases any one TM gets wrong are going
>>>>> to be
>>>>> interesting.  This may be a case where I'd change my mind when someone
>>>>> comes up with a definition and it just turns out to be interesting in
>>>>> some as yet unforeseen sense, but I can't see that happening right now
>>>>> (as is to be expected of unforeseen occurrences).
>>>>
>>>>       If we take the "one TM" to be a TM that always halts with the
>>>> answer "HALTS", then the cases it gets wrong are precisely the cases
>>>> that don't halt.  That's interesting, as there is a simple proof that
>>>> there is no TM that can determine just those cases [tho' there are
>>>> TMs that determine supersets of them].  Perhaps that's not quite what
>>>> you meant?
>>>>
>>>
>>> // Simplified Linz Ĥ (Linz:1990:319)
>>> void P(u32 x)
>>> {
>>>    u32 Input_Halts = H(x, x);
>>>    if (Input_Halts)
>>>      HERE: goto HERE;
>>> }
>>>
>>> int main()
>>> {
>>>    u32 Input_Halts = H((u32)P, (u32)P);
>>>    Output("Input_Halts = ", Input_Halts);
>>> }
>>>
>>> In the above case no instance of P ever sees any return value from H.
>>>
>>> Halting problem undecidability and infinitely nested simulation
>>>
>>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
>>>
>>>
>>>
>>>
>>
>> Only because H make a mistake and does try to find out what really
>> happens.
>>
>> Change main to:
>>
>> int main()
>> {
>>      P(u32)P);
>> }
>>
>> and the P that main calls DOES get the return value from H (or you syste
>> is proved to be fradulent) and then halt and H is proved wrong.
>>
>
> // Simplified Linz Ĥ (Linz:1990:319)
> void P(u32 x)
> {
>   u32 Input_Halts = H(x, x);
>   if (Input_Halts)
>     HERE: goto HERE;
> }
>
> Whenever P calls H(P,P) H must abort its simulation of P. The above
> computation P(P) calls H(P,P) which is the first invocation of an
> infinite sequence of invocations.
>
> Everyone that is not dumber than a box of rocks knows that when any
> invocation of an infinite sequence of invocations is terminated then the
> entire sequence halts.
>
> In the computation P(P) the third element of the infinite sequence of
> invocations is terminated.

Right, H aborts it SIMULATION of P. The first P is NOT a SIMULATION,
just the second one (3rd layer of 'call' sequence), so H will return its
answer to the non-simulation P and that P halts.

Thus P(P) is a Halting Computation.

The Question is whether P(P) is a Halting Computation or not. It Halts,
H says it doesn't. H is wrong. Simple and obvious to everyone with a
brain which seems to exclude you.

>
>
>> Since this is the machine that the Halting Problem is asking about, that
>> is the important one.
>>
>
>