Forums before death by AOL, social media and spammers... "We can't have nice things"
|    comp.ai.philosophy    |    Perhaps we should ask SkyNet about this    |    59,235 messages    |
[   << oldest   |   < older   |   list   |   newer >   |   newest >>   ]
|    Message 59,026 of 59,235    |
|    olcott to Mikko    |
|    Re: The Halting Problem asks for too muc    |
|    14 Jan 26 13:19:57    |
   
   XPost: sci.logic, comp.theory, sci.math   
   From: polcott333@gmail.com   
      
   On 1/14/2026 1:58 AM, Mikko wrote:   
   > On 13/01/2026 16:17, olcott wrote:   
   >> On 1/13/2026 2:46 AM, Mikko wrote:   
   >>> On 12/01/2026 16:43, olcott wrote:   
   >>>> On 1/12/2026 4:51 AM, Mikko wrote:   
   >>>>> On 11/01/2026 16:23, olcott wrote:   
   >>>>>> On 1/11/2026 4:22 AM, Mikko wrote:   
   >>>>>>> On 10/01/2026 17:47, olcott wrote:   
   >>>>>>>> On 1/10/2026 2:23 AM, Mikko wrote:   
   >>>>>>>>> On 09/01/2026 17:52, olcott wrote:   
   >>>>>>>>>> On 1/9/2026 3:59 AM, Mikko wrote:   
   >>>>>>>>>>> On 08/01/2026 16:22, olcott wrote:   
   >>>>>>>>>>>> On 1/8/2026 4:22 AM, Mikko wrote:   
   >>>>>>>>>>>>> On 07/01/2026 13:54, olcott wrote:   
   >>>>>>>>>>>>>> On 1/7/2026 5:49 AM, Mikko wrote:   
   >>>>>>>>>>>>>>> On 07/01/2026 06:44, olcott wrote:   
   >>>>>>>>>>>>>>>> All deciders essentially: Transform finite string   
   >>>>>>>>>>>>>>>> inputs by finite string transformation rules into   
   >>>>>>>>>>>>>>>> {Accept, Reject} values.   
   >>>>>>>>>>>>>>>>   
   >>>>>>>>>>>>>>>> The counter-example input to requires more than   
   >>>>>>>>>>>>>>>> can be derived from finite string transformation   
   >>>>>>>>>>>>>>>> rules applied to this specific input thus the   
   >>>>>>>>>>>>>>>> Halting Problem requires too much.   
   >>>>>>>>>>>>>>   
   >>>>>>>>>>>>>>> In a sense the halting problem asks too much: the problem   
   >>>>>>>>>>>>>>> is proven to   
   >>>>>>>>>>>>>>> be unsolvable. In another sense it asks too little:   
   >>>>>>>>>>>>>>> usually we want to   
   >>>>>>>>>>>>>>> know whether a method halts on every input, not just one.   
   >>>>>>>>>>>>>>>   
   >>>>>>>>>>>>>>> Although the halting problem is unsolvable, there are   
   >>>>>>>>>>>>>>> partial solutions   
   >>>>>>>>>>>>>>> to the halting problem. In particular, every counter-   
   >>>>>>>>>>>>>>> example to the   
   >>>>>>>>>>>>>>> full solution is correctly solved by some partial deciders.   
   >>>>>>>>>>>>>>   
   >>>>>>>>>>>>>> *if undecidability is correct then truth itself is broken*   
   >>>>>>>>>>>>>   
   >>>>>>>>>>>>> Depends on whether the word "truth" is interpeted in the   
   >>>>>>>>>>>>> standard   
   >>>>>>>>>>>>> sense or in Olcott's sense.   
   >>>>>>>>>>>>   
   >>>>>>>>>>>> Undecidability is misconception. Self-contradictory   
   >>>>>>>>>>>> expressions are correctly rejected as semantically   
   >>>>>>>>>>>> incoherent thus form no undecidability or incompleteness.   
   >>>>>>>>>>>   
   >>>>>>>>>>> The misconception is yours. No expression in the language of   
   >>>>>>>>>>> the first   
   >>>>>>>>>>> order group theory is self-contradictory. But the first order   
   >>>>>>>>>>> goupr   
   >>>>>>>>>>> theory is incomplete: it is impossible to prove that AB = BA   
   >>>>>>>>>>> is true   
   >>>>>>>>>>> for every A and every B but it is also impossible to prove   
   >>>>>>>>>>> that AB = BA   
   >>>>>>>>>>> is false for some A and some B.   
   >>>>>>>>>>>   
   >>>>>>>>>>   
   >>>>>>>>>> All deciders essentially: Transform finite string   
   >>>>>>>>>> inputs by finite string transformation rules into   
   >>>>>>>>>> {Accept, Reject} values.   
   >>>>>>>>>>   
   >>>>>>>>>> When a required result cannot be derived by applying   
   >>>>>>>>>> finite string transformation rules to actual finite   
   >>>>>>>>>> string inputs, then the required result exceeds the   
   >>>>>>>>>> scope of computation and must be rejected as an   
   >>>>>>>>>> incorrect requirement.   
   >>>>>>>>>   
   >>>>>>>>> No, that does not follow. If a required result cannot be   
   >>>>>>>>> derived by   
   >>>>>>>>> appying a finite string transformation then the it it is   
   >>>>>>>>> uncomputable.   
   >>>>>>>>   
   >>>>>>>> Right. Outside the scope of computation. Requiring anything   
   >>>>>>>> outside the scope of computation is an incorrect requirement.   
   >>>>>>>>   
   >>>>>>>>> Of course, it one can prove that the required result is not   
   >>>>>>>>> computable   
   >>>>>>>>> then that helps to avoid wasting effort to try the impossible. The   
   >>>>>>>>> situation is worse if it is not known that the required result   
   >>>>>>>>> is not   
   >>>>>>>>> computable.   
   >>>>>>>>>   
   >>>>>>>>> That something is not computable does not mean that there is   
   >>>>>>>>> anyting   
   >>>>>>>>> "incorrect" in the requirement.   
   >>>>>>>>   
   >>>>>>>> Yes it certainly does. Requiring the impossible is always an error.   
   >>>>>>>   
   >>>>>>> It is a perfectly valid question to ask whther a particular   
   >>>>>>> reuqirement   
   >>>>>>> is satisfiable.   
   >>>>>>   
   >>>>>> Any yes/no question lacking a correct yes/no answer   
   >>>>>> is an incorrect question that must be rejected on   
   >>>>>> that basis.   
   >>>>>   
   >>>>> Irrelevant. The question whether a particular requirement is   
   >>>>> satisfiable   
   >>>>> does have an answer that is either "yes" or "no". In some ases it is   
   >>>>> not known whether it is "yes" or "no" and there may be no known way to   
   >>>>> find out be even then either "yes" or "no" is the correct answer.   
   >>>>   
   >>>> Now that I finally have the standard terminology:   
   >>>> Proof-theoretic semantics has always been the correct   
   >>>> formal system to handle decision problems.   
   >>>>   
   >>>> When it is asked a yes/no question lacking a correct   
   >>>> yes/no answer it correctly determines non-well-founded.   
   >>>> I have been correct all along and merely lacked the   
   >>>> standard terminology.   
   >>>   
   >>> Irrelevant, as already noted above.   
   > Yes, it is. How to handle questions that lack a yes/no answer is   
   > irrelevant when discussing questions that do have a yes/no asnwer.   
   > Whether a particular requirement is satisriable always has a yes/no   
   > answer, so it is irrelevat how to handle questions that don't.   
   >   
      
   The classical diagonal argument for the Halting Problem asks a halt   
   decider H to evaluate a program D whose behavior depends on H’s own   
   output. That is not a legitimate semantic question. Under   
   proof‑theoretic semantics — where meaning is grounded in the inferential   
   structure of the implementation language — D has an ungrounded semantic   
   value because its evaluation dependency graph contains a cycle. H is   
   therefore correct to reject D as semantically ill‑formed.   
      
   --   
   Copyright 2026 Olcott
|
[   << oldest   |   < older   |   list   |   newer >   |   newest >>   ]
(c) 1994, bbs@darkrealms.ca