XPost: comp.theory
From: news.dead.person.stones@darjeeling.plus.com
On 20/11/2025 02:08, dart200 wrote:
> 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
I'm not clear what you mean by "writing a paradox". The HP is not a paradox,
in my view, and I
would guess in most computer scientists / mathematicians views (but that's
just a guess).
It sounds as though you're challenging posters to write some kind of /program/
?, so maybe just
replace your use of "paradox" with "program" or at leas some more descriptive
term. I think there's
a risk that people seeing you talking about HP paradoxes could dismiss you
as a crank. (I'm not
suggesting you are a crank, just that your terminology may result in people
disengaging from your
work...)
Clearly every TM halts or does not halt, so this "program" must be some kind
of program that neither
halts nor doesn't halt? Ummm.... Well, I guess you want people to write one
of your
context-sensitive programs? Perhaps they simply don't have any concept of
halting?
But is it really the case that cs_TMs don't have a halting status? That
sounds wrong, but for sure
we might need to work on setting a new appropriate definition of halting,
applicable for cs-TMs? As
soon as we do that, my previous argument will work with appropriate
adjustments.
[Basically, what I said holds as long as there are only a small number of
halting statuses that
apply to cs-TMs. In fact, I imagine we will still have just "halts" or
"neverhalts", so my H0, H1
will suffice as they are - regardless of whether your program "confounds"
them!.)
So I don't think (a) disagrees with my previous post.
>
> 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.
I think you're just saying that HP cannot be solved by having two deciders
e.g. my H0/H1, such that
given any input M, one of H0/H1 decides M correctly. That's true, as the HP
asks for /one/ TM
decider, not two, and crucially we don't have a way to combine H0/H1 into a
single decider that
satisfies HP.
Mike.
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
