Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| 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-16 17:04 -0800 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <rrear4$4qt$2@gioia.aioe.org> (permalink) |
| References | <9d72637f-0382-4596-bbb4-36fbde2f2355n@googlegroups.com> <20201215123748.481@kylheku.com> <f7ac3ca5-ec4b-4171-aabb-b94eff068d3fn@googlegroups.com> |
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?
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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