XPost: comp.theory, sci.logic, sci.math
From: polcott333@gmail.com
On 11/19/2025 5:04 PM, Jeff Barnett wrote:
> On 11/19/2025 12:42 PM, Mike Terry wrote:
>> On 19/11/2025 18:26, dart200 wrote:
>>> On 11/18/25 3:47 PM, Mike Terry wrote:
>>>> On 18/11/2025 03:10, dart200 wrote:
>>>>> On 11/17/25 7:07 PM, Kaz Kylheku wrote:
>>>>>> On 2025-11-18, dart200 wrote:
>>>>>>> On 11/17/25 4:31 PM, olcott wrote:
>>>>>>>> On 11/17/2025 6:06 PM, dart200 wrote:
>>>>>>>>> On 11/17/25 3:35 PM, olcott wrote:
>>>>>>>>>> The halting problem is requiring deciders to
>>>>>>>>>> compute information that is not contained in
>>>>>>>>>> their input.
>>>>>>>>>
>>>>>>>>> ur agreeing with turing and the halting problem:
>>>>>>>>>
>>>>>>>>> one cannot compute whether a machine halts or not from the string
>>>>>>>>> describing the machine
>>>>>>>>>
>>>>>>>>
>>>>>>>> That the halting problem limits computation
>>>>>>>> is like this very extreme example:
>>>>>>>>
>>>>>>>> Predict who the next president of the United States
>>>>>>>> will be entirely on the basis of √2 (square root of 2).
>>>>>>>> That cannot be derived from the input.
>>>>>>>
>>>>>>> bruh, ur agreeing with the halting problem:
>>>>>>>
>>>>>>> one cannot take the string describing the machine, and use it to
>>>>>>> compute
>>>>>>> whether the machine described halts
>>>>>>
>>>>>> But that isn't true; you certainly can do that. Just not using one
>>>>>> unified algorithm that works for absolutely all such strings.
>>>>>>
>>>>>> When it /does/ work, it's certainly not based on any input other than
>>>>>> the string.
>>>>>
>>>>> yes i meant generally
>>>>>
>>>>> you also can't compute generally whether you can or cannot compute
>>>>> whether a an machine description halts or not
>>>>
>>>> What does that mean though?
>>>>
>>>> It sounds like you're asking for a /single/ TM that given /any/
>>>> machine description D, must compute "whether or not D's halting is
>>>> computable". [And saying no such single TM exists?]
>>>
>>> yes, it takes /single/ machine input a outputs whether /any/ other
>>> machine could compute the input machine's halting semantics.
>>
>> Have you read Kaz's response to my post? That explains why for any
>> given machine, there is always some other machine that computes the
>> halting status of that machine. Basically there are only two possible
>> behaviours: halts or neverhalts. We just need two machines H1 and H0
>> that straight away return halts/neverhalts respectively. For any
>> machine M, either H1 or H0 correctly computes M's halting status, so
>> assuming normal terminology use, any single M is decideable. (And by
>> extension, halting for any finite set of machines is decidable.)
>>
>> Sometimes people attempt to come up with reasons why H1 and H0 don't
>> count. That was certainly PO's response, and his explanation was that
>> H1 and H0 are disqualified as halt deciders because they "aren't even
>> trying". He has never explained what it means for a TM to "not really
>> try" to do something; of course, TMs are just what they are, without
>> "trying" to do anything. We're not talking about an olympic sport
>> where there are points awarded for effort/artistic interpretation
>> etc., it's all just "whether they work".
>
> They don't count as *deciders* plain and simple because a *decider* must
> decide correctly on all possible inputs. Even a partial decider must,
> for all possible inputs, return "yes", "no", or "don't know" and must be
> correct when returning one of the first two. So that any machine that
> returns the same value for all inputs, is a decider in a domain where
> the onto range contains one and only one value, e.g., a halt decider
> that decides halting status for all possible non-halting (TM, data)
> input - not very interesting. Neither is the example of a decider that
> returns "don't know" for all inputs. (Just to state the obvious: when
> something is said to return a value halting of that something is entailed.)
Yes that is technically correct, yet the term partial decider
totally befuddles newcomers. I switched to termination analyzers
that are supposed to be correct for all program/input pairs
which is made much simpler for programs having no inputs.
>> [Also, people like PO often confuse what the halting problem says,
>> believing that it is implying that there is some machine M which
>> "cannot be decided". That's a misunderstanding...]
>>
>> Anyhow, all of that is completely missing the point of the halting
>> problem - that is to find /one/ machine H that can decide /any/ input
>> M_desc. Finding a machine that can decide one specific input is
>> trivial.--
> Jeff Barnett
>
--
Copyright 2025 Olcott
My 28 year goal has been to make
"true on the basis of meaning" computable.
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
