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


Groups > comp.lang.c > #156236 > 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 7 — 5 participants

Back to article view | Back to comp.lang.c


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 Girls Dating <girlsdating170@gmail.com> - 2020-11-06 20:39 -0800
    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 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

#156236 — 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]


#156266 — 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#156236
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]


#156551

FromGirls Dating <girlsdating170@gmail.com>
Date2020-11-06 20:39 -0800
Message-ID<9b6dbccf-71f5-43b2-99de-1dae705e4b13o@googlegroups.com>
In reply to#156236
On Thursday, October 29, 2020 at 5:13:29 AM UTC+5:30, 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.
> 
> 
> 
> 
> 
> 
> -- 
> Copyright 2020 Pete Olcott

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


#156582 — 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#156236
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]


#156594

FromMr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date2020-11-12 18:36 +0000
Message-ID<WgfrH.423651$TG.12268@fx08.ams4>
In reply to#156236
On 28/10/2020 23:43, 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.

You still haven't shown how your decider decides that a program won't halt and until you do this you haven't refuted anything. SHOW. YOUR. WORKING. OR. SHUT. THE. FUCK. UP.

/Flibble

-- 
¬

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


#156595

FromSjouke Burry <burrynulnulfour@ppllaanneett.nnll>
Date2020-11-12 21:37 +0100
Message-ID<5fad9cec$0$9538$e4fe514c@textnews.kpn.nl>
In reply to#156594
On 12.11.20 19:36, Mr Flibble wrote:
> On 28/10/2020 23:43, olcott wrote:
>> Intuitively, a decider should be a Tur
cut

You still have not killfiled olcot yet?  Tsssskkkkk.....

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


#156596

Fromolcott <NoOne@NoWhere.com>
Date2020-11-12 14:59 -0600
Message-ID<8POdnSv8qJTVPzDCnZ2dnUU7-f-dnZ2d@giganews.com>
In reply to#156595
On 11/12/2020 2:37 PM, Sjouke Burry wrote:
> On 12.11.20 19:36, Mr Flibble wrote:
>> On 28/10/2020 23:43, olcott wrote:
>>> Intuitively, a decider should be a Tur
> cut
> 
> You still have not killfiled olcot yet?  Tsssskkkkk.....

I set the Followup-To field to be comp.theory

-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [standalone]


Back to top | Article view | comp.lang.c


csiph-web