Re: Halting Problem: What Constitutes Pathological Input

Liste des GroupesRevenir à c theory 
Sujet : Re: Halting Problem: What Constitutes Pathological Input
De : dbush.mobile (at) *nospam* gmail.com (dbush)
Groupes : comp.theory
Date : 06. May 2025, 03:56:28
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <vvbtos$1tr5o$3@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 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.
If you claim there are steps, then you're assuming an algorithm exists that computes the mapping.  We then arrive at a contradiction, proving that the assumption that an algorithm exists that computes the following mapping is false, as proven by Linz and others 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

Date Sujet#  Auteur
3 May 26 o  …

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal