Sujet : Re: Halting Problem: What Constitutes Pathological Input
De : dbush.mobile (at) *nospam* gmail.com (dbush)
Groupes : comp.theoryDate : 06. May 2025, 04:16:50
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <vvbuv1$1tr5o$4@dont-email.me>
References : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
User-Agent : Mozilla Thunderbird
On 5/5/2025 11:05 PM, olcott wrote:
On 5/5/2025 9:56 PM, dbush wrote:
On 5/5/2025 10:51 PM, olcott wrote:
On 5/5/2025 9:27 PM, dbush wrote:
On 5/5/2025 10:18 PM, olcott wrote:
On 5/5/2025 8:59 PM, dbush wrote:
On 5/5/2025 8:57 PM, olcott wrote:
On 5/5/2025 7:49 PM, dbush wrote:
>
Which starts with the assumption that an algorithm exists that performs the following mapping:
>
>
Given any algorithm (i.e. a fixed immutable sequence of instructions) X described as <X> with input Y:
>
A solution to the halting problem is an algorithm H that computes the following mapping:
>
(<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
(<X>,Y) maps to 0 if and only if X(Y) does not halt when executed directly
>
>
>
DO COMPUTE THAT THE INPUT IS NON-HALTING
IFF (if and only if) the mapping FROM INPUTS
IS COMPUTED.
>
i.e. it is found to map something other than the above function which is a contradiction.
>
>
The above function VIOLATES COMPUTER SCIENCE.
You make no attempt to show how my claim
THAT IT VIOLATES COMPUTER SCIENCE IS INCORRECT
you simply take that same quote from a computer
science textbook as the infallible word-of-God.
>
All you are doing is showing that you don't understand proof by contradiction,
>
Not at all.
>
>
Yes.
>
The mapping is well defined.
>
You don't even know that "well defined" means
that all of the steps have been specified.
>
A mapping doesn't *have* steps. It's simply an association between an input domain and an output domain.
>
Computing the mapping does > have 100% totally specific steps
So you're assuming an algorithm exists that can compute the below mapping.
Then when a contradiction is reached, that proves the assumption false, as Linz and others proved and as you have *explicitly* agreed is correct.
Given any algorithm (i.e. a fixed immutable sequence of instructions) X described as <X> with input Y:
A solution to the halting problem is an algorithm H that computes the following mapping:
(<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
(<X>,Y) maps to 0 if and only if X(Y) does not halt when executed directly
…