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


Groups > comp.theory > #27221

Re: HALT has to solve NON_HALTING TMs but has to HALT itself!

From "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups comp.theory
Subject Re: HALT has to solve NON_HALTING TMs but has to HALT itself!
Date 2020-12-17 23:23 -0800
Organization Aioe.org NNTP Server
Message-ID <rrhlde$1g3o$1@gioia.aioe.org> (permalink)
References (4 earlier) <4b36145f-6b69-450c-b43b-30245f18c119n@googlegroups.com> <rrgdgo$33k$3@gioia.aioe.org> <846b42c8-7d24-4aec-8b3e-9ede17d15de1n@googlegroups.com> <rrhfbf$1nlm$1@gioia.aioe.org> <77a5ae0c-7ecf-4375-9cb5-908ac1eb7fa6n@googlegroups.com>

Show all headers | View raw


On 12/17/2020 10:18 PM, Graham Cooper wrote:
> On Friday, December 18, 2020 at 4:40:04 PM UTC+11, Chris M. Thomasson wrote:
>> On 12/17/2020 7:58 PM, Graham Cooper wrote:
>>> On Friday, December 18, 2020 at 7:02:37 AM UTC+11, Chris M. Thomasson wrote:
>>>> On 12/17/2020 1:40 AM, Graham Cooper wrote:
>>>>> On Thursday, December 17, 2020 at 12:04:41 PM UTC+11, Chris M. Thomasson wrote:
>>>>>> On 12/15/2020 2:56 PM, Graham Cooper wrote:
>>>>>>> On Wednesday, December 16, 2020 at 7:44:08 AM UTC+11, Kaz Kylheku wrote:
>>>>>>>> On 2020-12-15, Graham Cooper <graham...@gmail.com> wrote:
>>>>>>>>> Doesn't matter, if halt hangs on a spurious program test
>>>>>>>>> then that program hangs too so we KNOW its halt value
>>>>>>>>> with incremental processing time!
>>>>>>>> You can't externally tell the difference between a machine that truly
>>>>>>>> hangs forever, and a machine that terminates, but has not yet done so:
>>>>>>>> it just requires more time and steps.
>>>>>>>>
>>>>>>>> Only using internal reasoning---by observing some internal behavior, or
>>>>>>>> deducing it from analyzing the code---can you tell that something hangs
>>>>>>>> forever. Like, "aha, here is a trivial endless loop, which is provably
>>>>>>>> reached from the starting point in no more than 300 steps".
>>>>>>>>
>>>>>>>> This is the same as the halting problem. The halting theorem says that
>>>>>>>> there can be no universal algorithm for deciding, in a finite number
>>>>>>>> of steps, whether a given machine will halt.
>>>>>>>
>>>>>>> Which is just : GIVEN A SMALLER CLASS OF COMPUTATION
>>>>>>>
>>>>>>> CAN YOU DECIDE A LARGER CLASS OF COMPUTATION
>>>>>>>
>>>>>>> A self inconsistent paradox of specification
>>>>>>>
>>>>>>>>
>>>>>>>> Thus when you say "if halt hangs ... that program hals too ... so we
>>>>>>>> KNOW its halt value", you are necessarily taking the perspective that we
>>>>>>>> have a magic oracle that allows us to know.
>>>>>>>
>>>>>>>
>>>>>>> WRONG! you dont need an ORACLE
>>>>>>>
>>>>>>> There is a difference between
>>>>>>>
>>>>>>> 10 steps - halt( spuriousProgram ) = HANG
>>>>>>> 100 steps - halt( spuriousProgram ) = HANG
>>>>>>> 1000 steps - halt( spuriousProgram ) = HANG
>>>>>>> 10000 steps - halt( spuriousProgram ) = HANG
>>>>>>>
>>>>>>> 10 steps - halt( longProgram ) = HANG
>>>>>>> 100 steps - halt( longProgram ) = HANG
>>>>>>> 1000 steps - halt( longProgram ) = HANG
>>>>>>> 10000 steps - halt( longProgram ) = OUTPUTS VALUE
>>>>>>>
>>>>>>>
>>>>>>> Consider INFINITE PROCESSING STEPS and you can SEE the ANSWER!
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>>
>>>>>>>> We do not have an algorithm (Turing computation) to be able to KNOW;
>>>>>>>> not for any arbitary machine.
>>>>>>>
>>>>>>> ...for a finite number of steps.
>>>>>>>
>>>>>>> But its just a POORLY SPECIFIED SPECIFICATION
>>>>>>>
>>>>>>> You can go AROUND AND AROUND in semantic discussion
>>>>>>> OR you can use a RUBRIC for the halting problem.
>>>>>>>
>>>>>>> Is CHAITANS OMEGA UNCOMPUTABLE
>>>>>>>
>>>>>>>
>>>>>>> 10 processing steps - CO = 0.???1????01????...
>>>>>>> 100 processing steps - CO = 0.???11??0001????...
>>>>>>> 1000 processing steps - CO = 0.?1111?00001????...
>>>>>>> 10000 processing steps - CO = 0.11111?0000111??...
>>>>>>>
>>>>>>>
>>>>>>> LOOKS COMPUTABLE TO ME!
>>>>>>>
>>>>>>> At the Infinite processing time LIMIT - CO is fully computable
>>>>>>>
>>>>>>> Any remaining ? can be determined to be 0's
>>>>>>>
>>>>>> What is an infinite processing time limit?
>>>>>
>>>>>
>>>>> Its just a hypothetical limit like 1/n as n-->o = INFINITY
>>>> I am wondering if you tried to see if a server work loop, think
>>>> threadpool, would halt... Say its been running for several years and
>>>> going strong
>>>
>>> As long as the programs on the server DONT include an INF LOOP CHECKER
>>> then there's nothing stopping that.
>> The main server loop never dies, unless artificially directed to do so.
> 
> Right!  Technically it doesnt compute anything.

I must be missing something, well... The server loop can compute, or 
process, if you will, say... Client requests?

> 
> Computable is merely defined that way, a program processes an input, writes an output and halts.
> 
> It ties in with FUNCTION theory that way.
> 
> a series of outputs is not a pure function.
> 
> To tie function theory and non-terminating code (input streams) together you require some extra functions
> 
> INPUT = <ABCD...>
> 
> F' = f(A)
> F'= f(AB)
> F'' = f(ABC)
> ...
> 
> 
> so what you get is
> 
> mapfun( f ,  < <A> <AB> <ABC> <ABCD> ... > )
> 
> to process an infinite stream in pure functions
> 
> 
> 
> 
> 

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


Thread

HALT has to solve NON_HALTING TMs but has to HALT itself! Graham Cooper <grahamcooper7@gmail.com> - 2020-12-15 07:19 -0800
  Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2020-12-15 20:15 +0000
  Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-15 20:44 +0000
    Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Graham Cooper <grahamcooper7@gmail.com> - 2020-12-15 14:56 -0800
      Re: HALT has to solve NON_HALTING TMs but has to HALT itself! "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-16 17:04 -0800
        Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Graham Cooper <grahamcooper7@gmail.com> - 2020-12-17 01:40 -0800
          Re: HALT has to solve NON_HALTING TMs but has to HALT itself! "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-17 12:02 -0800
            Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Graham Cooper <grahamcooper7@gmail.com> - 2020-12-17 19:58 -0800
              Re: HALT has to solve NON_HALTING TMs but has to HALT itself! "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-17 21:39 -0800
                Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Graham Cooper <grahamcooper7@gmail.com> - 2020-12-17 22:18 -0800
                Re: HALT has to solve NON_HALTING TMs but has to HALT itself! "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-17 23:23 -0800
                Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Graham Cooper <grahamcooper7@gmail.com> - 2020-12-17 23:30 -0800
  Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Jeff Barnett <jbb@notatt.com> - 2020-12-15 15:00 -0700
    Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-15 22:13 +0000
      Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-15 23:12 +0000
        Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Graham Cooper <grahamcooper7@gmail.com> - 2020-12-15 15:23 -0800
          Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-16 00:39 +0000
        Re: HALT has to solve NON_HALTING TMs but has to HALT itself! olcott <NoOne@NoWhere.com> - 2020-12-15 17:26 -0600
          Re: HALT has to solve NON_HALTING TMs but has to HALT itself! "dklei...@gmail.com" <dkleinecke@gmail.com> - 2020-12-15 16:01 -0800
          Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-16 00:15 +0000

csiph-web