XPost: comp.theory, comp.software-eng   
   From: user7160@newsgrouper.org.invalid   
      
   On 1/14/26 7:43 PM, Richard Damon wrote:   
   > On 1/13/26 3:33 PM, dart200 wrote:   
   >> On 1/13/26 4:09 AM, Richard Damon wrote:   
   >>> On 1/12/26 11:21 PM, dart200 wrote:   
   >>>> On 1/12/26 7:16 PM, Richard Damon wrote:   
   >>>>> On 1/12/26 5:09 PM, dart200 wrote:   
   >>>>>> On 1/12/26 4:06 AM, Richard Damon wrote:   
   >>>>>>> On 1/6/26 10:03 PM, dart200 wrote:   
   >>>>>>>> On 1/6/26 5:26 PM, olcott wrote:   
   >>>>>>>>> On 1/6/2026 1:47 AM, dart200 wrote:   
   >>>>>>>>>> On 1/5/26 4:24 PM, Oleksiy Gapotchenko wrote:   
   >>>>>>>>>>> Just an external observation:   
   >>>>>>>>>>>   
   >>>>>>>>>>> A lot of tech innovations in software optimization area get   
   >>>>>>>>>>> discarded from the very beginning because people who work on   
   >>>>>>>>>>> them perceive the halting problem as a dogma. As result,   
   >>>>>>>>>>> certain practical things (in code analysis) are not even   
   >>>>>>>>>>> tried because it's assumed that they are bound by the halting   
   >>>>>>>>>>> problem.   
   >>>>>>>>>>>   
   >>>>>>>>>>> In practice, however, the halting problem is rarely a   
   >>>>>>>>>>> limitation. And even when one hits it, they can safely   
   >>>>>>>>>>> discard a particular analysis branch by marking it as   
   >>>>>>>>>>> inconclusive.   
   >>>>>>>>>>>   
   >>>>>>>>>>> Halting problem for sure can be better framed to not sound as   
   >>>>>>>>>>> a dogma, at least. In practice, algorithmic inconclusiveness   
   >>>>>>>>>>> has 0.001 probability, not a 100% guarantee as many engineers   
   >>>>>>>>>>> perceive it.   
   >>>>>>>>>>   
   >>>>>>>>>> god it's been such a mind-fuck to unpack the halting problem,   
   >>>>>>>>>>   
   >>>>>>>>>> but the halting problem does not mean that no algorithm exists   
   >>>>>>>>>> for any given machine, just that a "general" decider does not   
   >>>>>>>>>> exist for all machiens ...   
   >>>>>>>>>>   
   >>>>>>>>>> heck it must be certain that for any given machine there must   
   >>>>>>>>>> exist a partial decider that can decide on it ... because   
   >>>>>>>>>> otherwise a paradox would have to address all possible partial   
   >>>>>>>>>> deciders in a computable fashion and that runs up against it's   
   >>>>>>>>>> own limit to classical computing. therefore some true decider   
   >>>>>>>>>> must exist for any given machine that exists ... we just can't   
   >>>>>>>>>> funnel the knowledge thru a general interface.   
   >>>>>>>>>>   
   >>>>>>>>>   
   >>>>>>>>> For every H there is a D such that D does the opposite   
   >>>>>>>>> of whatever H reports. In this case use H1 on this D.   
   >>>>>>>>   
   >>>>>>>> yes, the inability to correctly resolve halting thru a singular   
   >>>>>>>> interface is a flaw of TM computing, not an inherent algorithmic   
   >>>>>>>> limit   
   >>>>>>>>   
   >>>>>>>   
   >>>>>>> Nope, because the proof doesn't actually need to talk about HOW   
   >>>>>>> the decider actually made its decision, and thus not limited to   
   >>>>>>> Turing Machines.   
   >>>>>>>   
   >>>>>>> All it needs is that the decider be limited by the rules of a   
   >>>>>>> computation.   
   >>>>>>>   
   >>>>>>> All the arguements against the proof seem to begin with the error   
   >>>>>>> that the decider can be changed after the fact and such change   
   >>>>>>> changes the input to match, but that breaks the fundamental   
   >>>>>>> property of computations, that they are fixed algorithms   
   >>>>>>>   
   >>>>>>> The proof shows that the SPECIFIC decider that the input was made   
   >>>>>>> from will get the wrong answer, and we can make such an input for   
   >>>>>>> ANY specific decider, and thus no decider can get all answers   
   >>>>>>> correct.   
   >>>>>>>   
   >>>>>>> That the input HAS a correct answer (just the opposite of what   
   >>>>>>> that specific decider gives) shows that there IS a correct   
   >>>>>>> answer, so there is nothing wrong about the question of its   
   >>>>>>> halting, and thus a non- answer like "its behavior is contrary"   
   >>>>>>> is valid.   
   >>>>>>>   
   >>>>>>> Everyone trying to make the arguements just shows they don't   
   >>>>>>> understand the basics of what a computation is.   
   >>>>>>   
   >>>>>> missed ya dick!   
   >>>>>>   
   >>>>>> given that deciders are inherently part of the execution path they   
   >>>>>> are deciding on ... ofc deciders can modify their behavior based   
   >>>>>> on an input which they are included within, like they can modify   
   >>>>>> their behavior based on the properties of the input.   
   >>>>>   
   >>>>> No, that behavior had to always have been in them, and thus seen by   
   >>>>> the "pathological" input.   
   >>>>>   
   >>>>>>   
   >>>>>> this is how partial deciders can intelligently block on responding   
   >>>>>> to input that cannot be answered thru their particular interface.   
   >>>>>>   
   >>>>>> i'm not aware of any method that can prove a partial decider can't   
   >>>>>> be more efficient that brute force, because again, they can block   
   >>>>>> when encountering a paradox specific to their interface.   
   >>>>>   
   >>>>> How does "brute force" determine non-halting?   
   >>>>   
   >>>> well it does for the halting computations (bounded time, bounded   
   >>>> space),   
   >>>>   
   >>>> and proper infinite loops (unbounded time, bounded space),   
   >>>>   
   >>>> just not runaway infinite computation (unbounded time, unbounded space)   
   >>>   
   >>> Which exist and is a form of non-halting.   
   >>>   
   >>> Yes, Non-Turing Complete systems, with bounded space, are Halt Decidable   
   >>   
   >> infinite loops in turing complete system are also fully enumerable   
   >> just like halting machines are. they will always result in repeat   
   >> configurations, and this is decidable within an unbounded amount of   
   >> time using brute force.   
   >   
   > You seem to confuse "enumerable" with effectively enumerable.   
   >   
   > Enumerable means that via the process of the Axiom of Choice, some   
   > enumeration is possible to be found. Doing this might require having a   
   > "God Function" to determine if a given candidate is part of the set.   
   >   
   > Just because an infinite set is enumberable, doesn't mean that you CAN   
   > create that set in a computation.   
   >   
   > While the looping machines are enumerable, that doesn't mean you can   
   > generate a set of all such machines.   
   >   
   > Unless you can actually SHOW how to DECIDE on this, in countable   
   > unbounded time, you can't claim it.   
   >   
   > THe problem is that while N is enumerable, and N^k is enumberable, 2^N   
   > is not.   
   >   
   > Your problem is you can't tell when you have simulated a machine long   
   > enough to say that it is no longer a bounded space machine, and thus   
   > "looping" is not deciable, only recognizable.   
   >   
   >>   
   >>> with simple deciders as long as the decider is allowed to be   
   >>> sufficiently bigger than the program it is deciding on. That has been   
   >>> known for a long time, but isn't an exception to the Halting Problem,   
   >>> as it doesn't meet the basic requirements.   
   >>>   
   >>>>   
   >>>>>   
   >>>>> And nothing in the theory disagrees with partial halt deciders   
   >>>>> existing, they just can NEVER give an answer to the pathological   
      
   [continued in next message]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)