Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #2643 > unrolled thread
| Started by | olcott <polcott2@gmail.com> |
|---|---|
| First post | 2021-03-14 13:17 -0500 |
| Last post | 2021-03-16 19:12 +0000 |
| Articles | 5 — 3 participants |
Back to article view | Back to comp.software-eng
This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by
below is the oldest one visible, not the original post.
Re: Refuting the halting problem proofs with fully operational code (argument reframed on Ben's suggestion) olcott <polcott2@gmail.com> - 2021-03-14 13:17 -0500
Re: Refuting the halting problem proofs [...]. (I dare you to find the error) olcott <NoOne@NoWhere.com> - 2021-03-15 09:09 -0500
Re: Refuting the halting problem proofs [...]. (I dare you to find the error) olcott <NoOne@NoWhere.com> - 2021-03-15 10:11 -0500
Re: Refuting the halting problem proofs with fully operational code (It is not that hard.) olcott <NoOne@NoWhere.com> - 2021-03-16 13:40 -0500
Re: Refuting the halting problem proofs with fully operational code (It is not that hard.) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-16 19:12 +0000
| From | olcott <polcott2@gmail.com> |
|---|---|
| Date | 2021-03-14 13:17 -0500 |
| Subject | Re: Refuting the halting problem proofs with fully operational code (argument reframed on Ben's suggestion) |
| Message-ID | <s2lk0l$ikn$1@dont-email.me> |
On 3/14/2021 11:34 AM, Kaz Kylheku wrote: > On 2021-03-14, olcott <polcott2@gmail.com> wrote: >> There is no correct yes/no value that any decider can ever return to an >> input that does the opposite of whatever the decider decides. >> >> You know this I know this so I don't understand why you lie about this. > > The decider is a function. H_Hat is a specific input, so Halts(H_Hat, > H_Hat) returns exactly one value, just like Add(1, 3). It cannot > return any other value. The opposite of that value is the correct one. > On Ben's excellent suggestion I have superseded all of this reasoning and simply concluded that if the only reason an input program halts is that its execution was aborted by the halt decider then this input program <is> a non-halting computation. On 3/13/2021 8:26 PM, Ben Bacarisse wrote: > If you really could detect those computations would not > halt if not stopped, you'd have a conventional halt decider > and you should be boasting about that, not hiding your light > under a "redefining the criterion" bushel. > The linked paper shows exactly how an at least partial halt decider > really could detect those computations** would not halt if not stopped, ** The conventional halting problem undecidability proof counter-examples http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-03-15 09:09 -0500 |
| Subject | Re: Refuting the halting problem proofs [...]. (I dare you to find the error) |
| Message-ID | <8Y-dnTHgjZc599L9nZ2dnUU7-a-dnZ2d@giganews.com> |
| In reply to | #2643 |
On 3/15/2021 8:38 AM, Andy Walker wrote: > On 15/03/2021 02:30, Chris M. Thomasson wrote: >> On 3/14/2021 7:20 PM, olcott wrote: >>> This proves that I am correct [...]. >>> Thanks to Ben and Kaz this is all that is needed. >> If you smash your forehead in with a sledge hammer, will you halt? > > I'm slightly ashamed to admit that when PO /did/ halt, there > was a short period of relief, but after a month or so I started to > miss the regular banter. I assume that no-one, not even PO, really > thinks that any progress is being made, or will ever be made, so it's > just a matter of observing PO and his entourage winding each other up. > What would be perfect would be if each member of the entourage could > restrict themselves to one posting per day. That would give us about > a dozen articles per day as light relief, rather than getting on for > 100 [which means I have to zap lots of them unread]. > Any bloody idiot can continue to parrot: You are wrong, you are wrong, I know that you are wrong because I really really believe that you are wrong. I dare you or anyone else to find a single significant error (that changes the outcome) in any of this: http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-03-15 10:11 -0500 |
| Subject | Re: Refuting the halting problem proofs [...]. (I dare you to find the error) |
| Message-ID | <8b-dnRnWLMqn5NL9nZ2dnUU7-a_NnZ2d@giganews.com> |
| In reply to | #2644 |
On 3/15/2021 9:55 AM, David Brown wrote:
> Note - please /stop/ posting this stuff in unrelated groups such as
> c.l.c and c.l.c++.
>
> On 15/03/2021 15:09, olcott wrote:
>> On 3/15/2021 8:38 AM, Andy Walker wrote:
>>> On 15/03/2021 02:30, Chris M. Thomasson wrote:
>>>> On 3/14/2021 7:20 PM, olcott wrote:
>>>>> This proves that I am correct [...].
>>>>> Thanks to Ben and Kaz this is all that is needed.
>>>> If you smash your forehead in with a sledge hammer, will you halt?
>>>
>>> I'm slightly ashamed to admit that when PO /did/ halt, there
>>> was a short period of relief, but after a month or so I started to
>>> miss the regular banter. I assume that no-one, not even PO, really
>>> thinks that any progress is being made, or will ever be made, so it's
>>> just a matter of observing PO and his entourage winding each other up.
>>> What would be perfect would be if each member of the entourage could
>>> restrict themselves to one posting per day. That would give us about
>>> a dozen articles per day as light relief, rather than getting on for
>>> 100 [which means I have to zap lots of them unread].
>>>
>>
>> Any bloody idiot can continue to parrot:
>> You are wrong, you are wrong,
>> I know that you are wrong because
>> I really really believe that you are wrong.
>
> That is basically what /you/ have been saying to the people who figured
> out that the halting problem cannot be solved.
>
>>
>> I dare you or anyone else to find a single significant error
>> (that changes the outcome) in any of this:
>>
>> http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf
>>
>
> I dare you to look at the rough proof at
> <https://en.wikipedia.org/wiki/Halting_problem> and find a single
> significant error in that. If there is no error in Turing's proof that
> the halting problem cannot be solved, then there is no need to look at
> your work to know it is wrong. (Looking at it to find /what/ is wrong
> might still be instructive.)
>
> But just for fun, I did have a look at your link. Your first mistake is
> in your first sentence - "The simplest way to define a halt decider is
> to make a program that runs its input to see what it does". You can't
> make such a program. If you could, the halting problem would be
> trivially solvable. You can't start your "proof" by assuming the thing
> you want to proof - that's begging the question, or a circular argument.
> (You can suppose it is true in order to derive a contradiction, to
> prove the hypothesis is false - but that's not what you are trying to do
> here.)
>
> You then continue to assume the existence of the impossible halt decider
> program.
>
> The nearest you get to saying something correct is to talk about a "(at
> least partial) halt decider". You don't define your terms (a common
> mistake amongst people who don't know how to write a proof), but
> certainly it is trivially possible to define a function that /sometimes/
> determines if a function halts. The only impossible bit is to make such
> a function that is /not/ "partial" - that works for any function, and
> any input.
>
> Your idea seems to be that "Halts" will look at a trace and see if a
> function (possibly "Halts" itself - your document is not clear) is
> called twice from the same address without there being a conditional
> jump in between. If so, it will conclude that the function will be
> "infinitely recursive" and not halt. Otherwise the function will halt.
> Is that correct?
>
>
> There are major flaws in this argument.
>
> First, there is no requirement for a an infinite recursion in order for
> a function not to halt. An infinite loop will be a non-halting system.
> (Loops are equivalent to a limited form of recursion in computation
> theory, but for some incomprehensible reason you are using x86 machine
> code instead of simpler computation models. There are a large numbers
> of ways of causing an infinite loop in x86, without recursion or
> conditional branches.)
>
> Secondly, your algorithm does not detect all infinite recursion.
> Conditional branches are no guarantee that the recursion is not infinite.
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. (Sipser 1997:165)
Sipser, Michael 1997. Introduction to the Theory of Computation. Boston:
PWS Publishing Company (165-167)
All that I have done is conclusively prove that the
"do the opposite of whatever halt decider decides"
basis of the conventional halting problem proofs does
not actually prove halting problem undecidability.
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-03-16 13:40 -0500 |
| Subject | Re: Refuting the halting problem proofs with fully operational code (It is not that hard.) |
| Message-ID | <jcSdnb84BfUwZs39nZ2dnUU7-UPNnZ2d@giganews.com> |
| In reply to | #2643 |
On 3/16/2021 1:09 PM, olcott wrote:
> On 3/16/2021 12:26 PM, Kaz Kylheku wrote:
>> On 2021-03-16, olcott <NoOne@NoWhere.com> wrote:
>>> On 3/16/2021 8:45 AM, Kaz Kylheku wrote:
>>>> On 2021-03-15, olcott <NoOne@NoWhere.com> wrote:
>>>>> On 3/15/2021 3:18 PM, Kaz Kylheku wrote:
>>>>>>> When Test() is called with H_Hat as input this is not the
>>>>>>> pathological
>>>>>>> self-reference error. This does not derive infinite recursion.
>>>>>>
>>>>>> I don't follow this at all, sorry. What I'm saying is that I expect
>>>>>> these two to generate generate identical code, except for some
>>>>>> details of function address:
>>>>>>
>>>>>> void Test(u32 P)
>>>>>> {
>>>>>> u32 Input_Halts = Halts(P, P);
>>>>>>
>>>>>> ...
>>>>>>
>>>>>> void H_Hat(u32 P)
>>>>>> {
>>>>>> u32 Input_Halts = Halts(P, P);
>>>>>> ...
>>>>>>
>>>>>>
>>>>>> and I also mentioned that calls to either of these can be
>>>>>> completely inlined into main, so there is no difference.
>>>>>>
>>>>>> The runaway recursion is detected inside Halts(P, P), is it not?
>>>>>>
>>>>>> What happens if we call this from main:
>>>>>>
>>>>>> Test((u32) Test);
>>>>>>
>>>>>> That now has a "pathological" self-reference inside Test, right?
>>>>>> so that should now be aborted.
>>>>>
>>>>> Yes I think that you "got it" now.
>>>>
>>>> Ah, okay; we are back full tilt on that hapless global decider program.
>>>>
>>>> Unfortunately, although having multiple modes caused communication
>>>> problems, the local mode is the one which is compatible with the
>>>> concept of a function and Turing machine.
>>>>
>>>> You might remember the discussion from months ago about this; I
>>>> conceded
>>>> that local decider is a function because it isn't informed by global
>>>> state, only by instruction traces which it calculates itself.
>>>>
>>>> At that time I wrote off the global mode as incorrect and
>>>> not worthy of further consideration.
>>>>
>>>> To reiterate my position:
>>>>
>>>> The global mode leaks information so that functions are no longer
>>>> pure computations based on just their arguments.
>>>>
>>>
>>> This is not the case when the global halt decider is a function of the
>>> global UTM that is simulating every input. Its only input is the Turing
>>> machine descriptions thus making its halting decision a function of
>>> these finite strings. The UTM is an aspect of itself.
>>
>> OK, if the enire program as a whole is the input to a global decider,
>> then whenever we produce different programs for different things---like
>> calling H_Hat directly, or calling some Tests function---those are
>> completely different inputs.
>>
>> Those inputs look like compiled C programs which contain functions, but
>> that means nothing. Only the global decider is a function.
>>
>> The entities inside the input like Halts or H_Hat are not functions.
>> Their behavior changes based on the exact configuration of the overall
>> input. E.g. sometimes Halts returns 0, and sometimes not, for apparently
>> the same input.
>>
>> In that case, it's not clear what the global decider is exactly doing;
>> its results don't make any clear statement about H_Hat or Halts.
>
> This adapted UTM would simply simulate the execution of its input until
> its input halts on its own or its halt decider determines that its input
> would never halt on its own and stops simulating it. In order for the
> UTM to see what its input does it must keep track of an execution trace
> of its input. This UTM / halt decider is a pure function of its inputs.
>
>>>> That's what explains that Halts(P, P) can return in one situation
>>>> and be aborted in another. Its behavior is influenced by some global
>>>> information about events that have happened or not happened previously
>>>> to its invocation.
>>>
>>> Which the global UTM aspect of the global halt decider would have as a
>>> part of its own internal state.
>>
>> The problem is that the theory requires Halts(P, P) to be TM.
>>
>> Halts(P, P) is just a fragment of a tape of some master TM, so loosely
>> to speak.
>
> No it is operating system level functionality that is provided to its
> sub-processes (the simulated inputs) just like "C" printf must call the
> operating system for support.
>
>>>
>>>> If you present this to academia, you will get the same feedback, if
>>>
>>> I have to make what I am proposing perfectly clear before I ever present
>>> it to academia. They are not going to have the patience for endless
>>> reviews.
>>>
>>>> things even get that far. If Halts(H_Hat, H_Hat) demonstrably returns 0
>>>> in one program run, that proves that H_Hat(H_Hat) cannot be infinitely
>>>> recursive:
>>>
>>> It <is> infinitely recursive and the halt decider would have decided
>>
>> But it obviously isn't, when you yourself have a test case where
>> Halts(H_Hat, H_Hat) cheerfully returns 0.
>
> On 3/14/2021 5:11 PM, Kaz Kylheku wrote:
> > On 2021-03-14, olcott <NoOne@NoWhere.com> wrote:
> >> So you agree that an input program that only halts because the halt
> >> decider stops simulating it <is> a non-halting computation?
> >
> > If we are sure that the decision to stop it was correct (it is not
> > actually a halting program that was prematurely stopped) we may
> > pronounce it non-halting.
>
>> You are requiring people (people who know what a function is) to accept
>> execution traces which show that Halts(H_Hat, H_Hat) terminates in
>> a finite number of steps, returning 0.
>>
>> Then you're asking the same people to accept that H_Hat(H_Hat),
>> which calls Halts(H_Hat, H_Hat) and returns if that returns 0,
>> is infinitely recursive.
>>
>
> People that believe that computations that only halt because their
> execution was aborted by the halt decider are halting computations can
> simply be dismissed as incorrect.
>
>> For H_Hat(H_Hat) to recursive at all (let alone infinitely), it
>> cannot be the case that Halts(H_Hat, H_Hat) calculates zero in a finite
>> number of steps.
>
> Sure it can, you already agreed to this.
> On 3/14/2021 5:11 PM, Kaz Kylheku wrote:
> > On 2021-03-14, olcott <NoOne@NoWhere.com> wrote:
> >> So you agree that an input program that only halts because the halt
> >> decider stops simulating it <is> a non-halting computation?
> >
> > If we are sure that the decision to stop it was correct (it is not
> > actually a halting program that was prematurely stopped) we may
> > pronounce it non-halting.
>
>> So you're asking rational people to accept all three of these:
>>
>> 1. Halts is a computational function. Therefore
>> Halts(H_Hat, H_Hat) is Turing computation.
>> It either terminates, or doesn't; if it terminates,
>> it always terminates in the same state.
>>
>> 2. Halts(H_Hat, H_Hat) returns 0.
>
> People that believe that computations that only halt because their
> execution was aborted by the halt decider are halting computations can
> simply be dismissed as incorrect.
>
>> 3. Halts(H_Hat, H_Hat) doesn't return.
>
> I never said this.
>
>>> that if sneaky things were not being done behind its back. The
>>> counter-example case that you and others cite is always a case of sneaky
>>> things being done behind the halt decider's its back.
>>
>> Nope; the thing is being done in the open: integrating the decider into
>> another function to create H_Hat.
>>
>> None of these "sneaky things" do anything so cude as your own sneaky
>> things, namely destroy the concept of a function.
>>
>>>
>>> When people are only presented with a global halt decider based on
>>> adapting a global UTM this issue will never occur to them.
>>>
>>>> it's obviously calling a function which calculates 0 in a
>>>> finite number of steps. So then if you turn around with a different
>>>> program run in which H_Hat is suddenly diagnosed as infinitely
>>>> recursive
>>>> because it calls Halts(H_Hat, H_Hat), that's a huge red flag that you
>>>> have something unsavory going on. Questions will be asked.
>>>>
>>>
>>> People that believe that computations that only halt because their
>>> execution was aborted by the halt decider are halting computations can
>>> simply be dismissed as incorrect.
>>
>> I specifically don't believe that though; I believe that when your
>> decider says "simulation halted due to runaway recursion" or whatever,
>> a runaway recursion was intercepted. I take that at face value.
>>
>> Likewise, when Halts(P, P) returns 0, I take that to be a real halting
>> computation.
>>
>> The problem is you have gamed things so that the same code (which is
>> supposed to be a function whose behavior depends only on its arguments)
>> is sometimes runaway recursive and sometimes isn't.
(1) Halts() begins simulating H_Hat(H_Hat).
(2) Halts() maintains an execution trace of its simulation of H_Hat(H_Hat).
(3) Halts() examines the execution trace of its simulation of
H_Hat(H_Hat) immediately after it simulates each H_Hat(H_Hat) instruction.
(4) Halts() determines that H_Hat(H_Hat) would never terminate unless
Halts() stops simulating it.
(5) Halts() Terminates its simulation of H_Hat(H_Hat).
(6) Halts() Reports not halting for H_Hat(H_Hat).
(7) Halts() stops executing.
Its really not that hard.
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2021-03-16 19:12 +0000 |
| Subject | Re: Refuting the halting problem proofs with fully operational code (It is not that hard.) |
| Message-ID | <20210316115933.537@kylheku.com> |
| In reply to | #2649 |
On 2021-03-16, olcott <NoOne@NoWhere.com> wrote:
>
> (1) Halts() begins simulating H_Hat(H_Hat).
>
> (2) Halts() maintains an execution trace of its simulation of H_Hat(H_Hat).
>
> (3) Halts() examines the execution trace of its simulation of
> H_Hat(H_Hat) immediately after it simulates each H_Hat(H_Hat) instruction.
>
> (4) Halts() determines that H_Hat(H_Hat) would never terminate unless
> Halts() stops simulating it.
>
> (5) Halts() Terminates its simulation of H_Hat(H_Hat).
>
> (6) Halts() Reports not halting for H_Hat(H_Hat).
>
> (7) Halts() stops executing.
>
> Its really not that hard.
Firstly, why don't these same (1) ... (7) steps play out when we have this:
main()
{
H_Hat((u32) H_Hat);
}
Here, H_Hat calls Halts(P, P). Thus
(1) Halts() begins simulating H_Hat(H_Hat)
(2) Halts() maintains an execution trace ...
etc.
Secondly, step (4) is wrong. H_Hat(H_Hat) does terminate; it terminates
spontaneously when it gets a 0 from Halts. The execution trace is
incomplete/incorrect, causing (4) to make the wrong conclusion.
The trace is incomplete because Halts is not tracing into the
Halts(P, P) call that H_Hat is making.
Halts is *pretending* that Halts(P, P) is just a transparent P(P).
But that is not true; and moments later, Halts itself "behaves opposite"
to that by returning 0 from a Halts(P, P) invocation.
Your Halts is a pathological liar, basically.
That's your entire trick:
1. Whenever H_Hat calls Halts, your contraption switches Halts(P, I)
into being just a transparent P(I) call.
2. When Halts is called directly without going through H_Hat,
Halts is the real function, containing decision-making logic,
and not just P(I) call.
3. Whenever Halts simulates H_Hat calling Halts, the situation is
again like (1): it is assumed that Halts(P, I) is just P(I).
--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
[toc] | [prev] | [standalone]
Back to top | Article view | comp.software-eng
csiph-web