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

Groups > comp.theory > #37174

Re: The contradiction that the HP is predicated on is detectable ..

Show all headers | View raw

On 7/27/21 3:13 PM, olcott wrote:
> On 7/27/2021 2:46 PM, Peter wrote:
>> olcott wrote:
>>> On 7/27/2021 2:02 PM, Peter wrote:
>>>> Mr Flibble wrote:
>>>>> .. due to the infinite recursion missed by Strachey blowing the
>>>>> stack of
>>>>> any turing machine simulator with finite memory (stack) size.  One
>>>>
>>>> Turing machines don't have stacks.  Stack machines have (of course)
>>>> stacks of limitless length.
>>>>
>>>
>>> Flibble's reasoning is correct, yet based on my 2016 reasoning.
>>> When the otherwise computationally equivalent TM counter-example
>>> cases are translated into an architecture having finite resources
>>> running out of stack memory would indicate infinite recursion.
>>
>> The machines of interest can't run out of stack.  Some of them (TMs)
>> don't have stacks to run out of, and others (e.g. stack machines) have
>> limitless stacks.
> 
> Your reference is not to the specific case at hand:
> 
> rec routine P
>   §L:if T[P] go to L
>     Return §
> 
> Strachey, C 1965.  An impossible program The Computer Journal, Volume 7,
> Issue 4, January 1965, Page 313, https://doi.org/10.1093/comjnl/7.4.313
> 
> For the specific case at hand Flibble's crude system of infinite
> recursion detection would work.

It would still fail.

When we run P(P), that machine will call H(P,P) which will cycle through
some large number of iterations, see the exhaustion of memory, say that
the machine is non-halting, return that value, and P will then Halt,
show that H was WRONG. DEFINITION.

You STILL have the case that replacement of the simulation of a
simulator by the simulation of the machine being simulated is only valid
if the simulator NEVER, (and that meaans NEVER) aborts its simulation.

Note, this method actually breaks the definition of computation, as the
results of a given machine isn't just dependent on the defintion of THAT
computation, as it becomes dependent on how much else is happening.

At best, the system needs to just abort the whole machine and say that
the computation exceeds the capability of the system. This means that H
can't use it as its decision method.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

The contradiction that the HP is predicated on is detectable .. Mr Flibble <flibble@reddwarf.jmc> - 2021-07-27 18:34 +0100
  Re: The contradiction that the HP is predicated on is detectable .. olcott <NoOne@NoWhere.com> - 2021-07-27 12:59 -0500
  Re: The contradiction that the HP is predicated on is detectable .. Peter <peterxpercival@hotmail.com> - 2021-07-27 20:02 +0100
    Re: The contradiction that the HP is predicated on is detectable .. olcott <NoOne@NoWhere.com> - 2021-07-27 14:14 -0500
      Re: The contradiction that the HP is predicated on is detectable .. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-07-27 12:23 -0700
        Re: The contradiction that the HP is predicated on is detectable .. olcott <NoOne@NoWhere.com> - 2021-07-27 14:36 -0500
      Re: The contradiction that the HP is predicated on is detectable .. Peter <peterxpercival@hotmail.com> - 2021-07-27 20:46 +0100
        Re: The contradiction that the HP is predicated on is detectable .. olcott <NoOne@NoWhere.com> - 2021-07-27 17:13 -0500
          Re: The contradiction that the HP is predicated on is detectable .. Richard Damon <Richard@Damon-Family.org> - 2021-07-27 15:56 -0700
            Re: The contradiction that the HP is predicated on is detectable .. olcott <NoOne@NoWhere.com> - 2021-07-27 18:06 -0500
              Re: The contradiction that the HP is predicated on is detectable .. Richard Damon <Richard@Damon-Family.org> - 2021-07-27 16:17 -0700
      Re: The contradiction that the HP is predicated on is detectable .. Mr Flibble <flibble@reddwarf.jmc> - 2021-07-27 20:47 +0100
        Re: The contradiction that the HP is predicated on is detectable .. olcott <NoOne@NoWhere.com> - 2021-07-27 16:06 -0500
          Re: The contradiction that the HP is predicated on is detectable .. Mr Flibble <flibble@reddwarf.jmc> - 2021-07-28 17:35 +0100
            Re: The contradiction that the HP is predicated on is detectable .. olcott <NoOne@NoWhere.com> - 2021-07-28 12:31 -0500
      Re: The contradiction that the HP is predicated on is detectable .. André G. Isaak <agisaak@gm.invalid> - 2021-07-27 13:58 -0600
        Re: The contradiction that the HP is predicated on is detectable .. olcott <NoOne@NoWhere.com> - 2021-07-27 17:13 -0500
      Re: The contradiction that the HP is predicated on is detectable .. Richard Damon <news.x.richarddamon@xoxy.net> - 2021-07-27 13:05 -0700
        Re: The contradiction that the HP is predicated on is detectable .. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-07-27 13:11 -0700
      Re: The contradiction that the HP is predicated on is detectable .. Jeff Barnett <jbb@notatt.com> - 2021-07-27 15:04 -0600
        Re: The contradiction that the HP is predicated on is detectable .. olcott <NoOne@NoWhere.com> - 2021-07-27 16:56 -0500
          Re: The contradiction that the HP is predicated on is detectable .. Jeff Barnett <jbb@notatt.com> - 2021-07-28 00:44 -0600
            Re: The contradiction that the HP is predicated on is detectable .. olcott <NoOne@NoWhere.com> - 2021-07-28 08:57 -0500
        Re: The contradiction that the HP is predicated on is detectable .. Mr Flibble <flibble@reddwarf.jmc> - 2021-07-28 17:36 +0100
          Re: The contradiction that the HP is predicated on is detectable .. olcott <NoOne@NoWhere.com> - 2021-07-28 12:33 -0500
          Re: The contradiction that the HP is predicated on is detectable .. Jeff Barnett <jbb@notatt.com> - 2021-07-28 11:40 -0600
            Re: The contradiction that the HP is predicated on is detectable .. olcott <NoOne@NoWhere.com> - 2021-07-28 12:53 -0500
              Re: The contradiction that the HP is predicated on is detectable .. Richard Damon <Richard@Damon-Family.org> - 2021-07-28 11:25 -0700

csiph-web