XPost: comp.theory, comp.ai.philosophy, sci.math
From: user7160@newsgrouper.org.invalid
On 11/19/25 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.
>
>
> Mike.
mike, there's two responses to this
a) you can construct halting paradoxes that contradicts multiple and
possibly even infinite deciders. certainly any finite set, after which
it becomes cat and mouse: if you define a new decider, i can add to my
growing multi-paradox that includes it.
homework assignment for the group: write a multi-decider paradox that
confounds both H1 and H0
b) turing's original semantic paradox ("satisfactory" circle-free vs
circular computable number) cannot be solved by a secondary decider on
the matter. the halting problem is fundamentally a simple form of
semantic paradox than the "satisfactory" problem.
afaik, other than me, no one i've read is trying to address semantic
paradoxes is targeting turing's original form.
i should probably write a post on that too
--
a burnt out swe investigating into why our tooling doesn't involve
basic semantic proofs like halting analysis
please excuse my pseudo-pyscript,
~ nick
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
