Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) |
| Date | 2020-11-13 22:31 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <87v9e8nb1v.fsf@bsb.me.uk> (permalink) |
| References | (2 earlier) <dsidnXe82rgBMjPCnZ2dnUU7-TudnZ2d@giganews.com> <bryrH.427984$Av7.295018@fx34.iad> <xsKdnfrzZrqzKzPCnZ2dnUU7-R3NnZ2d@giganews.com> <87a6vlnns8.fsf@bsb.me.uk> <oa6dncC29b13UDPCnZ2dnUU7-cnNnZ2d@giganews.com> |
olcott <NoOne@NoWhere.com> writes:
> On 11/13/2020 11:56 AM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 11/13/2020 10:24 AM, Richard Damon wrote:
>>>> On 11/13/20 11:09 AM, olcott wrote:
>>>>> On 11/13/2020 9:51 AM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> When-so-ever UTM halt decider H decides that:
>>>>>>> (1) its input (<P>,I) would never halt unless H stopped simulating it
>>>>>>> and
>>>>>>> (2) its input (<P>,I) would never halt unless H stopped simulating it
>>>>>>> then H has made a correct not-halting decision on this input.
>>>>>>>
>>>>>>> Since it does divide all of its inputs into {halting and
>>>>>>> not-halting}** it is a halt decider.
>>>>>>
>>>>>> No, that's not what the halting problem is about.
>>>>>>
>>>>>
>>>>> Sure it is:
>>>>>
>>>>> **The Halting problem is a problem in computer science.
>>>>> The problem is looking at a computer program and finding
>>>>> out if the program is going to run forever or not. We say
>>>>> that a program "solves the halting problem" if it can
>>>>> look at any other program and tell if that other program
>>>>> will run forever or not.
>>>>> https://simple.wikipedia.org/wiki/Halting_problem
>>>>>
>>>>> Glancing at a few of my words for the purpose of contriving some sort of
>>>>> rebuttal has not ultimately been a very effective strategy for you.
>>>>>
>>>>
>>>> The key differencne between that and what you say is that this
>>>> definition is based on the ACTUAL behavior of the actual program, and
>>>> not on what some program did or did not do while analyising the program.
>>>>
>>>> YOUR definition focuses on what the decider did, not what the program
>>>> under test does, and if there is a possible difference, you resolve it
>>>> by focusing on the decider, and NOT on the actual program. Thus, you
>>>> program is NOT a true Halting Decider.
>>>>
>>>
>>> Since H does divide all of its inputs into {halting and not-halting}
>>> it is a halt decider.
>>
>> It does not, as you yourself have told us. Given
>>
>> void H_Hat(u32 P) { if (H(P, P)) while (1); }
>>
>>> 08 bool H(u32 P, u32 I)
>>> 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 }
>>
>> You have confirmed that H(H_Hat, H_Hat) is false and that H_Hat(H_hat)
>> is a finite computation.
>
> When anyone cites what is purported to be a counter-example to a halt
> decider correctly deciding its inputs and this "counter-example" is not
> an input to this halt decider they commit the straw-man error of
> reasoning.
I gave a counter example to H being a halt decider. It is the pair
(H_Hat, H_Hat). It is "input" (at least as close as your code has to
such a thing) to the halt decider H. H gives the wrong answer
(according to you). Are you actually agreeing that the H you showed is
not a halt decider, because the counter example I gave is right there as
an "input" to H?
If you are saying that some other function is in fact a halt decider,
please actually show it, and I will give you the counter example to it
being one. The same counter-example does not apply to all deciders,
though they often look similar.
--
Ben.
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 09:14 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-13 15:51 +0000
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 10:09 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 11:24 -0500
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 10:37 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-13 17:56 +0000
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 12:18 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-13 22:31 +0000
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 16:45 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 17:56 -0500
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 17:02 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 18:59 -0500
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 18:21 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 20:54 -0500
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 20:35 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 22:39 -0500
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) [ counter-example? ] olcott <NoOne@NoWhere.com> - 2020-11-13 22:11 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) [ counter-example? ] olcott <NoOne@NoWhere.com> - 2020-11-13 22:22 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) [ counter-example? ] Richard Damon <Richard@Damon-Family.org> - 2020-11-14 09:33 -0500
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-14 01:48 +0000
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 20:24 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-14 15:09 +0000
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) [ counter-example? ] olcott <NoOne@NoWhere.com> - 2020-11-13 23:44 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) [ counter-example? ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-14 14:54 +0000
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-13 17:39 +0000
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 12:14 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-13 22:12 +0000
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 16:32 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-14 01:56 +0000
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 21:23 -0600
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-14 14:54 +0000
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Jeff Barnett <jbb@notatt.com> - 2020-11-13 11:34 -0700
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-13 20:45 +0000
Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Jeff Barnett <jbb@notatt.com> - 2020-11-13 14:18 -0700
csiph-web