On 3/15/2025 4:54 AM, Mikko wrote:
On 2025-03-14 18:29:13 +0000, olcott said:
(1) What time is it (yes or no)?
(2) What integer X is > 5 and < 3?
(3) When we define the HP as having H return a value
corresponding to the halting behavior of input D
and input D can actually does the opposite of whatever
value that H returns, then we have boxed ourselves
in to a problem having no solution.
There are also problems that were defined with the idea that someone
would solve them but later turned out to be unsolvable, for example
angle trisection with straightedge and compass.
That a formal problem is unsolvable need not prevent solving similar
practical problem. A question like (1) is not useful for any practical
purpose so there is never any parctical need to ask it. The problem
(2) is so obviously unsolvable that everyone can try to avoid situations
where that solution would be needed. That (3) is unsolvable is not as
obvious and a solution would be useful, so someone might put some
considerable effort to solve it. Still, a partial solution, i.e. a method
that does not answer every input but produces the right answer in many
cases and never the wrong answer, can be useful for practical purposes.
When a problem is defined to have logically impossible
instances the inability to do the logically impossible
places no actual limitation on anything or anyone.
Find the square root of a box of cherries.
Determine if input DD to termination analyzer HHH
could cause a denial-of-service DOS attack to succeed.
HHH is a correct DOS detector.
On 3/15/2025 4:54 AM, Mikko wrote:
On 2025-03-14 18:29:13 +0000, olcott said:
(1) What time is it (yes or no)?
(2) What integer X is > 5 and < 3?
(3) When we define the HP as having H return a value
corresponding to the halting behavior of input D
and input D can actually does the opposite of whatever
value that H returns, then we have boxed ourselves
in to a problem having no solution.
There are also problems that were defined with the idea that someone
would solve them but later turned out to be unsolvable, for example
angle trisection with straightedge and compass.
That a formal problem is unsolvable need not prevent solving similar
practical problem. A question like (1) is not useful for any practical
purpose so there is never any parctical need to ask it. The problem
(2) is so obviously unsolvable that everyone can try to avoid situations
where that solution would be needed. That (3) is unsolvable is not as
obvious and a solution would be useful, so someone might put some
considerable effort to solve it. Still, a partial solution, i.e. a method
that does not answer every input but produces the right answer in many
cases and never the wrong answer, can be useful for practical purposes.
When a problem is defined to have logically impossible
instances the inability to do the logically impossible
places no actual limitation on anything or anyone.
Find the square root of a box of cherries.
Determine if input DD to termination analyzer HHH
could cause a denial-of-service DOS attack to succeed.
HHH is a correct DOS detector.
On 3/15/2025 10:51 PM, dbush wrote:H should be simulating the input AS IF it were executed directly. That's
On 3/15/2025 11:28 PM, olcott wrote:
On 3/15/2025 10:09 PM, dbush wrote:
On 3/15/2025 10:58 PM, olcott wrote:
On 3/15/2025 9:43 PM, dbush wrote:
On 3/15/2025 10:30 PM, olcott wrote:
The problem is defined such that H doesn't even get to look as that one.When DD() is directly executed this is not the same DD instance thatThat is not an assumption. It follows from a series of truthONLY when we ALSO assume that <X> can actually do the opposite ofThe STUPIDLY false assumption
That an H exists that satisfies the following definition:
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
whatever value that H reports.
preserving operations after making the assumption that an H that
satisfies the above requirements exist.
is the actual input to HHH.
Doesn't matter. To be a solution to the halting problem, HHH(DD) is
required to answer what would happen in the hypothetical case that DD
is executed directly.
The closest that H can possibly get to the actual behavior of its input
is for H to simulate this input. H cannot execute <D> because <D> is a
finite string.
--Anything else is not the halting problem but something else.
This goes back to my question, which I'll now ask a fourth time:
I want to know if any arbitrary algorithm X with input Y will halt when
executed directly. If I had an H that could tell me that in *all*
possible cases, I could solve the Goldbach conjecture, among many other
unsolved problems.
Does an H exist that can tell me that or not?
On 3/15/2025 10:09 PM, dbush wrote:Well THAT is not a problem.
On 3/15/2025 10:58 PM, olcott wrote:
On 3/15/2025 9:43 PM, dbush wrote:
On 3/15/2025 10:30 PM, olcott wrote:ONLY when we ALSO assume that <X> can actually do the opposite of
On 3/15/2025 9:23 PM, dbush wrote:
On 3/15/2025 9:30 PM, olcott wrote:
On 3/15/2025 5:37 PM, dbush wrote:
On 3/15/2025 5:34 PM, olcott wrote:
On 3/15/2025 4:54 AM, Mikko wrote:The halting problem wasn't defined to be uncomputable. It would >>>>>>>> be very useful to have an H that can report if X(Y) halts when >>>>>>>> executed directly for *all* possible X and Y. It was later found >>>>>>>> that no such H exists.
On 2025-03-14 18:29:13 +0000, olcott said:When a problem is defined to have logically impossible instances >>>>>>>>> the inability to do the logically impossible places no actual >>>>>>>>> limitation on anything or anyone.
(1) What time is it (yes or no)?
(2) What integer X is > 5 and < 3?
(3) When we define the HP as having H return a value
corresponding to the halting behavior of input D and input D >>>>>>>>>>> can actually does the opposite of whatever value that H
returns, then we have boxed ourselves in to a problem having >>>>>>>>>>> no solution.
There are also problems that were defined with the idea that >>>>>>>>>> someone would solve them but later turned out to be unsolvable, >>>>>>>>>> for example angle trisection with straightedge and compass. >>>>>>>>>> That a formal problem is unsolvable need not prevent solving >>>>>>>>>> similar practical problem. A question like (1) is not useful >>>>>>>>>> for any practical purpose so there is never any parctical need >>>>>>>>>> to ask it. The problem (2) is so obviously unsolvable that >>>>>>>>>> everyone can try to avoid situations where that solution would >>>>>>>>>> be needed. That (3) is unsolvable is not as obvious and a
solution would be useful, so someone might put some
considerable effort to solve it. Still, a partial solution, >>>>>>>>>> i.e. a method that does not answer every input but produces the >>>>>>>>>> right answer in many cases and never the wrong answer, can be >>>>>>>>>> useful for practical purposes.
The counter-example input is merely a logical impossibility
Which arose as part of a false assumption, thereby proving the
assumption false.
The STUPIDLY false assumption
That an H exists that satisfies the following definition:
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
whatever value that H reports.
lol wrong. DD is completely defined by its code, including HHH. If youThat is not an assumption. It follows from a series of truthWhen DD() is directly executed this is not the same DD instance that is
preserving operations after making the assumption that an H that
satisfies the above requirements exist.
the actual input to HHH. This actual input instance cannot return to DD because it is only a finite string that is never executed.
A solution to the halting problem is an algorithm H
On 3/16/2025 8:40 AM, dbush wrote:
On 3/16/2025 12:25 AM, olcott wrote:
On 3/15/2025 10:51 PM, dbush wrote:
On 3/15/2025 11:28 PM, olcott wrote:
On 3/15/2025 10:09 PM, dbush wrote:
On 3/15/2025 10:58 PM, olcott wrote:
On 3/15/2025 9:43 PM, dbush wrote:
On 3/15/2025 10:30 PM, olcott wrote:
On 3/15/2025 9:23 PM, dbush wrote:
On 3/15/2025 9:30 PM, olcott wrote:
On 3/15/2025 5:37 PM, dbush wrote:Which arose as part of a false assumption, thereby proving the >>>>>>>>>> assumption false.
On 3/15/2025 5:34 PM, olcott wrote:
On 3/15/2025 4:54 AM, Mikko wrote:
On 2025-03-14 18:29:13 +0000, olcott said:
(1) What time is it (yes or no)?
(2) What integer X is > 5 and < 3?
(3) When we define the HP as having H return a value >>>>>>>>>>>>>>> corresponding to the halting behavior of input D >>>>>>>>>>>>>>> and input D can actually does the opposite of whatever >>>>>>>>>>>>>>> value that H returns, then we have boxed ourselves >>>>>>>>>>>>>>> in to a problem having no solution.
There are also problems that were defined with the idea >>>>>>>>>>>>>> that someone
would solve them but later turned out to be unsolvable, >>>>>>>>>>>>>> for example
angle trisection with straightedge and compass.
That a formal problem is unsolvable need not prevent >>>>>>>>>>>>>> solving similar
practical problem. A question like (1) is not useful for >>>>>>>>>>>>>> any practical
purpose so there is never any parctical need to ask it. >>>>>>>>>>>>>> The problem
(2) is so obviously unsolvable that everyone can try to >>>>>>>>>>>>>> avoid situations
where that solution would be needed. That (3) is
unsolvable is not as
obvious and a solution would be useful, so someone might >>>>>>>>>>>>>> put some
considerable effort to solve it. Still, a partial
solution, i.e. a method
that does not answer every input but produces the right >>>>>>>>>>>>>> answer in many
cases and never the wrong answer, can be useful for >>>>>>>>>>>>>> practical purposes.
When a problem is defined to have logically impossible >>>>>>>>>>>>> instances the inability to do the logically impossible >>>>>>>>>>>>> places no actual limitation on anything or anyone.
The halting problem wasn't defined to be uncomputable. It >>>>>>>>>>>> would be very useful to have an H that can report if X(Y) >>>>>>>>>>>> halts when executed directly for *all* possible X and Y. It >>>>>>>>>>>> was later found that no such H exists.
The counter-example input is merely a logical impossibility >>>>>>>>>>
The STUPIDLY false assumption
That an H exists that satisfies the following definition:
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
ONLY when we ALSO assume that <X> can actually do the opposite
of whatever value that H reports.
That is not an assumption. It follows from a series of truth
preserving operations after making the assumption that an H that
satisfies the above requirements exist.
When DD() is directly executed this is not the same DD instance
that is the actual input to HHH.
Doesn't matter. To be a solution to the halting problem, HHH(DD) is
required to answer what would happen in the hypothetical case that
DD is executed directly.
The problem is defined such that H doesn't even get to look as that one.
You're mistaking what HHH is being asked to compute for what HHH is
able to compute. The implementation doesn't dictate the requirements.
Another example of the limits of computation
no CAD system will ever be able to correctly
represent the geometric object of a square
circle in the same two dimensional plane.
No system that computes the square-root will ever
correctly compute the square root of a box of cherries.
The closest that H can possibly get to the actual behavior of its input
is for H to simulate this input. H cannot execute <D> because <D> is
a finite string.
But remember the definition of a solution to the halting problem,
which states that H is required to answer what the algorithm / program
described by that finite string will do when executed directly:
No decider can be correctly required to report on the
behavior that it cannot see. The problem here is the
persistent false assumption that pathological self-reference
does not change behavior.
On 3/16/2025 2:14 PM, Fred. Zwarts wrote:
Op 16.mrt.2025 om 15:51 schreef olcott:
On 3/16/2025 8:40 AM, dbush wrote:
On 3/16/2025 12:25 AM, olcott wrote:
On 3/15/2025 10:51 PM, dbush wrote:
On 3/15/2025 11:28 PM, olcott wrote:
On 3/15/2025 10:09 PM, dbush wrote:
On 3/15/2025 10:58 PM, olcott wrote:
On 3/15/2025 9:43 PM, dbush wrote:
On 3/15/2025 10:30 PM, olcott wrote:
On 3/15/2025 9:23 PM, dbush wrote:
On 3/15/2025 9:30 PM, olcott wrote:
On 3/15/2025 5:37 PM, dbush wrote:Which arose as part of a false assumption, thereby proving >>>>>>>>>>>> the assumption false.
On 3/15/2025 5:34 PM, olcott wrote:
On 3/15/2025 4:54 AM, Mikko wrote:
On 2025-03-14 18:29:13 +0000, olcott said:
(1) What time is it (yes or no)?
(2) What integer X is > 5 and < 3?
(3) When we define the HP as having H return a value >>>>>>>>>>>>>>>>> corresponding to the halting behavior of input D >>>>>>>>>>>>>>>>> and input D can actually does the opposite of whatever >>>>>>>>>>>>>>>>> value that H returns, then we have boxed ourselves >>>>>>>>>>>>>>>>> in to a problem having no solution.
There are also problems that were defined with the idea >>>>>>>>>>>>>>>> that someone
would solve them but later turned out to be unsolvable, >>>>>>>>>>>>>>>> for example
angle trisection with straightedge and compass. >>>>>>>>>>>>>>>>
That a formal problem is unsolvable need not prevent >>>>>>>>>>>>>>>> solving similar
practical problem. A question like (1) is not useful for >>>>>>>>>>>>>>>> any practical
purpose so there is never any parctical need to ask it. >>>>>>>>>>>>>>>> The problem
(2) is so obviously unsolvable that everyone can try to >>>>>>>>>>>>>>>> avoid situations
where that solution would be needed. That (3) is >>>>>>>>>>>>>>>> unsolvable is not as
obvious and a solution would be useful, so someone might >>>>>>>>>>>>>>>> put some
considerable effort to solve it. Still, a partial >>>>>>>>>>>>>>>> solution, i.e. a method
that does not answer every input but produces the right >>>>>>>>>>>>>>>> answer in many
cases and never the wrong answer, can be useful for >>>>>>>>>>>>>>>> practical purposes.
When a problem is defined to have logically impossible >>>>>>>>>>>>>>> instances the inability to do the logically impossible >>>>>>>>>>>>>>> places no actual limitation on anything or anyone. >>>>>>>>>>>>>>>
The halting problem wasn't defined to be uncomputable. It >>>>>>>>>>>>>> would be very useful to have an H that can report if X(Y) >>>>>>>>>>>>>> halts when executed directly for *all* possible X and Y. >>>>>>>>>>>>>> It was later found that no such H exists.
The counter-example input is merely a logical impossibility >>>>>>>>>>>>
The STUPIDLY false assumption
That an H exists that satisfies the following definition:
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
ONLY when we ALSO assume that <X> can actually do the opposite >>>>>>>>> of whatever value that H reports.
That is not an assumption. It follows from a series of truth >>>>>>>> preserving operations after making the assumption that an H that >>>>>>>> satisfies the above requirements exist.
When DD() is directly executed this is not the same DD instance
that is the actual input to HHH.
Doesn't matter. To be a solution to the halting problem, HHH(DD) >>>>>> is required to answer what would happen in the hypothetical case
that DD is executed directly.
The problem is defined such that H doesn't even get to look as that
one.
You're mistaking what HHH is being asked to compute for what HHH is
able to compute. The implementation doesn't dictate the requirements. >>>>
Another example of the limits of computation
no CAD system will ever be able to correctly
represent the geometric object of a square
circle in the same two dimensional plane.
So, we agree that the answer on the question: "Does an algorithm exist
that draws a square circle" is 'No'.
No system that computes the square-root will ever
correctly compute the square root of a box of cherries.
So, we agree that the answer on the question: "Does an algorithm exist
that computes the square root of a box of cherries" is 'No'.
The closest that H can possibly get to the actual behavior of its
input
is for H to simulate this input. H cannot execute <D> because <D> is >>>>> a finite string.
But remember the definition of a solution to the halting problem,
which states that H is required to answer what the algorithm /
program described by that finite string will do when executed directly: >>>>
No decider can be correctly required to report on the
behavior that it cannot see. The problem here is the
persistent false assumption that pathological self-reference
does not change behavior.
So we agree that the answer on the question: "Does an algorithm exist
that for all possible inputs returns whether it describes a halting
program in direct execution" is 'No'.
Only when the problem is defined to require H to return
a correct halt status value for an input that is actually
able to do the opposite of whatever value that H returns.
On 3/16/2025 2:14 PM, Fred. Zwarts wrote:
Op 16.mrt.2025 om 15:51 schreef olcott:
On 3/16/2025 8:40 AM, dbush wrote:
On 3/16/2025 12:25 AM, olcott wrote:
On 3/15/2025 10:51 PM, dbush wrote:
On 3/15/2025 11:28 PM, olcott wrote:
On 3/15/2025 10:09 PM, dbush wrote:
On 3/15/2025 10:58 PM, olcott wrote:
On 3/15/2025 9:43 PM, dbush wrote:
On 3/15/2025 10:30 PM, olcott wrote:
On 3/15/2025 9:23 PM, dbush wrote:
On 3/15/2025 9:30 PM, olcott wrote:
On 3/15/2025 5:37 PM, dbush wrote:
On 3/15/2025 5:34 PM, olcott wrote:
On 3/15/2025 4:54 AM, Mikko wrote:
On 2025-03-14 18:29:13 +0000, olcott said:
When DD() is directly executed this is not the same DD instanceThat is not an assumption. It follows from a series of truth >>>>>>>> preserving operations after making the assumption that an H that >>>>>>>> satisfies the above requirements exist.ONLY when we ALSO assume that <X> can actually do the opposite >>>>>>>>> of whatever value that H reports.The STUPIDLY false assumption
That an H exists that satisfies the following definition:
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
that is the actual input to HHH.
And since it *is* a possible input...So, we agree that the answer on the question: "Does an algorithm existAnother example of the limits of computation no CAD system will everDoesn't matter. To be a solution to the halting problem, HHH(DD) >>>>>> is required to answer what would happen in the hypothetical caseThe problem is defined such that H doesn't even get to look as that
that DD is executed directly.
one.
You're mistaking what HHH is being asked to compute for what HHH is
able to compute. The implementation doesn't dictate the
requirements.
be able to correctly represent the geometric object of a square circle
in the same two dimensional plane.
that draws a square circle" is 'No'.
No system that computes the square-root will ever correctly computeSo, we agree that the answer on the question: "Does an algorithm exist
the square root of a box of cherries.
that computes the square root of a box of cherries" is 'No'.
Only when the problem is defined to require H to return a correct haltNo decider can be correctly required to report on the behavior that itThe closest that H can possibly get to the actual behavior of its
input is for H to simulate this input. H cannot execute <D> because
<D> is a finite string.
But remember the definition of a solution to the halting problem,
which states that H is required to answer what the algorithm /
program described by that finite string will do when executed
directly:
cannot see. The problem here is the persistent false assumption that
pathological self-reference does not change behavior.
So we agree that the answer on the question: "Does an algorithm exist
that for all possible inputs returns whether it describes a halting
program in direct execution" is 'No'.
status value for an input that is actually able to do the opposite of whatever value that H returns.
Every polar (yes/no) question that lacks a correct yes or no answer isDisproving the assumption that a decider exists in the first place.
an incorrect polar question.
--So, we agree that the halting theorem is correct.
On 3/16/2025 7:44 AM, joes wrote:
Am Sat, 15 Mar 2025 23:25:25 -0500 schrieb olcott:
On 3/15/2025 10:51 PM, dbush wrote:
On 3/15/2025 11:28 PM, olcott wrote:
On 3/15/2025 10:09 PM, dbush wrote:
On 3/15/2025 10:58 PM, olcott wrote:
On 3/15/2025 9:43 PM, dbush wrote:
On 3/15/2025 10:30 PM, olcott wrote:
The problem is defined such that H doesn't even get to look as that one. >>> The closest that H can possibly get to the actual behavior of its inputWhen DD() is directly executed this is not the same DD instance that >>>>> is the actual input to HHH.That is not an assumption. It follows from a series of truthONLY when we ALSO assume that <X> can actually do the opposite of >>>>>>> whatever value that H reports.The STUPIDLY false assumption
That an H exists that satisfies the following definition:
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
preserving operations after making the assumption that an H that
satisfies the above requirements exist.
Doesn't matter. To be a solution to the halting problem, HHH(DD) is
required to answer what would happen in the hypothetical case that DD
is executed directly.
is for H to simulate this input. H cannot execute <D> because <D> is a
finite string.
H should be simulating the input AS IF it were executed directly.
_DDD()
[00002172] 55 push ebp ; housekeeping
[00002173] 8bec mov ebp,esp ; housekeeping
[00002175] 6872210000 push 00002172 ; push DDD
[0000217a] e853f4ffff call 000015d2 ; call HHH(DDD)
[0000217f] 83c404 add esp,+04
[00002182] 5d pop ebp
[00002183] c3 ret
Size in bytes:(0018) [00002183]
That would violate the semantics of the x86 language
that specifies that DDD remains stuck in recursive
emulation never reaching its own "ret" instruction
and terminating normally.
For the emulated DDD to behave the same as
the directly executed DDD it would have to
replace the machine code at its address 0000217a
with xor eax,eax (setting eax to 0) and never
calling HHH(DDD).
This would have the same behavior to outside observers
yet the failure to ever call HHH(DDD) still changes
the behavior.
That's
the meaning of a simulator. And you can certainly execute a string of
instructions. I don't know what that argument would buy you.
Anything else is not the halting problem but something else.
This goes back to my question, which I'll now ask a fourth time:
I want to know if any arbitrary algorithm X with input Y will halt when >>>> executed directly. If I had an H that could tell me that in *all*
possible cases, I could solve the Goldbach conjecture, among many other >>>> unsolved problems.
Does an H exist that can tell me that or not?
On 3/16/2025 3:20 PM, joes wrote:
Am Sun, 16 Mar 2025 14:32:38 -0500 schrieb olcott:
Only when the problem is defined to require H to return a correct halt
status value for an input that is actually able to do the opposite of
whatever value that H returns.
And since it *is* a possible input...A finite string is a possible input.
An executing process IS NOT A POSSIBLE INPUT.
Every polar (yes/no) question that lacks a correct yes or no answer is
an incorrect polar question.
Disproving the assumption that a decider exists in the first place.In the same way that no one can "decide" whether this sentence is true
or false: "What time is it?"
On 3/16/2025 3:20 PM, joes wrote:
Am Sun, 16 Mar 2025 14:32:38 -0500 schrieb olcott:
Only when the problem is defined to require H to return a correct halt
status value for an input that is actually able to do the opposite of
whatever value that H returns.
And since it *is* a possible input...
A finite string is a possible input.
An executing process IS NOT A POSSIBLE INPUT.
Every polar (yes/no) question that lacks a correct yes or no answer is
an incorrect polar question.
Disproving the assumption that a decider exists in the first place.
In the same way that no one can "decide" whether
this sentence is true or false: "What time is it?"
So, we agree that the halting theorem is correct.
On 3/16/25 7:33 PM, olcott wrote:
On 3/16/2025 3:20 PM, joes wrote:
Am Sun, 16 Mar 2025 14:32:38 -0500 schrieb olcott:A finite string is a possible input.
Only when the problem is defined to require H to return a correct
halt status value for an input that is actually able to do the
opposite of whatever value that H returns.
And since it *is* a possible input...
An executing process IS NOT A POSSIBLE INPUT.
So, I guess you don't understand what a program is, or how a compiler
can generate a program.
The "finite string" that defines the program, defines all the details
need to generate the behavior of that program, so the RESULTS of
executiong that program is a valid question.
In the same way that no one can "decide" whether this sentence is trueEvery polar (yes/no) question that lacks a correct yes or no answer
is an incorrect polar question.
Disproving the assumption that a decider exists in the first place.
or false: "What time is it?"
Sure it can, it can reject it as an incorrect statement, and thus not
true. (It doesn't need to say it is false, just not true).
On 3/16/2025 3:26 PM, Fred. Zwarts wrote:
Op 16.mrt.2025 om 20:32 schreef olcott:
On 3/16/2025 2:14 PM, Fred. Zwarts wrote:Read what I said: "all possible inputs". So, indeed, this input is
Op 16.mrt.2025 om 15:51 schreef olcott:
On 3/16/2025 8:40 AM, dbush wrote:
On 3/16/2025 12:25 AM, olcott wrote:
On 3/15/2025 10:51 PM, dbush wrote:
On 3/15/2025 11:28 PM, olcott wrote:
On 3/15/2025 10:09 PM, dbush wrote:
On 3/15/2025 10:58 PM, olcott wrote:
On 3/15/2025 9:43 PM, dbush wrote:
On 3/15/2025 10:30 PM, olcott wrote:
On 3/15/2025 9:23 PM, dbush wrote:
On 3/15/2025 9:30 PM, olcott wrote:
On 3/15/2025 5:37 PM, dbush wrote:Which arose as part of a false assumption, thereby proving >>>>>>>>>>>>>> the assumption false.
On 3/15/2025 5:34 PM, olcott wrote:The counter-example input is merely a logical impossibility >>>>>>>>>>>>>>
On 3/15/2025 4:54 AM, Mikko wrote:
On 2025-03-14 18:29:13 +0000, olcott said: >>>>>>>>>>>>>>>>>>
(1) What time is it (yes or no)?
(2) What integer X is > 5 and < 3?
(3) When we define the HP as having H return a value >>>>>>>>>>>>>>>>>>> corresponding to the halting behavior of input D >>>>>>>>>>>>>>>>>>> and input D can actually does the opposite of whatever >>>>>>>>>>>>>>>>>>> value that H returns, then we have boxed ourselves >>>>>>>>>>>>>>>>>>> in to a problem having no solution.
There are also problems that were defined with the >>>>>>>>>>>>>>>>>> idea that someone
would solve them but later turned out to be >>>>>>>>>>>>>>>>>> unsolvable, for example
angle trisection with straightedge and compass. >>>>>>>>>>>>>>>>>>
That a formal problem is unsolvable need not prevent >>>>>>>>>>>>>>>>>> solving similar
practical problem. A question like (1) is not useful >>>>>>>>>>>>>>>>>> for any practical
purpose so there is never any parctical need to ask >>>>>>>>>>>>>>>>>> it. The problem
(2) is so obviously unsolvable that everyone can try >>>>>>>>>>>>>>>>>> to avoid situations
where that solution would be needed. That (3) is >>>>>>>>>>>>>>>>>> unsolvable is not as
obvious and a solution would be useful, so someone >>>>>>>>>>>>>>>>>> might put some
considerable effort to solve it. Still, a partial >>>>>>>>>>>>>>>>>> solution, i.e. a method
that does not answer every input but produces the >>>>>>>>>>>>>>>>>> right answer in many
cases and never the wrong answer, can be useful for >>>>>>>>>>>>>>>>>> practical purposes.
When a problem is defined to have logically impossible >>>>>>>>>>>>>>>>> instances the inability to do the logically impossible >>>>>>>>>>>>>>>>> places no actual limitation on anything or anyone. >>>>>>>>>>>>>>>>>
The halting problem wasn't defined to be uncomputable. >>>>>>>>>>>>>>>> It would be very useful to have an H that can report if >>>>>>>>>>>>>>>> X(Y) halts when executed directly for *all* possible X >>>>>>>>>>>>>>>> and Y. It was later found that no such H exists. >>>>>>>>>>>>>>>
The STUPIDLY false assumption
That an H exists that satisfies the following definition: >>>>>>>>>>>>
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
ONLY when we ALSO assume that <X> can actually do the opposite >>>>>>>>>>> of whatever value that H reports.
That is not an assumption. It follows from a series of truth >>>>>>>>>> preserving operations after making the assumption that an H >>>>>>>>>> that satisfies the above requirements exist.
When DD() is directly executed this is not the same DD instance >>>>>>>>> that is the actual input to HHH.
Doesn't matter. To be a solution to the halting problem,
HHH(DD) is required to answer what would happen in the
hypothetical case that DD is executed directly.
The problem is defined such that H doesn't even get to look as
that one.
You're mistaking what HHH is being asked to compute for what HHH
is able to compute. The implementation doesn't dictate the
requirements.
Another example of the limits of computation
no CAD system will ever be able to correctly
represent the geometric object of a square
circle in the same two dimensional plane.
So, we agree that the answer on the question: "Does an algorithm
exist that draws a square circle" is 'No'.
No system that computes the square-root will ever
correctly compute the square root of a box of cherries.
So, we agree that the answer on the question: "Does an algorithm
exist that computes the square root of a box of cherries" is 'No'.
The closest that H can possibly get to the actual behavior of its >>>>>>> input
is for H to simulate this input. H cannot execute <D> because <D> is >>>>>>> a finite string.
But remember the definition of a solution to the halting problem,
which states that H is required to answer what the algorithm /
program described by that finite string will do when executed
directly:
No decider can be correctly required to report on the
behavior that it cannot see. The problem here is the
persistent false assumption that pathological self-reference
does not change behavior.
So we agree that the answer on the question: "Does an algorithm
exist that for all possible inputs returns whether it describes a
halting program in direct execution" is 'No'.
Only when the problem is defined to require H to return
a correct halt status value for an input that is actually
able to do the opposite of whatever value that H returns.
included. So we agree that no such algorithm exists.
Square_Root("This does not have a square root")
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 496 |
| Nodes: | 16 (4 / 12) |
| Uptime: | 54:01:22 |
| Calls: | 9,759 |
| Calls today: | 19 |
| Files: | 13,742 |
| Messages: | 6,185,022 |