Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #24583 > unrolled thread

A non-halting decider is defined

Started byolcott <NoOne@NoWhere.com>
First post2020-10-28 18:43 -0500
Last post2020-11-12 14:59 -0600
Articles 20 on this page of 26 — 9 participants

Back to article view | Back to comp.theory


Contents

  A non-halting decider is defined olcott <NoOne@NoWhere.com> - 2020-10-28 18:43 -0500
    Re: Stop crossposting you imbecil spammer (Re: A non-halting decider is defined Mostowski Collapse <janburse@fastmail.fm> - 2020-10-29 19:40 +0100
    Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 11:06 -0600
      Re: A non-halting decider is defined [ 2020-11-11 version ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-11 18:11 +0000
        Re: A non-halting decider is defined [ 2020-11-11 version ] David Kleinecke <dkleinecke@gmail.com> - 2020-11-11 10:59 -0800
          Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 13:08 -0600
          Re: A non-halting decider is defined [ 2020-11-11 version ] Richard Damon <Richard@Damon-Family.org> - 2020-11-11 15:29 -0500
            Re: A non-halting decider is defined [ 2020-11-11 version ] David Kleinecke <dkleinecke@gmail.com> - 2020-11-11 13:00 -0800
              Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 15:56 -0600
              Re: A non-halting decider is defined [ 2020-11-11 version ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-11 22:01 +0000
                Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 17:48 -0600
                  Re: A non-halting decider is defined [ 2020-11-11 version ] Jeff Barnett <jbb@notatt.com> - 2020-11-11 17:33 -0700
                  Re: A non-halting decider is defined [ 2020-11-11 version ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-12 02:02 +0000
                Re: A non-halting decider is defined [ 2020-11-11 version ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-11 23:53 +0000
                  Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 18:04 -0600
                    Re: A non-halting decider is defined [ 2020-11-11 version ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-12 01:00 +0000
                      Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 19:16 -0600
                Re: A non-halting decider is defined [ 2020-11-11 version ] Richard Damon <Richard@Damon-Family.org> - 2020-11-11 19:00 -0500
                  Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 18:11 -0600
                    Re: A non-halting decider is defined [ 2020-11-11 version ] Richard Damon <Richard@Damon-Family.org> - 2020-11-11 20:44 -0500
                      Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 19:52 -0600
                        Re: A non-halting decider is defined [ 2020-11-11 version ] Richard Damon <Richard@Damon-Family.org> - 2020-11-11 21:06 -0500
                Re: A non-halting decider is defined [ count-example? ] olcott <NoOne@NoWhere.com> - 2020-11-14 08:09 -0600
    Re: A non-halting decider is defined Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-11-12 18:36 +0000
      Re: A non-halting decider is defined Sjouke Burry <burrynulnulfour@ppllaanneett.nnll> - 2020-11-12 21:37 +0100
        Re: A non-halting decider is defined olcott <NoOne@NoWhere.com> - 2020-11-12 14:59 -0600

Page 1 of 2  [1] 2  Next page →


#24583 — A non-halting decider is defined

Fromolcott <NoOne@NoWhere.com>
Date2020-10-28 18:43 -0500
SubjectA non-halting decider is defined
Message-ID<pa-dnZ4DVImQnwfCnZ2dnUU7-e_NnZ2d@giganews.com>
Intuitively, a decider should be a Turing machine that given an input, 
halts and either accepts or rejects, relaying its answer in one of many 
equivalent ways, such as halting at an ACCEPT or REJECT state, or 
leaving its answer on the output tape.Yuval Filmus

https://cs.stackexchange.com/questions/84433/what-is-decider

Yuval Filmus top 0.04% overall Assistant Professor in the Department of 
Computer Science at the Technion.

A non-halting decider can be defined that always Accepts NON_HALTING 
input and Rejects HALTING input as follows:

The NON_HALTING decider UTM executes its subordinate UTM one state 
transition at a time until it detects non-halting behavior or its 
subordinate UTM has terminated normally.

If the halt decider UTM detects non-halting behavior of its subordinate 
UTM it simply stops executing the subordinate and transitions to its own 
final state of NON_TERMINATING_BEHAVIOR_DETECTED.

If the subordinate UTM terminates normally the halt decider UTM 
transitions to its own final state of SUBORDINATE_HAS_TERMINATED.






-- 
Copyright 2020 Pete Olcott

[toc] | [next] | [standalone]


#24634 — Re: Stop crossposting you imbecil spammer (Re: A non-halting decider is defined

FromMostowski Collapse <janburse@fastmail.fm>
Date2020-10-29 19:40 +0100
SubjectRe: Stop crossposting you imbecil spammer (Re: A non-halting decider is defined
Message-ID<rnf2af$u35$2@solani.org>
In reply to#24583
For gods sacke stop cross posting on 4 newsgroups.

Especially comp.lang.prolog doesn't make much sense.

RAM/RASP is probably best housed on comp.theory.

olcott schrieb:
> I am a brainless mud turtle 
> 

[toc] | [prev] | [next] | [standalone]


#25133 — Re: A non-halting decider is defined [ 2020-11-11 version ]

Fromolcott <NoOne@NoWhere.com>
Date2020-11-11 11:06 -0600
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<a8CdnUBfE5qVhzHCnZ2dnUU7-dPNnZ2d@giganews.com>
In reply to#24583
On 10/28/2020 6:43 PM, olcott wrote:
> Intuitively, a decider should be a Turing machine that given an input, 
> halts and either accepts or rejects, relaying its answer in one of many 
> equivalent ways, such as halting at an ACCEPT or REJECT state, or 
> leaving its answer on the output tape.Yuval Filmus
> 
> https://cs.stackexchange.com/questions/84433/what-is-decider
> 
> Yuval Filmus top 0.04% overall Assistant Professor in the Department of 
> Computer Science at the Technion.
> 
> A non-halting decider can be defined that always Accepts NON_HALTING 
> input and Rejects HALTING input as follows:
> 
> The NON_HALTING decider UTM executes its subordinate UTM one state 
> transition at a time until it detects non-halting behavior or its 
> subordinate UTM has terminated normally.
> 
> If the halt decider UTM detects non-halting behavior of its subordinate 
> UTM it simply stops executing the subordinate and transitions to its own 
> final state of NON_TERMINATING_BEHAVIOR_DETECTED.
> 
> If the subordinate UTM terminates normally the halt decider UTM 
> transitions to its own final state of SUBORDINATE_HAS_TERMINATED.

// Simplified version of Linz H_Hat DOES NOT copy itself
01 void H_Hat(u32 P)  // (bottom of page 319)
02 {
03   if (H(P, P))
04     HERE: goto HERE;
05   else
06     HALT
07 }

// Linz H with some of the ⊢* states shown
08 bool H(u32 P, u32 I)  // Page 318
09 {
10   bool Halted  = false;
11   bool Aborted = false;
12   while (!Halted && !Aborted)
13   {
14     Halted  = DebugStep(P, I);
15     Aborted = Needs_To_Be_Aborted();
16   }
17   return !Aborted;
18 }

http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

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

When-so-ever a halt decider correctly determines that its input would 
never halt unless forced to halt by this halt decider this halt decider 
has made a correct not-halting determination.

Unless H forces its input to halt: H(H_Hat, H_Hat) its first parameter 
specifies infinite recursion at its line 03.

NEW MATERIAL ADDED HERE

int main()
   H_Hat(H_Hat);

H_Hat(H_Hat) calls H(H_Hat, H_Hat) that decides that its first parameter 
(also the parameter to H_Hat) would never halt unless the halt decider 
forces it to halt. The execution trace proves that this is true.

H_Hat was intentionally designed to do the opposite of whatever the halt 
decider decides to thwart a correct halting decision. The halt decider 
got smarter and its halting decision is no longer thwarted.

The decision of every decider can only be correctly measured against its 
input.
The question is did the decider meet its own criterion measure for its 
input?

When the criterion measure of a halt decider is:
Does the input have to be forced to stop to prevent its infinite execution?

And the input does have to be forced to stop to prevent its infinite 
execution.

Then the halt decider necessarily made a correct not-halting decision.

int main()
{
   H_Hat(H_Hat);
   H(H_Hat, H_Hat);
}

In both of the above two cases the input must be forced to halt by the 
halt decider or it would never halt.

-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#25137 — Re: A non-halting decider is defined [ 2020-11-11 version ]

FromMike Terry <news.dead.person.stones@darjeeling.plus.com>
Date2020-11-11 18:11 +0000
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<tKednXr4xevQtDHCnZ2dnUU78T3NnZ2d@brightview.co.uk>
In reply to#25133
On 11/11/2020 17:06, olcott wrote:

<.. snip content already addressed many times in other posts ..>>

 > NEW MATERIAL ADDED HERE

<.. snip content already addressed many times in other posts ..>>


Please stop spamming this newsgroup.

Mike.

[toc] | [prev] | [next] | [standalone]


#25138 — Re: A non-halting decider is defined [ 2020-11-11 version ]

FromDavid Kleinecke <dkleinecke@gmail.com>
Date2020-11-11 10:59 -0800
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<1904ff20-b029-4ca6-89b9-615f5984e00do@googlegroups.com>
In reply to#25137
On Wednesday, November 11, 2020 at 10:11:29 AM UTC-8, Mike Terry wrote:
> On 11/11/2020 17:06, olcott wrote:
> 
> <.. snip content already addressed many times in other posts ..>>
> 
>  > NEW MATERIAL ADDED HERE
> 
> <.. snip content already addressed many times in other posts ..>>
> 
> 
> Please stop spamming this newsgroup.
> 
> Mike.

I have been following this argument for the laughs. But they
have been few and far between. 

One thing I don't understand: Linz defines H as any halt
decider - what gives anyone the right to write code for
it?

[toc] | [prev] | [next] | [standalone]


#25139 — Re: A non-halting decider is defined [ 2020-11-11 version ]

Fromolcott <NoOne@NoWhere.com>
Date2020-11-11 13:08 -0600
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<JqGdnWcqzIcgqzHCnZ2dnUU7-QHNnZ2d@giganews.com>
In reply to#25138
On 11/11/2020 12:59 PM, David Kleinecke wrote:
> On Wednesday, November 11, 2020 at 10:11:29 AM UTC-8, Mike Terry wrote:
>> On 11/11/2020 17:06, olcott wrote:
>>
>> <.. snip content already addressed many times in other posts ..>>
>>
>>   > NEW MATERIAL ADDED HERE
>>
>> <.. snip content already addressed many times in other posts ..>>
>>
>>
>> Please stop spamming this newsgroup.
>>
>> Mike.
> 
> I have been following this argument for the laughs. But they
> have been few and far between.
> 
> One thing I don't understand: Linz defines H as any halt
> decider - what gives anyone the right to write code for
> it?
> 

The ⊢* wildcard state transitions specified as an aspect of the Linz 
definition of H on page 318 expressly allow for unlimited variations 
that otherwise meet the rest of the spec.

http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

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


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#25143 — Re: A non-halting decider is defined [ 2020-11-11 version ]

FromRichard Damon <Richard@Damon-Family.org>
Date2020-11-11 15:29 -0500
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<4RXqH.261071$d95.207052@fx06.iad>
In reply to#25138
On 11/11/20 1:59 PM, David Kleinecke wrote:
> On Wednesday, November 11, 2020 at 10:11:29 AM UTC-8, Mike Terry wrote:
>> On 11/11/2020 17:06, olcott wrote:
>>
>> <.. snip content already addressed many times in other posts ..>>
>>
>>  > NEW MATERIAL ADDED HERE
>>
>> <.. snip content already addressed many times in other posts ..>>
>>
>>
>> Please stop spamming this newsgroup.
>>
>> Mike.
> 
> I have been following this argument for the laughs. But they
> have been few and far between. 
> 
> One thing I don't understand: Linz defines H as any halt
> decider - what gives anyone the right to write code for
> it?
> 

One way to disprove a non-existance proof is to provide an example of an
instance. Linz put forward that no halt decider can correctly decide his
H_Hat, which is built based on the halt decider being tested.

If you COULD create a specific halt decider that did correctly predict
what H_Hat would do, that would be a proof that Linz was wrong, and that
there must be something incorrect in his argument (though, because
Linz's argument is so basic, it likely means there is an error in your
decider).

This is the case, apparently with PO's 'proof'. He has tried changing
the wording of the definition a bit to something that sounds close
enough that it  might be good enough, bue then doesn't even match his
modified definition.

The problem is that he as taken a rule for detecting some types of
non-halting behavior as being true axiomatically when it is NOT true,
and throws up all sorts of smoke and mirrors to try to defend it, to the
point of believing his rule more than actual observations.

Yes, there is likely some very modified versions of the halting problem
that his proof could be used to show that Linz's proof doesn't apply to
that modified problem, but these are cases where we likely already know
that Linz doesn't apply (Linz only applies to UNIVERSAL halt detectors,
a halt detector that claims to be able to handle ANY Turing Machine). It
also turns out that those modified versions are also likely not very
interesting to actually want such a partial halt decider.

[toc] | [prev] | [next] | [standalone]


#25144 — Re: A non-halting decider is defined [ 2020-11-11 version ]

FromDavid Kleinecke <dkleinecke@gmail.com>
Date2020-11-11 13:00 -0800
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<81b63906-3740-4840-abe3-acfbec62209do@googlegroups.com>
In reply to#25143
On Wednesday, November 11, 2020 at 12:29:55 PM UTC-8, Richard Damon wrote:
> On 11/11/20 1:59 PM, David Kleinecke wrote:
> > On Wednesday, November 11, 2020 at 10:11:29 AM UTC-8, Mike Terry wrote:
> >> On 11/11/2020 17:06, olcott wrote:
> >>
> >> <.. snip content already addressed many times in other posts ..>>
> >>
> >>  > NEW MATERIAL ADDED HERE
> >>
> >> <.. snip content already addressed many times in other posts ..>>
> >>
> >>
> >> Please stop spamming this newsgroup.
> >>
> >> Mike.
> > 
> > I have been following this argument for the laughs. But they
> > have been few and far between. 
> > 
> > One thing I don't understand: Linz defines H as any halt
> > decider - what gives anyone the right to write code for
> > it?
> > 
> 
> One way to disprove a non-existance proof is to provide an example of an
> instance. Linz put forward that no halt decider can correctly decide his
> H_Hat, which is built based on the halt decider being tested.
> 
> If you COULD create a specific halt decider that did correctly predict
> what H_Hat would do, that would be a proof that Linz was wrong, and that
> there must be something incorrect in his argument (though, because
> Linz's argument is so basic, it likely means there is an error in your
> decider).
> 
> This is the case, apparently with PO's 'proof'. He has tried changing
> the wording of the definition a bit to something that sounds close
> enough that it  might be good enough, bue then doesn't even match his
> modified definition.
> 
> The problem is that he as taken a rule for detecting some types of
> non-halting behavior as being true axiomatically when it is NOT true,
> and throws up all sorts of smoke and mirrors to try to defend it, to the
> point of believing his rule more than actual observations.
> 
> Yes, there is likely some very modified versions of the halting problem
> that his proof could be used to show that Linz's proof doesn't apply to
> that modified problem, but these are cases where we likely already know
> that Linz doesn't apply (Linz only applies to UNIVERSAL halt detectors,
> a halt detector that claims to be able to handle ANY Turing Machine). It
> also turns out that those modified versions are also likely not very
> interesting to actually want such a partial halt decider.

OK - I think I grasp that.

But all that is required is to provide the code for a universal
halt detector in any old language. For a while now what proports
to be the code of such a detector has been posted and copied. It
is a joke - a wrapper around two programs that apparently someone
thinks do the work of a universal halt detector. 

[toc] | [prev] | [next] | [standalone]


#25145 — Re: A non-halting decider is defined [ 2020-11-11 version ]

Fromolcott <NoOne@NoWhere.com>
Date2020-11-11 15:56 -0600
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<68ednd1WjcNywDHCnZ2dnUU7-eXNnZ2d@giganews.com>
In reply to#25144
On 11/11/2020 3:00 PM, David Kleinecke wrote:
> On Wednesday, November 11, 2020 at 12:29:55 PM UTC-8, Richard Damon wrote:
>> On 11/11/20 1:59 PM, David Kleinecke wrote:
>>> On Wednesday, November 11, 2020 at 10:11:29 AM UTC-8, Mike Terry wrote:
>>>> On 11/11/2020 17:06, olcott wrote:
>>>>
>>>> <.. snip content already addressed many times in other posts ..>>
>>>>
>>>>   > NEW MATERIAL ADDED HERE
>>>>
>>>> <.. snip content already addressed many times in other posts ..>>
>>>>
>>>>
>>>> Please stop spamming this newsgroup.
>>>>
>>>> Mike.
>>>
>>> I have been following this argument for the laughs. But they
>>> have been few and far between.
>>>
>>> One thing I don't understand: Linz defines H as any halt
>>> decider - what gives anyone the right to write code for
>>> it?
>>>
>>
>> One way to disprove a non-existance proof is to provide an example of an
>> instance. Linz put forward that no halt decider can correctly decide his
>> H_Hat, which is built based on the halt decider being tested.
>>
>> If you COULD create a specific halt decider that did correctly predict
>> what H_Hat would do, that would be a proof that Linz was wrong, and that
>> there must be something incorrect in his argument (though, because
>> Linz's argument is so basic, it likely means there is an error in your
>> decider).
>>
>> This is the case, apparently with PO's 'proof'. He has tried changing
>> the wording of the definition a bit to something that sounds close
>> enough that it  might be good enough, bue then doesn't even match his
>> modified definition.
>>
>> The problem is that he as taken a rule for detecting some types of
>> non-halting behavior as being true axiomatically when it is NOT true,
>> and throws up all sorts of smoke and mirrors to try to defend it, to the
>> point of believing his rule more than actual observations.
>>
>> Yes, there is likely some very modified versions of the halting problem
>> that his proof could be used to show that Linz's proof doesn't apply to
>> that modified problem, but these are cases where we likely already know
>> that Linz doesn't apply (Linz only applies to UNIVERSAL halt detectors,
>> a halt detector that claims to be able to handle ANY Turing Machine). It
>> also turns out that those modified versions are also likely not very
>> interesting to actually want such a partial halt decider.
> 
> OK - I think I grasp that.
> 
> But all that is required is to provide the code for a universal
> halt detector in any old language. 

Not really. It is not my goal to write an infinitely long paper an 
eternity from now.

My goal is to show exactly how an x86 based virtual machine would decide 
halting on the x86 virtual machine form of the simplest counter-example 
of all of the halting problem proofs:

// Simplified version of Linz H_Hat DOES NOT copy itself
01 void H_Hat(u32 P)  // (bottom of page 319)
02 {
03   if (H(P, P))
04     HERE: goto HERE;
05   else
06     HALT
07 }

The x86utm based operating system that I wrote provides the means for 
this computation to be equivalent to its UTM based form. In other words 
(for all practical purposes) it executes UTMs that have the x86 language 
as their machine decription language.

> For a while now what proports
> to be the code of such a detector has been posted and copied. It
> is a joke - a wrapper around two programs that apparently someone
> thinks do the work of a universal halt detector.
> 

The x86utm operating system is currently mostly fully operational code. 
There is a little glitch when I execute function call to a function that 
executes its own caller in DebugStep() mode.

-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#25146 — Re: A non-halting decider is defined [ 2020-11-11 version ]

FromMike Terry <news.dead.person.stones@darjeeling.plus.com>
Date2020-11-11 22:01 +0000
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<3eKdnTKBs4GCwjHCnZ2dnUU78N-dnZ2d@brightview.co.uk>
In reply to#25144
On 11/11/2020 21:00, David Kleinecke wrote:
> On Wednesday, November 11, 2020 at 12:29:55 PM UTC-8, Richard Damon wrote:
>> On 11/11/20 1:59 PM, David Kleinecke wrote:
>>> On Wednesday, November 11, 2020 at 10:11:29 AM UTC-8, Mike Terry wrote:
>>>> On 11/11/2020 17:06, olcott wrote:
>>>>
>>>> <.. snip content already addressed many times in other posts ..>>
>>>>
>>>>  > NEW MATERIAL ADDED HERE
>>>>
>>>> <.. snip content already addressed many times in other posts ..>>
>>>>
>>>>
>>>> Please stop spamming this newsgroup.
>>>>
>>>> Mike.
>>>
>>> I have been following this argument for the laughs. But they
>>> have been few and far between.
>>>
>>> One thing I don't understand: Linz defines H as any halt
>>> decider - what gives anyone the right to write code for
>>> it?
>>>
>>
>> One way to disprove a non-existance proof is to provide an example of an
>> instance. Linz put forward that no halt decider can correctly decide his
>> H_Hat, which is built based on the halt decider being tested.
>>
>> If you COULD create a specific halt decider that did correctly predict
>> what H_Hat would do, that would be a proof that Linz was wrong, and that
>> there must be something incorrect in his argument (though, because
>> Linz's argument is so basic, it likely means there is an error in your
>> decider).
>>
>> This is the case, apparently with PO's 'proof'. He has tried changing
>> the wording of the definition a bit to something that sounds close
>> enough that it  might be good enough, bue then doesn't even match his
>> modified definition.
>>
>> The problem is that he as taken a rule for detecting some types of
>> non-halting behavior as being true axiomatically when it is NOT true,
>> and throws up all sorts of smoke and mirrors to try to defend it, to the
>> point of believing his rule more than actual observations.
>>
>> Yes, there is likely some very modified versions of the halting problem
>> that his proof could be used to show that Linz's proof doesn't apply to
>> that modified problem, but these are cases where we likely already know
>> that Linz doesn't apply (Linz only applies to UNIVERSAL halt detectors,
>> a halt detector that claims to be able to handle ANY Turing Machine). It
>> also turns out that those modified versions are also likely not very
>> interesting to actually want such a partial halt decider.
>
> OK - I think I grasp that.
>
> But all that is required is to provide the code for a universal
> halt detector in any old language. For a while now what proports
> to be the code of such a detector has been posted and copied. It
> is a joke - a wrapper around two programs that apparently someone
> thinks do the work of a universal halt detector.
>

PO is not claiming to have a /universal/ halt detector.

Linz's proof goes along these lines:
1)  Suppose H is a universal halt decider
2)  Construct from H this new program H^. [Details in Linz proof,
     but crucially, /every/ H has its own corresponding H^.]
3)  Then we show that due to the way H^ was constructed from H,
     H incorrectly decides halting for the input pair (H^, H^).
     [..contradicting (1)]

PO's argument was (is?) that he had his own H and an H^, where H^ is 
correctly derived from H according to Linz specifications, and yet his H 
/correctly/ decides the halting status of input (H^,H^).  /If/ that were 
possible, it would indicate faulty logic in the Linz proof, although PO 
has never been able to indicate which part of the proof reasoning is faulty.

So... his H is not meant (or required) to be a /universal/ halt decider, 
just a halt decider for its "nemesis" input (H^,H^).  He is trying to 
show that the /reasoning/ of the Linz proof must be faulty, because that 
reasoning gives a faulty conclusion in the one case of his H, H^ programs.

Of course, it does not, and PO has actually admitted that for his 
specific H,H^  :
a) H^(H^) halts,
b) H(H^,H^) decides "never halts".
[I.e. exactly in line with Linz proof]

He thinks he has invented his own (rather bizarre) new decider condition 
(let's call that PO-decision), with corresponding class of inputs C_PO 
which are the inputs (P,I) which satisfy his PO-decision.

Indeed, it's the case that for his code:
a) (H^,H^) is not in C_PO,
b) H(H^,H^) decides "not in C_PO".

I think he wants to claim this contradicts Linz, but of course, Linz 
says nothing whatsoever about C_PO or PO-condition, /even if PO could 
rigorously define the class/, which he's quite incapable of.  And there 
are many much less contorted conditions than PO-condition which /can/ be 
decided correctly, so it's all just hot air.  Not that PO can understand 
that...

Mike.

[toc] | [prev] | [next] | [standalone]


#25149 — Re: A non-halting decider is defined [ 2020-11-11 version ]

Fromolcott <NoOne@NoWhere.com>
Date2020-11-11 17:48 -0600
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<0cSdnZbejdHT5THCnZ2dnUU7-InNnZ2d@giganews.com>
In reply to#25146
On 11/11/2020 4:01 PM, Mike Terry wrote:
> On 11/11/2020 21:00, David Kleinecke wrote:
>> On Wednesday, November 11, 2020 at 12:29:55 PM UTC-8, Richard Damon 
>> wrote:
>>> On 11/11/20 1:59 PM, David Kleinecke wrote:
>>>> On Wednesday, November 11, 2020 at 10:11:29 AM UTC-8, Mike Terry wrote:
>>>>> On 11/11/2020 17:06, olcott wrote:
>>>>>
>>>>> <.. snip content already addressed many times in other posts ..>>
>>>>>
>>>>>  > NEW MATERIAL ADDED HERE
>>>>>
>>>>> <.. snip content already addressed many times in other posts ..>>
>>>>>
>>>>>
>>>>> Please stop spamming this newsgroup.
>>>>>
>>>>> Mike.
>>>>
>>>> I have been following this argument for the laughs. But they
>>>> have been few and far between.
>>>>
>>>> One thing I don't understand: Linz defines H as any halt
>>>> decider - what gives anyone the right to write code for
>>>> it?
>>>>
>>>
>>> One way to disprove a non-existance proof is to provide an example of an
>>> instance. Linz put forward that no halt decider can correctly decide his
>>> H_Hat, which is built based on the halt decider being tested.
>>>
>>> If you COULD create a specific halt decider that did correctly predict
>>> what H_Hat would do, that would be a proof that Linz was wrong, and that
>>> there must be something incorrect in his argument (though, because
>>> Linz's argument is so basic, it likely means there is an error in your
>>> decider).
>>>
>>> This is the case, apparently with PO's 'proof'. He has tried changing
>>> the wording of the definition a bit to something that sounds close
>>> enough that it  might be good enough, bue then doesn't even match his
>>> modified definition.
>>>
>>> The problem is that he as taken a rule for detecting some types of
>>> non-halting behavior as being true axiomatically when it is NOT true,
>>> and throws up all sorts of smoke and mirrors to try to defend it, to the
>>> point of believing his rule more than actual observations.
>>>
>>> Yes, there is likely some very modified versions of the halting problem
>>> that his proof could be used to show that Linz's proof doesn't apply to
>>> that modified problem, but these are cases where we likely already know
>>> that Linz doesn't apply (Linz only applies to UNIVERSAL halt detectors,
>>> a halt detector that claims to be able to handle ANY Turing Machine). It
>>> also turns out that those modified versions are also likely not very
>>> interesting to actually want such a partial halt decider.
>>
>> OK - I think I grasp that.
>>
>> But all that is required is to provide the code for a universal
>> halt detector in any old language. For a while now what proports
>> to be the code of such a detector has been posted and copied. It
>> is a joke - a wrapper around two programs that apparently someone
>> thinks do the work of a universal halt detector.
>>
> 
> PO is not claiming to have a /universal/ halt detector.
> 
> Linz's proof goes along these lines:
> 1)  Suppose H is a universal halt decider
> 2)  Construct from H this new program H^. [Details in Linz proof,
>      but crucially, /every/ H has its own corresponding H^.]
> 3)  Then we show that due to the way H^ was constructed from H,
>      H incorrectly decides halting for the input pair (H^, H^).
>      [..contradicting (1)]
> 
> PO's argument was (is?) that he had his own H and an H^, where H^ is 
> correctly derived from H according to Linz specifications, and yet his H 
> /correctly/ decides the halting status of input (H^,H^).  /If/ that were 
> possible, it would indicate faulty logic in the Linz proof, although PO 
> has never been able to indicate which part of the proof reasoning is 
> faulty.

You mean that I have NEVER indicated this more than fifty times:

The new criterion measure can not be fooled by an input that does the 
opposite of whatever the halt decider decides.

   Now we construct a new Turing machine D with H as a
   subroutine. This new TM calls H to determine what M
   does when the input to M is its own description <M>.
   Once D has determined this information, it does the
   opposite. That is, it rejects if M accepts and accepts
   if M does not accept. The following is a description of D.
   http://www.liarparadox.org/sipser_165.pdf

Sipser, Michael 1997. Introduction to the Theory of Computation. Boston: 
PWS Publishing Company (165-167)

When we change the criterion measure from:
(a) Does machine M halt on its input w?

To this new criterion measure:
(b) Does the simulation of the input M on input w have to be forced to 
stop to prevent its infinite execution?

Then an input that does the opposite of whatever the halt decider 
decides has no effect what-so-ever on this decision because the input 
was forced to stop before it could have any effect on this decision.


> So... his H is not meant (or required) to be a /universal/ halt decider, 
> just a halt decider for its "nemesis" input (H^,H^).  He is trying to 
> show that the /reasoning/ of the Linz proof must be faulty, because that 
> reasoning gives a faulty conclusion in the one case of his H, H^ programs.
> 
> Of course, it does not, and PO has actually admitted that for his 
> specific H,H^  :
> a) H^(H^) halts,
> b) H(H^,H^) decides "never halts".
> [I.e. exactly in line with Linz proof]

> He thinks he has invented his own (rather bizarre) new decider condition 
> (let's call that PO-decision), with corresponding class of inputs C_PO 
> which are the inputs (P,I) which satisfy his PO-decision.

The new criterion measure still divides inputs into halting and 
not-halting thus still directly relevant to the halting problem.

> Indeed, it's the case that for his code:
> a) (H^,H^) is not in C_PO,
> b) H(H^,H^) decides "not in C_PO".
> 
> I think he wants to claim this contradicts Linz, but of course, Linz 
> says nothing whatsoever about C_PO or PO-condition, /even if PO could 
> rigorously define the class/, which he's quite incapable of.  And there 
> are many much less contorted conditions than PO-condition which /can/ be 
> decided correctly, so it's all just hot air.  Not that PO can understand 
> that...
> 
> Mike.
> 


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#25156 — Re: A non-halting decider is defined [ 2020-11-11 version ]

FromJeff Barnett <jbb@notatt.com>
Date2020-11-11 17:33 -0700
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<rohvt9$afs$1@dont-email.me>
In reply to#25149
On 11/11/2020 4:48 PM, olcott wrote:
> On 11/11/2020 4:01 PM, Mike Terry wrote:
>> On 11/11/2020 21:00, David Kleinecke wrote:
>>> On Wednesday, November 11, 2020 at 12:29:55 PM UTC-8, Richard Damon 
>>> wrote:
>>>> On 11/11/20 1:59 PM, David Kleinecke wrote:
>>>>> On Wednesday, November 11, 2020 at 10:11:29 AM UTC-8, Mike Terry 
>>>>> wrote:
>>>>>> On 11/11/2020 17:06, olcott wrote:
>>>>>>
>>>>>> <.. snip content already addressed many times in other posts ..>>
>>>>>>
>>>>>>  > NEW MATERIAL ADDED HERE
>>>>>>
>>>>>> <.. snip content already addressed many times in other posts ..>>
>>>>>>
>>>>>>
>>>>>> Please stop spamming this newsgroup.
>>>>>>
>>>>>> Mike.
>>>>>
>>>>> I have been following this argument for the laughs. But they
>>>>> have been few and far between.
>>>>>
>>>>> One thing I don't understand: Linz defines H as any halt
>>>>> decider - what gives anyone the right to write code for
>>>>> it?
>>>>>
>>>>
>>>> One way to disprove a non-existance proof is to provide an example 
>>>> of an
>>>> instance. Linz put forward that no halt decider can correctly decide 
>>>> his
>>>> H_Hat, which is built based on the halt decider being tested.
>>>>
>>>> If you COULD create a specific halt decider that did correctly predict
>>>> what H_Hat would do, that would be a proof that Linz was wrong, and 
>>>> that
>>>> there must be something incorrect in his argument (though, because
>>>> Linz's argument is so basic, it likely means there is an error in your
>>>> decider).
>>>>
>>>> This is the case, apparently with PO's 'proof'. He has tried changing
>>>> the wording of the definition a bit to something that sounds close
>>>> enough that it  might be good enough, bue then doesn't even match his
>>>> modified definition.
>>>>
>>>> The problem is that he as taken a rule for detecting some types of
>>>> non-halting behavior as being true axiomatically when it is NOT true,
>>>> and throws up all sorts of smoke and mirrors to try to defend it, to 
>>>> the
>>>> point of believing his rule more than actual observations.
>>>>
>>>> Yes, there is likely some very modified versions of the halting problem
>>>> that his proof could be used to show that Linz's proof doesn't apply to
>>>> that modified problem, but these are cases where we likely already know
>>>> that Linz doesn't apply (Linz only applies to UNIVERSAL halt detectors,
>>>> a halt detector that claims to be able to handle ANY Turing 
>>>> Machine). It
>>>> also turns out that those modified versions are also likely not very
>>>> interesting to actually want such a partial halt decider.
>>>
>>> OK - I think I grasp that.
>>>
>>> But all that is required is to provide the code for a universal
>>> halt detector in any old language. For a while now what proports
>>> to be the code of such a detector has been posted and copied. It
>>> is a joke - a wrapper around two programs that apparently someone
>>> thinks do the work of a universal halt detector.
>>>
>>
>> PO is not claiming to have a /universal/ halt detector.
>>
>> Linz's proof goes along these lines:
>> 1)  Suppose H is a universal halt decider
>> 2)  Construct from H this new program H^. [Details in Linz proof,
>>      but crucially, /every/ H has its own corresponding H^.]
>> 3)  Then we show that due to the way H^ was constructed from H,
>>      H incorrectly decides halting for the input pair (H^, H^).
>>      [..contradicting (1)]
>>
>> PO's argument was (is?) that he had his own H and an H^, where H^ is 
>> correctly derived from H according to Linz specifications, and yet his 
>> H /correctly/ decides the halting status of input (H^,H^).  /If/ that 
>> were possible, it would indicate faulty logic in the Linz proof, 
>> although PO has never been able to indicate which part of the proof 
>> reasoning is faulty.
> 
> You mean that I have NEVER indicated this more than fifty times:
> 
> The new criterion measure can not be fooled by an input that does the 
> opposite of whatever the halt decider decides.
> 
>    Now we construct a new Turing machine D with H as a
>    subroutine. This new TM calls H to determine what M
>    does when the input to M is its own description <M>.
>    Once D has determined this information, it does the
>    opposite. That is, it rejects if M accepts and accepts
>    if M does not accept. The following is a description of D.
>    http://www.liarparadox.org/sipser_165.pdf
> 
> Sipser, Michael 1997. Introduction to the Theory of Computation. Boston: 
> PWS Publishing Company (165-167)
> 
> When we change the criterion measure from:
> (a) Does machine M halt on its input w?
> 
> To this new criterion measure:
> (b) Does the simulation of the input M on input w have to be forced to 
> stop to prevent its infinite execution?
> 
> Then an input that does the opposite of whatever the halt decider 
> decides has no effect what-so-ever on this decision because the input 
> was forced to stop before it could have any effect on this decision.
> 
> 
>> So... his H is not meant (or required) to be a /universal/ halt 
>> decider, just a halt decider for its "nemesis" input (H^,H^).  He is 
>> trying to show that the /reasoning/ of the Linz proof must be faulty, 
>> because that reasoning gives a faulty conclusion in the one case of 
>> his H, H^ programs.
>>
>> Of course, it does not, and PO has actually admitted that for his 
>> specific H,H^  :
>> a) H^(H^) halts,
>> b) H(H^,H^) decides "never halts".
>> [I.e. exactly in line with Linz proof]
> 
>> He thinks he has invented his own (rather bizarre) new decider 
>> condition (let's call that PO-decision), with corresponding class of 
>> inputs C_PO which are the inputs (P,I) which satisfy his PO-decision.
> 
> The new criterion measure still divides inputs into halting and 
> not-halting thus still directly relevant to the halting problem.
> 
>> Indeed, it's the case that for his code:
>> a) (H^,H^) is not in C_PO,
>> b) H(H^,H^) decides "not in C_PO".
>>
>> I think he wants to claim this contradicts Linz, but of course, Linz 
>> says nothing whatsoever about C_PO or PO-condition, /even if PO could 
>> rigorously define the class/, which he's quite incapable of.  And 
>> there are many much less contorted conditions than PO-condition which 
>> /can/ be decided correctly, so it's all just hot air.  Not that PO can 
>> understand that...
>>
>> Mike.

Thanks. You have just convinced me that Mike is correct as in "Not that 
PO can understand that..." Have you considered going back in student 
mode for a while? Even if you had stumbled over some valid criticism of 
the conventional wisdom, you would convince no one. Your terminology, 
bad coding, lack of memory of what you have said, and your thirst for 
recognition blot out any possibility of positive feedback. How did you 
feel when Cooper made total sport of you by acting like a supporter? 
That's as close to positive feedback as your likely to get here without 
improving your education and your mind. Who knows, there might be a good 
idea in there or even a useful intelligent new thought but not in your 
current sorry state. Improve for your own good (and the good of the 
internet). Thanks for listening.
-- 
Jeff Barnett

[toc] | [prev] | [next] | [standalone]


#25169 — Re: A non-halting decider is defined [ 2020-11-11 version ]

FromMike Terry <news.dead.person.stones@darjeeling.plus.com>
Date2020-11-12 02:02 +0000
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<Bp-dncTtN9xaCjHCnZ2dnUU78RHNnZ2d@brightview.co.uk>
In reply to#25149
On 11/11/2020 23:48, olcott wrote:
> On 11/11/2020 4:01 PM, Mike Terry wrote:
>> On 11/11/2020 21:00, David Kleinecke wrote:
>>> On Wednesday, November 11, 2020 at 12:29:55 PM UTC-8, Richard Damon
>>> wrote:
>>>> On 11/11/20 1:59 PM, David Kleinecke wrote:
>>>>> On Wednesday, November 11, 2020 at 10:11:29 AM UTC-8, Mike Terry
>>>>> wrote:
>>>>>> On 11/11/2020 17:06, olcott wrote:
>>>>>>
>>>>>> <.. snip content already addressed many times in other posts ..>>
>>>>>>
>>>>>>  > NEW MATERIAL ADDED HERE
>>>>>>
>>>>>> <.. snip content already addressed many times in other posts ..>>
>>>>>>
>>>>>>
>>>>>> Please stop spamming this newsgroup.
>>>>>>
>>>>>> Mike.
>>>>>
>>>>> I have been following this argument for the laughs. But they
>>>>> have been few and far between.
>>>>>
>>>>> One thing I don't understand: Linz defines H as any halt
>>>>> decider - what gives anyone the right to write code for
>>>>> it?
>>>>>
>>>>
>>>> One way to disprove a non-existance proof is to provide an example
>>>> of an
>>>> instance. Linz put forward that no halt decider can correctly decide
>>>> his
>>>> H_Hat, which is built based on the halt decider being tested.
>>>>
>>>> If you COULD create a specific halt decider that did correctly predict
>>>> what H_Hat would do, that would be a proof that Linz was wrong, and
>>>> that
>>>> there must be something incorrect in his argument (though, because
>>>> Linz's argument is so basic, it likely means there is an error in your
>>>> decider).
>>>>
>>>> This is the case, apparently with PO's 'proof'. He has tried changing
>>>> the wording of the definition a bit to something that sounds close
>>>> enough that it  might be good enough, bue then doesn't even match his
>>>> modified definition.
>>>>
>>>> The problem is that he as taken a rule for detecting some types of
>>>> non-halting behavior as being true axiomatically when it is NOT true,
>>>> and throws up all sorts of smoke and mirrors to try to defend it, to
>>>> the
>>>> point of believing his rule more than actual observations.
>>>>
>>>> Yes, there is likely some very modified versions of the halting problem
>>>> that his proof could be used to show that Linz's proof doesn't apply to
>>>> that modified problem, but these are cases where we likely already know
>>>> that Linz doesn't apply (Linz only applies to UNIVERSAL halt detectors,
>>>> a halt detector that claims to be able to handle ANY Turing
>>>> Machine). It
>>>> also turns out that those modified versions are also likely not very
>>>> interesting to actually want such a partial halt decider.
>>>
>>> OK - I think I grasp that.
>>>
>>> But all that is required is to provide the code for a universal
>>> halt detector in any old language. For a while now what proports
>>> to be the code of such a detector has been posted and copied. It
>>> is a joke - a wrapper around two programs that apparently someone
>>> thinks do the work of a universal halt detector.
>>>
>>
>> PO is not claiming to have a /universal/ halt detector.
>>
>> Linz's proof goes along these lines:
>> 1)  Suppose H is a universal halt decider
>> 2)  Construct from H this new program H^. [Details in Linz proof,
>>      but crucially, /every/ H has its own corresponding H^.]
>> 3)  Then we show that due to the way H^ was constructed from H,
>>      H incorrectly decides halting for the input pair (H^, H^).
>>      [..contradicting (1)]
>>
>> PO's argument was (is?) that he had his own H and an H^, where H^ is
>> correctly derived from H according to Linz specifications, and yet his
>> H /correctly/ decides the halting status of input (H^,H^).  /If/ that
>> were possible, it would indicate faulty logic in the Linz proof,
>> although PO has never been able to indicate which part of the proof
>> reasoning is faulty.
>
> You mean that I have NEVER indicated this more than fifty times:

None of what you say next explains which reasoning step in Linz is 
faulty.  I don't think you understand the concept of proof!
>
> The new criterion measure can not be fooled by an input that does the
> opposite of whatever the halt decider decides.
>
>   Now we construct a new Turing machine D with H as a
>   subroutine. This new TM calls H to determine what M
>   does when the input to M is its own description <M>.
>   Once D has determined this information, it does the
>   opposite. That is, it rejects if M accepts and accepts
>   if M does not accept. The following is a description of D.
>   http://www.liarparadox.org/sipser_165.pdf
>
> Sipser, Michael 1997. Introduction to the Theory of Computation. Boston:
> PWS Publishing Company (165-167)
>
> When we change the criterion measure from:
> (a) Does machine M halt on its input w?
>
> To this new criterion measure:
> (b) Does the simulation of the input M on input w have to be forced to
> stop to prevent its infinite execution?
>
> Then an input that does the opposite of whatever the halt decider
> decides has no effect what-so-ever on this decision because the input
> was forced to stop before it could have any effect on this decision.

You see - none of the above explained what reasoning step is faulty in 
Linz proof.  It's like you're saying "Linz proof is valid - at least, I 
can't find any mistake in it.  But I think it's wrong, anyway!!"

If you had read my post properly you'd have seen that I explained what 
you're doing here.  Your "criterion (b) is what I called your 
PO-condition.  As I explained, PO-condition is simply not the same as 
halting, and so is of no relevance to Linz proof (or Sipser).

>
>
>> So... his H is not meant (or required) to be a /universal/ halt
>> decider, just a halt decider for its "nemesis" input (H^,H^).  He is
>> trying to show that the /reasoning/ of the Linz proof must be faulty,
>> because that reasoning gives a faulty conclusion in the one case of
>> his H, H^ programs.
>>
>> Of course, it does not, and PO has actually admitted that for his
>> specific H,H^  :
>> a) H^(H^) halts,
>> b) H(H^,H^) decides "never halts".
>> [I.e. exactly in line with Linz proof]
>
>> He thinks he has invented his own (rather bizarre) new decider
>> condition (let's call that PO-decision), with corresponding class of
>> inputs C_PO which are the inputs (P,I) which satisfy his PO-decision.
>
> The new criterion measure still divides inputs into halting and
> not-halting thus still directly relevant to the halting problem.
>

Wrong, as explained many times by many people.

Mike.

[toc] | [prev] | [next] | [standalone]


#25150 — Re: A non-halting decider is defined [ 2020-11-11 version ]

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2020-11-11 23:53 +0000
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<87k0urtpr5.fsf@bsb.me.uk>
In reply to#25146
Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

> On 11/11/2020 21:00, David Kleinecke wrote:
<cut>
>> But all that is required is to provide the code for a universal
>> halt detector in any old language. For a while now what proports
>> to be the code of such a detector has been posted and copied. It
>> is a joke - a wrapper around two programs that apparently someone
>> thinks do the work of a universal halt detector.
>>
>
> PO is not claiming to have a /universal/ halt detector.

Not so long ago:

  "The non-halting decider that I defined accepts any and all
  non-halting inputs and rejects any and all halting inputs."

That is a universal halt decider.  It's true that recent posts have
mentioned partial deciders, but he's never retracted it (as if!).

> Linz's proof goes along these lines:
> 1)  Suppose H is a universal halt decider
> 2)  Construct from H this new program H^. [Details in Linz proof,
>     but crucially, /every/ H has its own corresponding H^.]
> 3)  Then we show that due to the way H^ was constructed from H,
>     H incorrectly decides halting for the input pair (H^, H^).
>     [..contradicting (1)]

I wonder if PO would have wasted so much time if the proof had been
written differently.  As I am sure you know, step 1 is not needed.  You
can reason about any TM, M, and show that is does not compute the
halting function because either there is some i for which M(i) does not
terminate, or there is some i for which M(i) =/= halts(i).

In fact Linz shows this proof for historical reasons only.  Having
established, in the previous chapter, that there is a recursively
enumerable language that is not recursive, the halting theorem is proved
as a one-sentence corollary of that.  Unfortunately PO has not read the
book.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#25152 — Re: A non-halting decider is defined [ 2020-11-11 version ]

Fromolcott <NoOne@NoWhere.com>
Date2020-11-11 18:04 -0600
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<K6udnSQtUoWU4THCnZ2dnUU7-T3NnZ2d@giganews.com>
In reply to#25150
On 11/11/2020 5:53 PM, Ben Bacarisse wrote:
> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
> 
>> On 11/11/2020 21:00, David Kleinecke wrote:
> <cut>
>>> But all that is required is to provide the code for a universal
>>> halt detector in any old language. For a while now what proports
>>> to be the code of such a detector has been posted and copied. It
>>> is a joke - a wrapper around two programs that apparently someone
>>> thinks do the work of a universal halt detector.
>>>
>>
>> PO is not claiming to have a /universal/ halt detector.
> 
> Not so long ago:
> 
>    "The non-halting decider that I defined accepts any and all
>    non-halting inputs and rejects any and all halting inputs."
> 
> That is a universal halt decider.  It's true that recent posts have
> mentioned partial deciders, but he's never retracted it (as if!).
> 
>> Linz's proof goes along these lines:
>> 1)  Suppose H is a universal halt decider
>> 2)  Construct from H this new program H^. [Details in Linz proof,
>>      but crucially, /every/ H has its own corresponding H^.]
>> 3)  Then we show that due to the way H^ was constructed from H,
>>      H incorrectly decides halting for the input pair (H^, H^).
>>      [..contradicting (1)]
> 
> I wonder if PO would have wasted so much time if the proof had been
> written differently.  As I am sure you know, step 1 is not needed.  You
> can reason about any TM, M, and show that is does not compute the
> halting function because either there is some i for which M(i) does not
> terminate, or there is some i for which M(i) =/= halts(i).
> 
> In fact Linz shows this proof for historical reasons only.  Having
> established, in the previous chapter, that there is a recursively
> enumerable language that is not recursive, the halting theorem is proved
> as a one-sentence corollary of that.  Unfortunately PO has not read the
> book.
> 

If the conventional:
"Do the opposite of whatever the halt decider decides" **

trick is shown to be decidable, then what is left that shows that 
halting is undecidable?

** Now we construct a new Turing machine D with H as a
subroutine. This new TM calls H to determine what M
does when the input to M is its own description <M>.
Once D has determined this information, it does the
opposite. That is, it rejects if M accepts and accepts
if M does not accept. The following is a description of D.
http://www.liarparadox.org/sipser_165.pdf (Sipser 1997)

Sipser, Michael 1997. Introduction to the Theory of Computation. Boston: 
PWS Publishing Company (165-167)


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#25160 — Re: A non-halting decider is defined [ 2020-11-11 version ]

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2020-11-12 01:00 +0000
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<87tutvs824.fsf@bsb.me.uk>
In reply to#25152
olcott <NoOne@NoWhere.com> writes:

> On 11/11/2020 5:53 PM, Ben Bacarisse wrote:
>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>
>>> On 11/11/2020 21:00, David Kleinecke wrote:
>> <cut>
>>>> But all that is required is to provide the code for a universal
>>>> halt detector in any old language. For a while now what proports
>>>> to be the code of such a detector has been posted and copied. It
>>>> is a joke - a wrapper around two programs that apparently someone
>>>> thinks do the work of a universal halt detector.
>>>>
>>>
>>> PO is not claiming to have a /universal/ halt detector.
>>
>> Not so long ago:
>>
>>    "The non-halting decider that I defined accepts any and all
>>    non-halting inputs and rejects any and all halting inputs."
>>
>> That is a universal halt decider.  It's true that recent posts have
>> mentioned partial deciders, but he's never retracted it (as if!).
>>
>>> Linz's proof goes along these lines:
>>> 1)  Suppose H is a universal halt decider
>>> 2)  Construct from H this new program H^. [Details in Linz proof,
>>>      but crucially, /every/ H has its own corresponding H^.]
>>> 3)  Then we show that due to the way H^ was constructed from H,
>>>      H incorrectly decides halting for the input pair (H^, H^).
>>>      [..contradicting (1)]
>>
>> I wonder if PO would have wasted so much time if the proof had been
>> written differently.  As I am sure you know, step 1 is not needed.  You
>> can reason about any TM, M, and show that is does not compute the
>> halting function because either there is some i for which M(i) does not
>> terminate, or there is some i for which M(i) =/= halts(i).
>>
>> In fact Linz shows this proof for historical reasons only.  Having
>> established, in the previous chapter, that there is a recursively
>> enumerable language that is not recursive, the halting theorem is proved
>> as a one-sentence corollary of that.  Unfortunately PO has not read the
>> book.
>
> If the conventional:
> "Do the opposite of whatever the halt decider decides" **
>
> trick is shown to be decidable, then what is left that shows that
> halting is undecidable?

All the other proofs you have not read.  For example the tiny proof that
directly follows the pages of Linz you have obsessed about for so many
years.  And of course there is the proof via Rado's demonstration that
the BB function is not computable.

You have a real problem understanding the notion of a proof.  There were
dozens of published "proofs" of the four colour theorem, all of which
were shown to be wrong.  It's still a theorem, though, because there is
a valid proof of it.  Only one is needed no matter how many non-proofs
there are.

Hypotheticals aside, you remain wrong about the main point.  H gets
H(H_Hat, H_Hat) wrong because the answer conflicts with the nature of
the computation H_Hat(H_Hat).  Neither what your H "had to do", nor what
H_Hat "would do" were is ever so slightly different, make the wrong
answer right.

It's amazing that you keep going despite accepting the plain facts of
the matter: that H(H_Hat, H_Hat) is false and that H_Hat(H_Hat) is a
finite computation.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#25162 — Re: A non-halting decider is defined [ 2020-11-11 version ]

Fromolcott <NoOne@NoWhere.com>
Date2020-11-11 19:16 -0600
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<WvadnSvqfOVxETHCnZ2dnUU7-Y_NnZ2d@giganews.com>
In reply to#25160
On 11/11/2020 7:00 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 11/11/2020 5:53 PM, Ben Bacarisse wrote:
>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>
>>>> On 11/11/2020 21:00, David Kleinecke wrote:
>>> <cut>
>>>>> But all that is required is to provide the code for a universal
>>>>> halt detector in any old language. For a while now what proports
>>>>> to be the code of such a detector has been posted and copied. It
>>>>> is a joke - a wrapper around two programs that apparently someone
>>>>> thinks do the work of a universal halt detector.
>>>>>
>>>>
>>>> PO is not claiming to have a /universal/ halt detector.
>>>
>>> Not so long ago:
>>>
>>>     "The non-halting decider that I defined accepts any and all
>>>     non-halting inputs and rejects any and all halting inputs."
>>>
>>> That is a universal halt decider.  It's true that recent posts have
>>> mentioned partial deciders, but he's never retracted it (as if!).
>>>
>>>> Linz's proof goes along these lines:
>>>> 1)  Suppose H is a universal halt decider
>>>> 2)  Construct from H this new program H^. [Details in Linz proof,
>>>>       but crucially, /every/ H has its own corresponding H^.]
>>>> 3)  Then we show that due to the way H^ was constructed from H,
>>>>       H incorrectly decides halting for the input pair (H^, H^).
>>>>       [..contradicting (1)]
>>>
>>> I wonder if PO would have wasted so much time if the proof had been
>>> written differently.  As I am sure you know, step 1 is not needed.  You
>>> can reason about any TM, M, and show that is does not compute the
>>> halting function because either there is some i for which M(i) does not
>>> terminate, or there is some i for which M(i) =/= halts(i).
>>>
>>> In fact Linz shows this proof for historical reasons only.  Having
>>> established, in the previous chapter, that there is a recursively
>>> enumerable language that is not recursive, the halting theorem is proved
>>> as a one-sentence corollary of that.  Unfortunately PO has not read the
>>> book.
>>
>> If the conventional:
>> "Do the opposite of whatever the halt decider decides" **
>>
>> trick is shown to be decidable, then what is left that shows that
>> halting is undecidable?
> 
> All the other proofs you have not read.  For example the tiny proof that
> directly follows the pages of Linz you have obsessed about for so many
> years.  And of course there is the proof via Rado's demonstration that
> the BB function is not computable.
> 
> You have a real problem understanding the notion of a proof.  There were
> dozens of published "proofs" of the four colour theorem, all of which
> were shown to be wrong.  It's still a theorem, though, because there is
> a valid proof of it.  Only one is needed no matter how many non-proofs
> there are.
> 
> Hypotheticals aside, you remain wrong about the main point.  H gets
> H(H_Hat, H_Hat) wrong because the answer conflicts with the nature of
> the computation H_Hat(H_Hat).  Neither what your H "had to do", nor what
> H_Hat "would do" were is ever so slightly different, make the wrong
> answer right.


Can you see how H_Hat() is infinitely recursive now?

void H_Hat(u32 P)  // (bottom of page 319)
{
    if (DebugTrace(P, P))
      HERE: goto HERE;
    else
      HALT
}

// My earliest version of H
u32 DebugTrace(u32 N, u32 M)
{
   ((int(*)(u32))N)(M);
}

int main()
{
   u32 N = (u32)H_Hat;
   u32 M = (u32)H_Hat;
   DebugTrace(N, M);
}


This version has equivalent semantics:

// Linz H with some of the ⊢* states shown
08 bool H(u32 P, u32 I)  // Page 318
09 {
10   bool Halted  = false;
11   while (!Halted && !Aborted)
12     Halted  = DebugStep(P, I);
13   return !Aborted;
14 }

If H_Hat really is infinitely recursive and H determines that H_Hat is 
infinitely recursive then H is correct.

It is like asking the question: Are black cats black?

-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#25151 — Re: A non-halting decider is defined [ 2020-11-11 version ]

FromRichard Damon <Richard@Damon-Family.org>
Date2020-11-11 19:00 -0500
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<%W_qH.423599$Av7.406890@fx34.iad>
In reply to#25146
On 11/11/20 5:01 PM, Mike Terry wrote:

> PO is not claiming to have a /universal/ halt detector.
> 
> Linz's proof goes along these lines:
> 1)  Suppose H is a universal halt decider
> 2)  Construct from H this new program H^. [Details in Linz proof,
>     but crucially, /every/ H has its own corresponding H^.]
> 3)  Then we show that due to the way H^ was constructed from H,
>     H incorrectly decides halting for the input pair (H^, H^).
>     [..contradicting (1)]
> 
> PO's argument was (is?) that he had his own H and an H^, where H^ is
> correctly derived from H according to Linz specifications, and yet his H
> /correctly/ decides the halting status of input (H^,H^).  /If/ that were
> possible, it would indicate faulty logic in the Linz proof, although PO
> has never been able to indicate which part of the proof reasoning is
> faulty.
> 
> So... his H is not meant (or required) to be a /universal/ halt decider,
> just a halt decider for its "nemesis" input (H^,H^).  He is trying to
> show that the /reasoning/ of the Linz proof must be faulty, because that
> reasoning gives a faulty conclusion in the one case of his H, H^ programs.
> 
> Of course, it does not, and PO has actually admitted that for his
> specific H,H^  :
> a) H^(H^) halts,
> b) H(H^,H^) decides "never halts".
> [I.e. exactly in line with Linz proof]
> 
> He thinks he has invented his own (rather bizarre) new decider condition
> (let's call that PO-decision), with corresponding class of inputs C_PO
> which are the inputs (P,I) which satisfy his PO-decision.
> 
> Indeed, it's the case that for his code:
> a) (H^,H^) is not in C_PO,
> b) H(H^,H^) decides "not in C_PO".
> 
> I think he wants to claim this contradicts Linz, but of course, Linz
> says nothing whatsoever about C_PO or PO-condition, /even if PO could
> rigorously define the class/, which he's quite incapable of.  And there
> are many much less contorted conditions than PO-condition which /can/ be
> decided correctly, so it's all just hot air.  Not that PO can understand
> that...
> 
> Mike.
> 

The key thing is that to disprove Linz, you don't need to actually make
a real Universal Halt Decider, If you could make a Halt Decider, even if
it was partial, that could handle Linz's machine, you could show that
his proof is somehow flawed (if you could also show you answered the
Halting decision right for the Linz's case).

PO's problem is that he hasn't come up with a even partial Halt Decider
for Linz's case, but he is trying to rephrase the question to something
that seems equivalent (instead of detecting halting/non-halting, detect
halting/need to abort to avoid non-halting), which if the machine really
did NEED to abort, and without aborting it is guaranteed that the
machine would have gone on forever, while his decider still maintains
always finite execution, because then needing to abort would exactly
match non-halting.

The problem is that the condition he detects as a situation where he
needs to abort isn't actually a true need to abort. When you remove the
abort in the code running the test (while keeping the code being tested
its original version) the code WILL come to a halt, so the abort wasn't
actually needed.  He unsoundly changes the input program at the same
time as making the change in the test code to prove need, and in that
double modified code, the machine does go into an infinite loop, but
this loop is inside the decider, so the decider fails to meet its
requirements.

He seems so fixed that his method has to work, that he finds the need to
warp everything else in the system to try and make his point work, and
refuses to listen to anyone else.

[toc] | [prev] | [next] | [standalone]


#25153 — Re: A non-halting decider is defined [ 2020-11-11 version ]

Fromolcott <NoOne@NoWhere.com>
Date2020-11-11 18:11 -0600
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<LoSdnRJyo48x4DHCnZ2dnUU7-YXNnZ2d@giganews.com>
In reply to#25151
On 11/11/2020 6:00 PM, Richard Damon wrote:
> On 11/11/20 5:01 PM, Mike Terry wrote:
> 
>> PO is not claiming to have a /universal/ halt detector.
>>
>> Linz's proof goes along these lines:
>> 1)  Suppose H is a universal halt decider
>> 2)  Construct from H this new program H^. [Details in Linz proof,
>>      but crucially, /every/ H has its own corresponding H^.]
>> 3)  Then we show that due to the way H^ was constructed from H,
>>      H incorrectly decides halting for the input pair (H^, H^).
>>      [..contradicting (1)]
>>
>> PO's argument was (is?) that he had his own H and an H^, where H^ is
>> correctly derived from H according to Linz specifications, and yet his H
>> /correctly/ decides the halting status of input (H^,H^).  /If/ that were
>> possible, it would indicate faulty logic in the Linz proof, although PO
>> has never been able to indicate which part of the proof reasoning is
>> faulty.
>>
>> So... his H is not meant (or required) to be a /universal/ halt decider,
>> just a halt decider for its "nemesis" input (H^,H^).  He is trying to
>> show that the /reasoning/ of the Linz proof must be faulty, because that
>> reasoning gives a faulty conclusion in the one case of his H, H^ programs.
>>
>> Of course, it does not, and PO has actually admitted that for his
>> specific H,H^  :
>> a) H^(H^) halts,
>> b) H(H^,H^) decides "never halts".
>> [I.e. exactly in line with Linz proof]
>>
>> He thinks he has invented his own (rather bizarre) new decider condition
>> (let's call that PO-decision), with corresponding class of inputs C_PO
>> which are the inputs (P,I) which satisfy his PO-decision.
>>
>> Indeed, it's the case that for his code:
>> a) (H^,H^) is not in C_PO,
>> b) H(H^,H^) decides "not in C_PO".
>>
>> I think he wants to claim this contradicts Linz, but of course, Linz
>> says nothing whatsoever about C_PO or PO-condition, /even if PO could
>> rigorously define the class/, which he's quite incapable of.  And there
>> are many much less contorted conditions than PO-condition which /can/ be
>> decided correctly, so it's all just hot air.  Not that PO can understand
>> that...
>>
>> Mike.
>>
> 
> The key thing is that to disprove Linz, you don't need to actually make
> a real Universal Halt Decider, If you could make a Halt Decider, even if
> it was partial, that could handle Linz's machine, you could show that
> his proof is somehow flawed (if you could also show you answered the
> Halting decision right for the Linz's case).
> 
> PO's problem is that he hasn't come up with a even partial Halt Decider
> for Linz's case, but he is trying to rephrase the question to something
> that seems equivalent (instead of detecting halting/non-halting, detect
> halting/need to abort to avoid non-halting), which if the machine really
> did NEED to abort, and without aborting it is guaranteed that the
> machine would have gone on forever, while his decider still maintains
> always finite execution, because then needing to abort would exactly
> match non-halting.
> 
> The problem is that the condition he detects as a situation where he
> needs to abort isn't actually a true need to abort. When you remove the
> abort in the code running the test (while keeping the code being tested
> its original version) the code WILL come to a halt,

// Simplified version of Linz H_Hat DOES NOT copy itself
01 void H_Hat(u32 P)  // (bottom of page 319)
02 {
03   if (H(P, P))
04     HERE: goto HERE;
05   else
06     HALT
07 }

// Linz H with some of the ⊢* states shown
08 bool H(u32 P, u32 I)  // Page 318
09 {
10   bool Halted  = false;
11   bool Aborted = false;
12   while (!Halted && !Aborted)
13   {
14     Halted  = DebugStep(P, I);
15     Aborted = Needs_To_Be_Aborted();
16   }
17   return !Aborted;
18 }

int main()
   H_Hat(H_Hat);

If we remove line 15 H_Hat(H_Hat) executes forever because the input to 
H_Hat really must be aborted to prevent infinite execution.


>  so the abort wasn't
> actually needed.  He unsoundly changes the input program at the same
> time as making the change in the test code to prove need, and in that
> double modified code, the machine does go into an infinite loop, but
> this loop is inside the decider, so the decider fails to meet its
> requirements.
> 
> He seems so fixed that his method has to work, that he finds the need to
> warp everything else in the system to try and make his point work, and
> refuses to listen to anyone else.
> 


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#25167 — Re: A non-halting decider is defined [ 2020-11-11 version ]

FromRichard Damon <Richard@Damon-Family.org>
Date2020-11-11 20:44 -0500
SubjectRe: A non-halting decider is defined [ 2020-11-11 version ]
Message-ID<Zr0rH.261085$d95.2722@fx06.iad>
In reply to#25153
On 11/11/20 7:11 PM, olcott wrote:
> 
> // Simplified version of Linz H_Hat DOES NOT copy itself
> 01 void H_Hat(u32 P)  // (bottom of page 319)
> 02 {
> 03   if (H(P, P))
> 04     HERE: goto HERE;
> 05   else
> 06     HALT
> 07 }
> 
> // Linz H with some of the ⊢* states shown
> 08 bool H(u32 P, u32 I)  // Page 318
> 09 {
> 10   bool Halted  = false;
> 11   bool Aborted = false;
> 12   while (!Halted && !Aborted)
> 13   {
> 14     Halted  = DebugStep(P, I);
> 15     Aborted = Needs_To_Be_Aborted();
> 16   }
> 17   return !Aborted;
> 18 }
> 
> int main()
>   H_Hat(H_Hat);
> 
> If we remove line 15 H_Hat(H_Hat) executes forever because the input to
> H_Hat really must be aborted to prevent infinite execution.
> 

To see that the Halt is not required try this:

// The Halt Detector under test,
bool H(u32 P, u32 I)
{
  bool Halted = false;
  bool Aborted = false;
  while(!Halted && !Aborted)
  {
     Halted = DebugStep(P, I);
     Aborted = Needs_To_Be_Aborted();
  }
  return !Aborted;
}

// Linz's H_Hat
void H_Hat(U32 P)
{
  if(H(P, P))
    Here: goto Here;
  else
    HALT
}

// Version of H without the abort test actually aborting the execution
// For a given input, if the original H returned false, then if it was
// right, this version should end up in an infinite loop.

// We need a seperate function so we don't change the program under test.

bool H_T(u32 P, u32 I)
{
  bool Halted = false;
  bool Aborted = false;
  while(!Halted)
  {
     Halted = DebugStep(P, I);
     Aborted = Needs_To_Be_Aborted();
  }
  return !Aborted;
}

// Test program to see if the specifed program will abort,
// Or verify the need to abort reported.

bool Test_H(U32 P, bool test)
{
  if(test)
     return H_T(P, P)
  else
     return H(P, P)
}

int main()
  // This will indicate that H_Hat needed to be aborted
  Test_H(H_Hat, false)
  // This will complete showing that it didn't need to be aborted
  Test_H(H_Hat, true)
}

[toc] | [prev] | [next] | [standalone]


Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.theory


csiph-web