Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #156236 > 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 | 7 — 5 participants |
Back to article view | Back to comp.lang.c
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
| 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 | #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]
| From | Girls Dating <girlsdating170@gmail.com> |
|---|---|
| Date | 2020-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]
| 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 | #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]
| From | Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> |
|---|---|
| Date | 2020-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]
| From | Sjouke Burry <burrynulnulfour@ppllaanneett.nnll> |
|---|---|
| Date | 2020-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-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