XPost: comp.theory, sci.logic, sci.math
From: chris.m.thomasson.1@gmail.com
On 11/19/2025 11:42 AM, 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".
>
> [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.
Right. Any machine can have a specialized decider for it. However, there
is no _single_ decider for all machines...
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
