Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #24583 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2020-10-28 18:43 -0500 |
| Last post | 2020-11-12 14:59 -0600 |
| Articles | 20 on this page of 26 — 9 participants |
Back to article view | Back to comp.theory
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 →
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-10-28 18:43 -0500 |
| Subject | A 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]
| From | Mostowski Collapse <janburse@fastmail.fm> |
|---|---|
| Date | 2020-10-29 19:40 +0100 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-11 11:06 -0600 |
| Subject | Re: 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]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2020-11-11 18:11 +0000 |
| Subject | Re: 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]
| From | David Kleinecke <dkleinecke@gmail.com> |
|---|---|
| Date | 2020-11-11 10:59 -0800 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-11 13:08 -0600 |
| Subject | Re: 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]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2020-11-11 15:29 -0500 |
| Subject | Re: 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]
| From | David Kleinecke <dkleinecke@gmail.com> |
|---|---|
| Date | 2020-11-11 13:00 -0800 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-11 15:56 -0600 |
| Subject | Re: 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]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2020-11-11 22:01 +0000 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-11 17:48 -0600 |
| Subject | Re: 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]
| From | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2020-11-11 17:33 -0700 |
| Subject | Re: 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]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2020-11-12 02:02 +0000 |
| Subject | Re: 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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2020-11-11 23:53 +0000 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-11 18:04 -0600 |
| Subject | Re: 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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2020-11-12 01:00 +0000 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-11 19:16 -0600 |
| Subject | Re: 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]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2020-11-11 19:00 -0500 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-11 18:11 -0600 |
| Subject | Re: 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]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2020-11-11 20:44 -0500 |
| Subject | Re: 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