Alan Turing's Halting Problem is incorrectly formed (PART-TWO)
Peter Olcott
http://www.netaxs.com/people/nerp/automata/halting2.html
Because of all of the dialogue of the other threads on this
subject I am able to state my position much more clearly.
Below is the best example yet of the proof of my point.
PREMISES:
(1) The Halting Problem was specified in such a way that a solution
was defined to be impossible.
(2) The set of questions that are defined to not have any possible
correct answer(s) forms a proper subset of all possible questions.
(3) Some questions that belong to this set are ill-formed.
(Example: What are the colors of the flag of the United States
of America in dollars and cents?)
(4) All the questions of this set have analogous properties such that
if one question of this set is ill-formed, then all questions of this set
are ill-formed.
CONCLUSION:
Therefore the Halting Problem is an ill-formed question.
George Greene
: Below is the link from which I am basing my discussion.
: http://www.netaxs.com/people/nerp/automata/halting2.html
We don't especially care.
All of US already KNOW what a TM is and what the Halting
Problem is, and if you want to have this discussion with
US, then you NEED to base your discussion on what WE think
the Halting Problem is, NOT what nerp thinks it is.
We're not going to waste our breath arguing with nerp if nerp
can't be bothered to show up.
: Because of all of the dialogue of the other threads on this
: subject I am able to state my position much more clearly.
: Below is the best example yet of the proof of my point.
:
: PREMISES:
: (1) The Halting Problem was specified in such a way that a solution
: was defined to be impossible.
That is false.
The problem has to do with the possible existence of something.
If it turns out that the something doesn't exist, that does NOT
mean that "the solution to the problem was defined to be impossible".
It just means that the sought thing simply does not exist.
It does not mean that that the definition of
the problem is flawed in any way. EVERYthing in math is a consequence
of definitions.
: (2) The set of questions that are defined to not have any possible
: correct answer(s) forms a proper subset of all possible questions.
That is also false. Within the context of this debate about TMs,
no set of questions is defined as having any correct answers.
Every question simply has the answer that it has.
On every input, every TM simply outputs what it outputs.
There is no possible way for any output to be "incorrect",
OR "correct". It IS possible for a PROGRAM, for a TM, ITSELF, to be
"incorrect" in the sense of failing to do something you
wanted it to, in the sense of failing to have some property
you wanted it to have. But there is no such thing as
an incorrect ANSWER. At best there is some CORRECT answer that
the proves that the PROGRAM was incorrect. If what you want
is a program that always halts yes/no where the output-answer
correctly tells whether its input M halts on its input w, then you are
guaranteeing that ALL possible programs are incorrect: NO TM-program
does THAT. But TM ANSWERS are NEVER "incorrect"; rather, they
just fail to describe halting. They CORRECTLY describe whatever
they DO describe; that just ISN'T halting.
: (3) Some questions that belong to this set are ill-formed.
: (Example: What are the colors of the flag of the United States
: of America in dollars and cents?)
This is completely irrelevant to any discussion about TMs.
There are no ill-formed questions in the TM universe unless
you are going to pre-stipulate that the infinite input tape
had infinitely many non-blank symbols distributed on it in
a non-recursive way, and even then, far from being "an ill-formed
question", that input tape will be (in VIRTUE of its ill-formedness)
simply NOT a question.
: (4) All the questions of this set have analogous properties such that
: if one question of this set is ill-formed, then all questions of this set
: are ill-formed.
All your talk about sets of questions is IRRELEVANT to the halting
problem.
--
--- The history of our nation has demonstrated that separate is seldom, if ever, equal.
--- (Feb.3,2004) Supreme Judicial Court of Massachusetts (4-3), adv.Sen.#2175
George Greene
: Therefore the Halting Problem is an ill-formed question.
If you are going to give us a natural-language definition of
"ill-formed question", then you might be able to salvage this.
But "the halting problem" is not, once you know the answer,
any sort of question at all.
ONCE THE ANSWER IS KNOWN, the "problem" disappears.
You could define "the shaving problem" (for a town)
as "Who (by name) is the barber (in this town) who shaves
all (and only) those (in this town) who don't shave themselves?".
This is a problem and a question but it is NOT ill-formed.
It just has "there is no such barber" as its EQUALLY-WELL-
formed ANSWER. The fact that "there is no such barber" is not
a barber's name does NOT make the question OR the answer "ill-
formed". It just means the question has a false presupposition.
"What is the name of the present king of France?"
is not ill-formed either, even though it gets precisely the
same kind of answer. The difference between these two examples
is that in the latter, the presupposition is false because of
concrete factual events, whereas in the former, it is false because
of something abstractly logical and therefore seemingly "definitional",
implying that something that WE have control over -- namely our
own DEFINITIONS of things -- might have caused the problem.
But the whole point in logic is that the definitions of things
like "and", "or", "not", and "all", DON'T change; we pretend that
we DON'T have control.
Once you SOLVE The Shaving Problem, The Shaving Problem CEASES TO EXIST.
Thereafter, you can't even POSE The Shaving Problem.
Thereafter, every time you get READY to pose The Shaving
Problem, you INSTEAD have to say, "In EVERY Town, there is
NO barber who shaves all&only those who don't shave themselves."
You sort of migrate from The Shaving Problem to The Non-Existence
of Russell's Barber. Over here in first-order logic, we migrated
from The Halting Problem to The Non-Existence of the Halt(,) TM.
George Greene
syntactically so much alike that you would be hard-pressed to allege
that one of these questions was well-formed and the other wasn't.
Assume (harmlessly) that TMs can be coded by individual numbers.
(1)
What is the smallest code of
a TM that takes (M,w) as input, where M is the code of a TM,
and halts when and only when M DOES halt on w?
This is a well-formed question and it has a well-formed answer; the answer
is the code of the smallest relevant Universal Turing Machine, and there
are plenty of papers in the literature pointing you to explicit definitions
of small Universal Turing Machines.
Now, consider another question differing from this one by ONLY ONE WORD.
In terms of form, these two questions are so similar that you cannot
hope to claim that one of them is well-formed while the other is ill-
formed.
(2)
What is the smallest code of
a TM that takes (M,w) as input, where M is the code of a TM,
and halts when and only when M DOESN'T halt on w?
There is no smallest code of such TMs because there
ARE NO such TMs. But there are plenty of TMs that are
"correct" for the spec in (1). And the fact that
no program satisfies a given spec does NOT imply
that the spec was "ill-formed".
The fact that there is no r satisfying
Ax[ rRx <-> ~ xRx ]
does NOT mean that that sentence is ill-formed.
It is just FALSE.
It is precisely because it is so WELL-formed that
we can SUCCEED in evaluating its truth-value enough,
or deriving it (or its denial) via inference rules,
to LEARN that it is always false. In the case of the
spec of a Halt(,) TM, it is precisely because the
spec is WELL-formed that we are ABLE to prove about it
that it is unsatisfiable.
Peter Olcott
> : (1) The Halting Problem was specified in such a way that a solution
> : was defined to be impossible.
>
> That is false.
> The problem has to do with the possible existence of something.
> If it turns out that the something doesn't exist, that does NOT
> mean that "the solution to the problem was defined to be impossible".
Yet this is not the case with the solution to the Halting Problem
(and square circles). In both these cases it is not merely that no
solution has been found to satisfy the requirements of the problem.
In BOTH these cases the problem is defined in such a way that
no solutions are possible. The lack of solution is directly derived
from the definition of the problem itself.
George Greene
: > : PREMISES:
: > : (1) The Halting Problem was specified in such a way that a solution
: > : was defined to be impossible.
: >
: > That is false.
: > The problem has to do with the possible existence of something.
: > If it turns out that the something doesn't exist, that does NOT
: > mean that "the solution to the problem was defined to be impossible".
"Peter Olcott" <olc...@worldnet.att.net> writes:
: Yet this is not the case with the solution to the Halting Problem
Yes, it is.
: (and square circles).
It's the same thing.
: In both these cases it is not merely that no
: solution has been found to satisfy the requirements of the problem.
How can you say "merely"?? In both cases it is the case
that no individual in the relevant domain satisfies
the requirements. Your "has been" is just plain evil: THERE IS NO
*TIME* involved here! EVERY last thing in the domain either does
or doesn't satisfy the requirements! AT THE *SAME* time! At ALL
times! NOW AND FOREVERmore!
: In BOTH these cases the problem is defined in such a way that
: no solutions are possible.
True, but IN MATH, it is ALWAYS like that!
The natural numbers have been defined in such a way that
no natural n can possibly satisfy the requirements of being > 2 and
having a corresponding x,y, and z such that x^n + y^n = z^n.
SO WHAT? Are you going to say that Fermat's Last Theorem is ILL-FORMED??
That is just stupid.
: The lack of solution is directly derived
: from the definition of the problem itself.
The lack of a solution to Fermat's Last Theorem is also
"directly derived from the definition of the problem itself".
IN MATH, EVERYthing is derived from definitions! BY DEFINITION!
In the case of the halting problem, what you are calling a
"solution" is starting to get complicated. There are TWO DIFFERENT
solutions to "the halting problem". If you define the problem by
"a solution to this problem is a TM-program that halts yes on (M,w)
when M halts on w and otherwise halts no", then yes, the problem
has no solutions.
But if you define "the halting problem" as "is there a TM that
always halts on (M,w) telling whether M halts on w?" then
the answer, "No, there is no such TM" (or, perhaps, rather,
a PROOF that there is no such TM) IS *ITSELF*THE* solution
to "the halting problem".
In EITHER case, NEITHER of these problem-definitions is flawed
or ill-formed as a definition. If the question is to find
a closed curve that is both circular and square, then the answer
is that there isn't one (or, rather, is a proof that there
isn't one). Ditto for a TM satisfying the Halt(,)
spec, or a barber shaving all&only those who don't shave themselves,
or a set containing all&only sets that don't contain themselves.
There are literally millions of properties with the meta-property
that you can't actually find even 1 thing having the property.
That does NOT make the properties or the associated problem of
finding something having them "ill-formed". It just means the
answer was no.
Acid Pooh
Your lack of understanding is astounding. Your "proof" is not a
proof. For one thing, it is based on false premises. Consider (1).
You state that "The Halting Problem was specified in such a way that
a solution was defined to be impossible." But solutions to questions
are not defined--they are found. Consider the equation x^2 = 4. For
what real values of x does x^2 = 4? Clearly, we can _find_ a
solution: 2 and -2. Now consider the equation x^2 = -4. For what
real values of x does x^2 = -4? Oh shit! There are no real values of
x which satisfy the equation. And yet, nobody (except you, perhaps?)
would call the second question ill-formed.
Now, if you look at the actual halting problem, it asks "Are there any
programs which can determine if an arbitrary program will halt?" We
can translate this easily into an analogous form as the above
question. "For what values of n will the Turing machine with Godel
number n determine if an arbitrary TM halts?" Again--none. This does
not mean that the question is ill-formed.
'cid 'ooh
Peter Olcott
> : no solutions are possible.
>
> True, but IN MATH, it is ALWAYS like that!
No its not. the question What is the third digit of PI to the right
of the decimal place has the answer of "1". This is a well-formed
question. When one asks what is the LAST digit of PI, then this
question was specifically defined to be unanswerable, thus
would be ill-formed.
> In EITHER case, NEITHER of these problem-definitions is flawed
> or ill-formed as a definition. If the question is to find
> a closed curve that is both circular and square, then the answer
> is that there isn't one (or, rather, is a proof that there
> isn't one). Ditto for a TM satisfying the Halt(,)
> spec, or a barber shaving all&only those who don't shave themselves,
> or a set containing all&only sets that don't contain themselves.
> There are literally millions of properties with the meta-property
> that you can't actually find even 1 thing having the property.
> That does NOT make the properties or the associated problem of
> finding something having them "ill-formed". It just means the
> answer was no.
In terms of constructing a basis for human communication that
is completely consistent, (what I typically refer to as treating
Natural Language as if it was a mathematical formalism,) I think
that it is useful (and required) that we define some statements
and questions as semantically ill-formed.
Thus if one asks is there a last digit to PI? this would be a
well-formed question, with the correct answer of "No".
If one were asked to provide the last digit to PI, then this would
be an ill-formed question with no possible correct answer, not
even "No" (it's not a numeric digit).
The Ghost In The Machine
<olc...@worldnet.att.net>
wrote
on Sun, 20 Jun 2004 16:31:12 GMT
<kZiBc.103407$Gx4....@bgtnsc04-news.ops.worldnet.att.net>:
One does have to be careful. The formulation on the
included page is slightly sloppy (thought straightforward);
a corrected formulation might be as follows.
Let Halt(m, i) be an algorithm. (Since all formulations of
machine simulations are equivalent, I am ignoring the exact
formulation, although it's clear there has to be (at least) one,
if we make this assumption.)
This algorithm can be encoded using a "standard" encoding,
yielding a code number 'h'. It's these code numbers that
Halt() is processing, not the actual machines -- feeding
a Turing machine to a Turing machine would indeed be silly;
one gets an image of a robot or person eating his own leg.
Construct Weird(i) in the usual fashion. I use
high-level pseudocode here, but one can equally well use
such things as Turing machines, infinite-integer-register
assembly code, flowcharts, etc. We might also assume a triplet
of computable functions: first(z) and second(z), which
basically split out x and y from the third function, z = pair(x,y).
The easiest method here might be to interleave bits;
I'll leave the details to the interested reader.
procedure Weird(integer i)
{
codenumber m = first(i);
if(Halt(m, i))
while true do
nothing;
else
return;
}
It's clear that, if Halt() is an algorithm, so is Weird(), though one
can quibble as to whether an algorithm is required to halt or not.
But even if Weird() is not an algorithm, it is a well-formed series
of code instructions, based on Halt(), which is also similarly
well-formed. Hence Weird() has a code number as well; we'll call
it 'w'. We'll also construct i, which is simply pair(w, 0). Since
Weird() ignores second(i) the second parameter could be anything,
really. We can notate Weird = Machine['w'], if we assume Machine
is a Universal Turing Machine or other such emulator.
And now we call Halt(w, i). Halt(w, i) will presumably
look at 'w' to see if Machine['w'] halts. If Halt(w, i)
indicates that the machine encoded by 'w' will halt on
input 'i', then we note that the machine is Weird, that
Weird(w,i) calls Halt(w,i) and therefore, if
Halt(w, i) returns 'true' then Machine['w'](i) = Weird(w, i)
must halt.
Except that it doesn't; therefore Halt(w, i) = 'true' is the wrong answer.
If Halt(w, i) returns 'false', then Weird(w, i) calls Halt(w, i),
gets its result (namely, 'false'), and this means it will never halt
on this input.
Except that it does; therefore Halt(w, i) = 'false' is also the wrong answer!
It is worth noting here that Weird() does not contain its
own encoding -- that is indeed impossible; it's similar to
a document containing its own MD5 hash code, and for much
the same reason. It's simply passing on what the caller requested --
which just happens to be Weird's encoding, but Weird doesn't "know" that.
I frankly fail to see a problem here. One either has a contradiction
or a misspecified algorithm (Halt is being naughty!); take your pick.
A more traditional variant might implement Weird thusly:
procedure Weird(integer i)
{
if(Halt(i, i))
while true do
nothing;
else
return;
}
which works just as well, if one calls Halt(w, w). Turing machines
don't have too much trouble copying a single integer, though
remembering the digit to copy might be a bit tricky, requiring
lots of replicated states (one per digit in the alphabet).
Infinite-integer-register simply does a MOV instruction.
If one wants to use infinite-integer-register assembly code, one can
simply define the encoding to be the machine code itself, assuming
the code is specified using position-independent constructs.
Halt might therefore take R1 and R2 as inputs and generate R0 as
output (0 = false, nonzero = true). Weird might do something
like:
Weird:
01 01 02 MOV R1,R2
10 04 CALL Halt
Here:
21 00 FD JNZ R0,Here
Stop:
00 HLT [or RET]
Halt:
[...]
and the encoding for 'w' would be most easily done in hex,
and start with 0x01010210042100FD00... (Jump and branch
instructions in my hypothetical scheme here base their
offsets on the address of the instruction following.
I've assumed here that an integer encodes itself if it's
in the range -64 to +63; for integers out of this range
one can get fancier; 127 (0x7f), for instance, might be
encoded 41 3f (-127 might be encoded BE C1), and 0x12345678
might be encoded 52 4D 45 59 38, by simply taking groups
of 6 bits and prefixing 01 or 10, except for the last byte.)
I am hoping David Matuszek is reading this. :-)
--
#191, ewi...@earthlink.net
It's still legal to go .sigless.
Peter Olcott
> > (1) The Halting Problem was specified in such a way that a solution
> > was defined to be impossible.
> Your lack of understanding is astounding. Your "proof" is not a
> proof. For one thing, it is based on false premises. Consider (1).
> You state that "The Halting Problem was specified in such a way that
> a solution was defined to be impossible." But solutions to questions
> are not defined--they are found.
It is not my lack of understanding here. I did not say that that solution
was defined. I said that the problem was defined. Problems ARE defined.
I will repeat the concrete example that I provided to the other respondent:
A well formed question that has a correct answer:
Does PI have a last digit? ANSWER: No
An ill formed question that has been defined to have no correct answer:
What is the last digit of PI? (note the answer must be a numeric digit).
> Consider the equation x^2 = 4. For
> what real values of x does x^2 = 4? Clearly, we can _find_ a
> solution: 2 and -2. Now consider the equation x^2 = -4. For what
> real values of x does x^2 = -4? Oh shit! There are no real values of
> x which satisfy the equation. And yet, nobody (except you, perhaps?)
> would call the second question ill-formed.
Try to imagine that we are not talking so much about the Halting Problem
itself, but, instead very subtle nuances of the meaning of words in a
sentence, as they apply to the Halting Problem.
As soon as your example would form the basis for a claim that the process
of deriving the square root of a number is incomplete because it does not
work for negative numbers, then either the question (or the claim) would
become ill-formed.
Its like saying that fire doesn't work because stainless steel can not be
lit on
fire with a match. When the test case of a process falls outside of the
domain
of the process, then the test case becomes invalid for this process.
Jon Haugsand
> > > PREMISES:
> > > (1) The Halting Problem was specified in such a way that a solution
> > > was defined to be impossible.
>I did not say that that solution
> was defined. I said that the problem was defined.
Maybe I need glasses, but to me the phrase "a solution was defined" is
a part of the first quote.
--
Jon Haugsand
Dept. of Informatics, Univ. of Oslo, Norway, mailto:jon...@ifi.uio.no
http://www.ifi.uio.no/~jonhaug/, Phone: +47 22 85 24 92
Sander Bruggink
> No its not. the question What is the third digit of PI to the right
> of the decimal place has the answer of "1". This is a well-formed
> question. When one asks what is the LAST digit of PI, then this
> question was specifically defined to be unanswerable, thus
> would be ill-formed.
When you are doing analogies, you should always pick the right
analogies. The question
(1) What is the last decimal of PI? (Answer: doesn't exist)
is somewhat analogous to the question:
(2) How is the TM defined which decides whether a given TM halts on
input x? (Answer: doesn't exist)
The question
(3) Does PI have a last decimal? (Answer: NO)
is analogous to the question:
(4) Does a TM exist which decides whether a given TM halts on input x?
(Answer: NO)
> In terms of constructing a basis for human communication that
> is completely consistent, (what I typically refer to as treating
> Natural Language as if it was a mathematical formalism,) I think
> that it is useful (and required) that we define some statements
> and questions as semantically ill-formed.
No. If you are treating natural language as a mathematical formalism,
you should distinguish syntactical and semantical notions. Syntax is
about "form", semantics about "meaning". "Semantically ill-formed" is
therefore inconsistent terminology. Since you seem to be an expert on
"pathological self-references", I will restate the point of this
paragraph in a more or less pathological self-referential way:
"The notion 'semantically ill-formed' is semantically ill-formed." ;-)
>
> Thus if one asks is there a last digit to PI? this would be a
> well-formed question, with the correct answer of "No".
Indeed.
> If one were asked to provide the last digit to PI, then this would
> be an ill-formed question with no possible correct answer, not
> even "No" (it's not a numeric digit).
It's a well-formed (syntactically correct) question, with no possible
answer ("ill-meaned"). And it has nothing whatsoever to do, not even in
an analogy, with the halting problem (see beginning of this post).
groente
-- Sander
Daryl McCullough
>PREMISES:
>(1) The Halting Problem was specified in such a way that a solution
>was defined to be impossible.
It wasn't *defined* to be impossible, it was *proved* to be
impossible.
>(2) The set of questions that are defined to not have any possible
>correct answer(s) forms a proper subset of all possible questions.
The question of "Does program P halt on input x?" *always* has
an answer---it's not defined to not have any possible correct
answer. It is just that no *single* program can correctly answer
*all* such questions.
You are confusing two different statements:
1. For all programs H, there is a question (of the form
"Does P halt on input q?") that H cannot correctly answer.
2. There is a question (of the form "Does P halt on input q?")
that no program can correctly answer.
1. is true, but 2. is false.
>(3) Some questions that belong to this set are ill-formed.
The question of "Does P halt on input q?" is not in that set,
so that set is irrelevant to the halting problem.
--
Daryl McCullough
Ithaca, NY
Chris Menzel
> A well formed question that has a correct answer:
> Does PI have a last digit? ANSWER: No
Is there a Turing machine that, when given as input (a code for) an
arbitrary Turing Machine M and input I for M, returns 1 if M halts on I,
and 0 otherwise? ANSWER: no
So the Halting Problem (in this guise, at least) is well formed. Good.
Chris Menzel
Peter Olcott
> you should distinguish syntactical and semantical notions. Syntax is
> about "form", semantics about "meaning". "Semantically ill-formed" is
> therefore inconsistent terminology. Since you seem to be an expert on
> "pathological self-references", I will restate the point of this
> paragraph in a more or less pathological self-referential way:
>
> "The notion 'semantically ill-formed' is semantically ill-formed." ;-)
The primary definition of {ill formed} is wrongly formed.
The secondary definition of ill formed pertains to syntax.
I try to always restrict myself to primary definitions.
> > Thus if one asks is there a last digit to PI? this would be a
> > well-formed question, with the correct answer of "No".
>
> Indeed.
>
>
> > If one were asked to provide the last digit to PI, then this would
> > be an ill-formed question with no possible correct answer, not
> > even "No" (it's not a numeric digit).
>
> It's a well-formed (syntactically correct) question, with no possible
> answer ("ill-meaned"). And it has nothing whatsoever to do, not even in
> an analogy, with the halting problem (see beginning of this post).
It does, but let's get past the ill-formed, issue first, then I will
proceed to show how it does.
Peter Olcott
"Jon Haugsand" <jon...@ifi.uio.no> wrote in message
news:dmn02xu...@palamos.ifi.uio.no...
> * Peter Olcott
> > > > PREMISES:
> > > > (1) The Halting Problem was specified in such a way that a solution
> > > > was defined to be impossible.
>
> >I did not say that that solution
> > was defined. I said that the problem was defined.
>
> Maybe I need glasses, but to me the phrase "a solution was defined" is
> a part of the first quote.
I will rephrase it to be more clear:
The problem was defined in such a way that makes a solution
impossible to achieve.
It is like asking for the last digit of PI, and only accepting a numeric
digit answer.
When I say that the problem was defined to make a solution impossible
I am referring to the specific counter-example test case that the Halt()
function must fail.
function LoopIfHalts (M, w):
if WillHalt (M, w) then
while true do {}
else
return false;
Specifically because the Halt() function must fail this test case,
the Halting Problem asserts that determining whether or not
any program will halt is necessarily incomplete.
My contention is that the Halting Problem assertion is exactly
analogous to saying that SquareRoot() is necessarily incomplete
because it does not work for negative numbers.
Peter Olcott
"Chris Menzel" <cme...@remove-this.tamu.edu> wrote in message
news:slrncde2nc...@philebus.tamu.edu...
Until you analyze why this answer is No.
Basically what I am saying is that the Halt() function can work
correctly on every correctly-formed TM, and thus any TM that
the Halt() function can not work correctly on, is thus not correctly
formed.
Peter Olcott
news:cb6pb...@drn.newsguy.com...
> Peter Olcott says...
>
> >PREMISES:
> >(1) The Halting Problem was specified in such a way that a solution
> >was defined to be impossible.
>
> It wasn't *defined* to be impossible, it was *proved* to be
> impossible.
The term domain is most commonly used to describe the set of values
D for which a function (map, transformation, etc.) is defined.
Let me rephrase my statement.
The Halt() function can work correctly over every element in its
domain.
function LoopIfHalts (M, w):
if WillHalt (M, w) then
while true do {}
else
return false;
Using the above program as a test case for the Halt() function
is like using -1 as the test case for a SquareRoot() function.
Chris Menzel
>
> "Chris Menzel" <cme...@remove-this.tamu.edu> wrote in message
> news:slrncde2nc...@philebus.tamu.edu...
> > On Mon, 21 Jun 2004 11:46:51 GMT, Peter Olcott <olc...@worldnet.att.net>
> said:
> > > A well formed question that has a correct answer:
> > > Does PI have a last digit? ANSWER: No
> >
> > Is there a Turing machine that, when given as input (a code for) an
> > arbitrary Turing Machine M and input I for M, returns 1 if M halts on I,
> > and 0 otherwise? ANSWER: no
> >
> > So the Halting Problem (in this guise, at least) is well formed. Good.
>
> Basically what I am saying is that the Halt() function can work
> correctly on every correctly-formed TM, and thus any TM that the
> Halt() function can not work correctly on, is thus not correctly
> formed.
Halt is just a function of 2 arguments. Given two numbers (coding a TM
and some input for it), its value is either 1 or 0. The idea of it
"working correctly" has no meaning here. You seem to be confusing
functions with programs. Or something.
Chris Menzel
Daryl McCullough
>The primary definition of {ill formed} is wrongly formed.
>The secondary definition of ill formed pertains to syntax.
"Form" and "syntax" mean the same thing.
Daryl McCullough
>Let me rephrase my statement.
>The Halt() function can work correctly over every element in its
>domain.
Its domain is defined to be the set of *all* pairs of strings
p and q. So, no, you are wrong.
You can certainly define a *limited* halt function. There
are certainly restricted sets of programs D such that there
is a halt function H_D that works on programs in set D. But
any such domain D must *either* be undecidable (there is
no way to know whether a program is in D or not), or must
be incomplete (there are some computable functions that
are not included in D).
To see this, assume that D is some decidable domain of
programs, which means that there is a program Valid_D(x)
which returns true if x is a program in D, and returns
false otherwise. Assume that there is a program H_D(x,y)
that solves the halting problem for domain D. That means
that
H_D(x,y) = true if x is a program in D
and x halts on input y
= false if x is a program in D
and x does not halt on input y
Then define a new function that takes strings as inputs and
returns booleans as follows:
f(x) =
if Valid_D(x) and H_D(x,x) and the return type of program x
is boolean, then return the negation of the result of running
x on input x,
otherwise, return false.
It's clear that if Valid_D is computable, and H_D is computable, then
f is computable. But it is also clear that f(x) cannot be a program in
domain D.
Daryl McCullough
>Basically what I am saying is that the Halt() function can work
>correctly on every correctly-formed TM, and thus any TM that
>the Halt() function can not work correctly on, is thus not correctly
>formed.
But basically, you are wrong.
Martin Shobe
What do you mean by a correctly-formed TM?
Martin
Peter Olcott
That is either a stupid or an ignorant statement.
Counter-example proof:
When someone forms something of clay, they are
not syntaxing something of clay.
Peter Olcott
> and some input for it), its value is either 1 or 0. The idea of it
> "working correctly" has no meaning here. You seem to be confusing
> functions with programs. Or something.
You left some details out. You forget that this definition specifies
an abstract machine that is the basis for the Turing thesis:
any computational process, such as those carried out by
present day computers, can be done on a Turing machine.
Here is the detail that many of you fail to get:
Because any computation can be accomplished on a Turing Machine,
therefore mathematical mappings of higher level abstractions to the
low level physical implementation (the Turing Machine itself) occur.
Because these mathematical mappings do occur, and are required,
it IS correct to refer to aspects of these higher level abstractions
as if they were directly represented by the Turing Machine.
Ultimately the argument that you are asserting would be analogous
to saying that there is no such thing as a spread-sheet because at the
computer circuit level all we have is (AND, OR and NOT) gates.
Daryl McCullough
>
>
>"Daryl McCullough" <da...@atc-nycorp.com> wrote
>> >The primary definition of {ill formed} is wrongly formed.
>> >The secondary definition of ill formed pertains to syntax.
>>
>> "Form" and "syntax" mean the same thing.
>That is either a stupid or an ignorant statement.
Think about the context of this discussion, Peter. In
the context of a computer program, what is the difference between
the "form" of a program and the "syntax" of a program?
The Ghost In The Machine
<6MJBc.111142$Gx4....@bgtnsc04-news.ops.worldnet.att.net>:
Did you want to quasi-Russelize this or something?
An interesting notion; level 0 programs would be primitive
recursive, level 1 programs would contain level 0 programs
and while loops, level 2 programs would contain level 1
programs and while loops, ...
In that case, one can write a level 2 Halt() to check level 1 programs.
Maybe.
Daryl McCullough
>My contention is that the Halting Problem assertion is exactly
>analogous to saying that SquareRoot() is necessarily incomplete
>because it does not work for negative numbers.
Yes, that's your contention, but you're completely wrong. There
is no analogy between the two cases. In the case of square-root,
there *is* no answer to the question
What real number x solves x*x = -1?
In contrast, the question
Does program P halt on input q?
always has an answer. It's just that there is no *program*
that can always give the correct answer.
David C. Ullrich
If I weren't afraid you'd try to explain I'd ask how in the
world you deduce that he doesn't understand that from what
he said.
************************
David C. Ullrich
Chris Menzel
> > Halt is just a function of 2 arguments. Given two numbers (coding a TM
> > and some input for it), its value is either 1 or 0. The idea of it
> > "working correctly" has no meaning here. You seem to be confusing
> > functions with programs. Or something.
>
> You left some details out. You forget that this definition specifies
> an abstract machine that is the basis for the Turing thesis:
Not a promising start.
> any computational process, such as those carried out by
> present day computers, can be done on a Turing machine.
So I've heard.
> Here is the detail that many of you fail to get:
>
> Because any computation can be accomplished on a Turing Machine,
> therefore mathematical mappings of higher level abstractions to the
> low level physical implementation (the Turing Machine itself) occur.
Hm, so you think a TM has something to do with physical implementations.
I'd say failing to "get" that detail would be a virtue.
> Because these mathematical mappings do occur, and are required,
> it IS correct to refer to aspects of these higher level abstractions
> as if they were directly represented by the Turing Machine.
>
> Ultimately the argument that you are asserting would be analogous
> to saying that there is no such thing as a spread-sheet because at the
> computer circuit level all we have is (AND, OR and NOT) gates.
Well, I'm afraid I can't whack my way through this thicket, but, as
noted, a few things stand out. Notably, you distinguish the idea of an
abstract machine from a Turing machine; and you think that a TM has
something to do with "low level physical implementation". This suggests
that you are very confused about what TMs are (and might explain why you
think some notion of "working correctly" is relevant in this
discussion). How about you clear things up and tell us what you think a
TM is?
Chris Menzel
Peter Olcott
> Peter Olcott says...
>
> >Basically what I am saying is that the Halt() function can work
> >correctly on every correctly-formed TM, and thus any TM that
> >the Halt() function can not work correctly on, is thus not correctly
> >formed.
>
> But basically, you are wrong.
Yet no one has been able to show this yet.
They have not been able to show this because I am not wrong.
Asking for the last digit of PI is an incorrectly formed question.
Asking the Halt() function to determine if the counter-example
program Halts() IS analogous to asking for the last digit of PI.
(Both have been defined to have no correct answer).
Peter Olcott
The Semantics of the program. Well formed syntax can still
leave incorrect semantics.
Peter Olcott
>
> In contrast, the question
>
> Does program P halt on input q?
>
> always has an answer. It's just that there is no *program*
> that can always give the correct answer.
Just like there is no program that can give the correct SquareRoot()
for the set of real numbers (including negative numbers) Halt() can
not determine if any program (including incorrectly formed programs)
will halt.
Peter Olcott
"David C. Ullrich" <ull...@math.okstate.edu> wrote in message
news:a03hd09nh7t49h8vj...@4ax.com...
> On Tue, 22 Jun 2004 12:11:19 GMT, "Peter Olcott"
> <olc...@worldnet.att.net> wrote:
>
> >> Halt is just a function of 2 arguments. Given two numbers (coding a TM
> >> and some input for it), its value is either 1 or 0. The idea of it
> >> "working correctly" has no meaning here. You seem to be confusing
> >> functions with programs. Or something.
> If I weren't afraid you'd try to explain I'd ask how in the
> world you deduce that he doesn't understand that from what
> he said.
I'll re-quote:
Peter Olcott
> I'd say failing to "get" that detail would be a virtue.
A TM is a specific definition of a particular physical implementation.
>
> > Because these mathematical mappings do occur, and are required,
> > it IS correct to refer to aspects of these higher level abstractions
> > as if they were directly represented by the Turing Machine.
> >
> > Ultimately the argument that you are asserting would be analogous
> > to saying that there is no such thing as a spread-sheet because at the
> > computer circuit level all we have is (AND, OR and NOT) gates.
>
> Well, I'm afraid I can't whack my way through this thicket, but, as
> noted, a few things stand out. Notably, you distinguish the idea of an
> abstract machine from a Turing machine; and you think that a TM has
> something to do with "low level physical implementation". This suggests
> that you are very confused about what TMs are (and might explain why you
> think some notion of "working correctly" is relevant in this
> discussion). How about you clear things up and tell us what you think a
> TM is?
>
> Chris Menzel
I know what a TM is, I have a copy of "An Introduction to Formal
Languages and Automata" by Peter Lentz. Why don't you demonstrate
some knowledge that can not merely be copied verbatim from a book,
or otherwise tell us what your credentials are?
Peter Olcott
> >Basically what I am saying is that the Halt() function can work
> >correctly on every correctly-formed TM, and thus any TM that
> >the Halt() function can not work correctly on, is thus not correctly
> >formed.
> >
>
> What do you mean by a correctly-formed TM?
>
basic definition. In the case of the Halting Problem the
definition must be much more precise. Most any program
that has a non-functional infinite loop would be incorrectly
formed. (Note MS Windows programs have functional
infinite loops, waiting for the user input).
Peter Olcott
> Peter Olcott says...
>
> >Let me rephrase my statement.
> >The Halt() function can work correctly over every element in its
> >domain.
>
> Its domain is defined to be the set of *all* pairs of strings
> p and q. So, no, you are wrong.
Then the domain is defined incorrectly. It's just like defining
the domain of all real numbers for SquareRoot.
> You can certainly define a *limited* halt function. There
> are certainly restricted sets of programs D such that there
> is a halt function H_D that works on programs in set D. But
> any such domain D must *either* be undecidable (there is
> no way to know whether a program is in D or not), or must
> be incomplete (there are some computable functions that
> are not included in D).
Ah, but the counter-example program is not computable.
You are asking a Yes / No question, and the answer lies
outside this set.
You can ask the question can there possibly exist any program
or function that can correctly determine whether any other
program will halt that answer is a flat "no".
When you ask WHY this is so, it is because there can possibly
be formed a program where the answer to the question:
"Does this Program halt?" has no correct (yes or no) answer,
yet you have already limited the possible answers to (yes or no)
so it is your limitation of this question's answer to (yes or no)
that creates the impossible (thus incorrectly formed) question.
Daryl McCullough
>> Peter Olcott says...
>>
>> >Let me rephrase my statement.
>> >The Halt() function can work correctly over every element in its
>> >domain.
>>
>> Its domain is defined to be the set of *all* pairs of strings
>> p and q. So, no, you are wrong.
>
>Then the domain is defined incorrectly. It's just like defining
>the domain of all real numbers for SquareRoot.
No, it's nothing like that. "What real number squared is
equal to -1?" has no answer. But "Does program P halt on
input q?" does have an answer.
>> You can certainly define a *limited* halt function. There
>> are certainly restricted sets of programs D such that there
>> is a halt function H_D that works on programs in set D. But
>> any such domain D must *either* be undecidable (there is
>> no way to know whether a program is in D or not), or must
>> be incomplete (there are some computable functions that
>> are not included in D).
>
>Ah, but the counter-example program is not computable.
That's a complete falsehood. If the domain D is decidable,
and the halt function for that domain is computable, then
the counter-example (a computable function that is not
in domain D) is computable. I *showed* you how to compute
it.
You just seem to spout anything off the top of your
head, without caring whether it is true, or not.
Daryl McCullough
>"Daryl McCullough" <da...@atc-nycorp.com> wrote
>> But basically, you are wrong.
>
>Yet no one has been able to show this yet.
You've been shown to be wrong dozens of times,
by dozens of people.
Daryl McCullough
>
>> What real number x solves x*x = -1?
>>
>> In contrast, the question
>>
>> Does program P halt on input q?
>>
>> always has an answer. It's just that there is no *program*
>> that can always give the correct answer.
>
>Just like there is no program that can give the correct SquareRoot()
>for the set of real numbers
No, it's nothing like that case.
There *is* no real number whose square is -1. That's different
from the case of the question "Does P halt on input q?" which
has an answer.
If Q is the program
Q(x) : if H(x,x) then loop forever, otherwise halt
then Q is a perfectly good program, and the question
"Does Q halt when given its own program as input?" is
a perfectly good question. We can even *compute* the
answer to that question: Just run H(Q,Q). If it returns
"true", then Q never halts when given its own program
as input. If H(Q,Q) returns "false", then Q does halt
when given its own program as input.
There is nothing invalid about program Q, and there
is nothing ill-formed about the question of whether
Q halts on its own input.
Barb Knox
da...@atc-nycorp.com (Daryl McCullough) wrote:
>Peter Olcott says...
>
>>"Daryl McCullough" <da...@atc-nycorp.com> wrote
>
>>> But basically, you are wrong.
>>
>>Yet no one has been able to show this yet.
>
>You've been shown to be wrong dozens of times,
>by dozens of people.
I think what he means is that no-one has been able to show HIM that he's wrong
(even though it's obvious to almost everyone else).
Given his apparently adamantine faith in his own rightness, I expect that
there is no point in further attempting to show him.
--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb |
| B B a a r b b |
| BBB aa a r bbb |
-----------------------------
Barb Knox
"Peter Olcott" <olc...@worldnet.att.net> wrote:
[snip]
> there can possibly
>be formed a program where the answer to the question:
>"Does this Program halt?" has no correct (yes or no) answer,
[snip]
Ignoring my own advice just now posted previously in this thread, I will
attempt to show you that that is flatly incorrect.
Given ANY particular program P, there *is* an effective procedure that says
whether or not it halts. The procedure is one of these two:
(H1) return "yes"
(H2) return "no"
Both these are effective procedures, and one of them (although we may not know
which one) gives the correct answer.
So the halting problem has a solution for any SINGLE program. What doesn't
have a solution is the halting problem for ALL programs together: given some
enumeration of all programs, NO ALGORITHM CAN GENERATE the sequence of yesses
and noes that gives the correct answer for every program in the enumeration.
BTW, this sequence (using 1 and 0 for yes and no) viewed as a binary fraction
is Chaitin's uncomputable Omega number.
Peter Olcott
> by dozens of people.
You didn't even bother to read the rest of my
point. If you don't read what I say, how can you
know that I am wrong?
Peter Olcott
> equal to -1?" has no answer. But "Does program P halt on
> input q?" does have an answer.
function LoopIfHalts (M, w):
if WillHalt (M, w) then
while true do {}
else
return false;
Okay then you tell me the answer
Does the above program halt?
Peter Olcott
> >be formed a program where the answer to the question:
> >"Does this Program halt?" has no correct (yes or no) answer,
> [snip]
>
> Ignoring my own advice just now posted previously in this thread, I will
> attempt to show you that that is flatly incorrect.
function LoopIfHalts (M, w):
if WillHalt (M, w) then
while true do {}
else
return false;
Okay then you tell me does the above program halt?
(or is it defined to have no correct to the question:
Does it halt?) *** NOTE *** Only Yes or No
are acceptable answers, any other answer is defined
to be incorrect.
Barb Knox
"Peter Olcott" <olcott@.att.net> wrote:
>> > there can possibly
>> >be formed a program where the answer to the question:
>> >"Does this Program halt?" has no correct (yes or no) answer,
>> [snip]
>>
>> Ignoring my own advice just now posted previously in this thread, I will
>> attempt to show you that that is flatly incorrect.
>
>function LoopIfHalts (M, w):
> if WillHalt (M, w) then
> while true do {}
> else
> return false;
>
>Okay then you tell me does the above program halt?
Be glad to, but first you need to give me the WHOLE program. In particular,
you need to show me the code for the function named "WillHalt" in the program.
Clearly, the behaviour of LoopIfHalts depends on the behaviour of the
so-called WillHalt.
>(or is it defined to have no correct to the question:
>Does it halt?)
EVERY program either halts or not, yes or no. But you haven't fully specified
a program here. E.g., if you feed it into a compiler it will complain about
the undefined function.
> *** NOTE *** Only Yes or No
>are acceptable answers, any other answer is defined
>to be incorrect.
--
Chris Menzel
>
> "Daryl McCullough" <da...@atc-nycorp.com> wrote in message
> news:cb864...@drn.newsguy.com...
> > Peter Olcott says...
> >
> > >Basically what I am saying is that the Halt() function can work
> > >correctly on every correctly-formed TM, and thus any TM that
> > >the Halt() function can not work correctly on, is thus not correctly
> > >formed.
> >
> > But basically, you are wrong.
>
> Yet no one has been able to show this yet.
> They have not been able to show this because I am not wrong.
The sad truth is that, on this point and many others, you mistake your
inability to see when you have been shown wrong with not being shown
wrong.
-cm
Peter Olcott
> > if WillHalt (M, w) then
> > while true do {}
> > else
> > return false;
> >
> >Okay then you tell me does the above program halt?
>
> Be glad to, but first you need to give me the WHOLE program. In
particular,
> you need to show me the code for the function named "WillHalt" in the
program.
> Clearly, the behaviour of LoopIfHalts depends on the behaviour of the
> so-called WillHalt.
You are the function WillHalt() what is your answer (Yes or No)
will this program halt? You are far superior to any mere Turing
Machine, aren't you? Certainly you can answer whether this program
will halt, can't you?
It is an answerable question isn't it?
That's what all my detractors have been so adamantly claiming,
after all every Turing Machine either halts or fails to halt.
Barb Knox
"Peter Olcott" <olc...@worldnet.att.net> wrote:
>> >function LoopIfHalts (M, w):
>> > if WillHalt (M, w) then
>> > while true do {}
>> > else
>> > return false;
>> >
>> >Okay then you tell me does the above program halt?
>>
>> Be glad to, but first you need to give me the WHOLE program. In
>particular,
>> you need to show me the code for the function named "WillHalt" in the
>program.
>> Clearly, the behaviour of LoopIfHalts depends on the behaviour of the
>> so-called WillHalt.
>
>You are the function WillHalt() what is your answer (Yes or No)
>will this program halt? You are far superior to any mere Turing
>Machine, aren't you?
Am I? Turing Machines have unlimited memory, whereas AFAIK I don't.
> Certainly you can answer whether this program
>will halt, can't you?
IF you actually follow the rules and FULLY SPECIFY A PROGRAM then I can indeed
give you an effective procedure for telling if it will halt.
>It is an answerable question isn't it?
If you bother to actually fully specify a program, it is. My assertion is
about programs, not about partial programs plus whatever other weirdness
you're trying to throw into the mix.
>That's what all my detractors have been so adamantly claiming,
>after all every Turing Machine either halts or fails to halt.
So you agree with that now? If so, good. If not, how about actually showing
us one of these programs that neither halts nor fails to halt. Frankly, even
in comparison with the other loonies who have haunted sci.logic, I find it
BIZARRE that you can conceive that a TM might neither halt (i.e. reach a stop
state after some finite number N of steps) nor not halt (i.e. NOT reach a stop
state after any finite number of steps). Really now, what other logical
possibilities might there conceivably be?
Acid Pooh
Although he stated his position very poorly, I believe he was
referring to the analogy I made (which included a reformulation of the
halting problem: "For what values of n will the Turing machine with
Godel number n determine if an arbitrary TM halts?"). My intention
was to show him this analogy and hope he doesn't think that the
square-root question isn't ill formed. Apparently he does. What a
maroon.
On a positive note, it appears that he actually does pay attention.
So there is still hope.
'cid 'ooh
Chris Menzel
> > Hm, so you think a TM has something to do with physical implementations.
> > I'd say failing to "get" that detail would be a virtue.
>
> A TM is a specific definition of a particular physical
> implementation.
Not by any definition anywhere. No wonder your claims about
computability and the Halting problem are so confused: You don't even
know what Turing machine is.
> > > Because these mathematical mappings do occur, and are required,
> > > it IS correct to refer to aspects of these higher level abstractions
> > > as if they were directly represented by the Turing Machine.
> > >
> > > Ultimately the argument that you are asserting would be analogous
> > > to saying that there is no such thing as a spread-sheet because at the
> > > computer circuit level all we have is (AND, OR and NOT) gates.
> >
> > Well, I'm afraid I can't whack my way through this thicket, but, as
> > noted, a few things stand out. Notably, you distinguish the idea of an
> > abstract machine from a Turing machine; and you think that a TM has
> > something to do with "low level physical implementation". This suggests
> > that you are very confused about what TMs are (and might explain why you
> > think some notion of "working correctly" is relevant in this
> > discussion). How about you clear things up and tell us what you think a
> > TM is?
>
> I know what a TM is,
You have yet to demonstrate that you do; indeed, you have amply
demonstrated that you do NOT -- for example, your belief that a TM is a
"a definition of particular physical implementation" when in fact a TM
is exactly NOT connected to any particular physical implementation.
> I have a copy of "An Introduction to Formal Languages and Automata" by
> Peter Lentz.
I have a copy of Meisner, Thorne and Wheeler, but I don't know jack
about general relativity.
BTW, this would be the book by Peter Lentz in which he purports to
demonstrates that the Halting Problem is undecidable? Why do you trust
anything in a book you think contains egregious errors?
> Why don't you demonstrate some knowledge that can not merely be copied
> verbatim from a book,
What would be the point of demonstrating my capacity for original
research in a post whose purpose is to point out your errors?
> or otherwise tell us what your credentials are?
Don't try to muddy the waters by changing the subject. You're the one
making outrageous claims that contradict well known, widely researched,
and exceedingly well understood results in computability theory when you
apparently don't even understand one its most BASIC notions.
Chris Menzel
|-|erc
|-|erc
> >The Halt() function can work correctly over every element in its
> >domain.
>
> Its domain is defined to be the set of *all* pairs of strings
> p and q. So, no, you are wrong.
>
> are certainly restricted sets of programs D such that there
> is a halt function H_D that works on programs in set D. But
> any such domain D must *either* be undecidable (there is
> no way to know whether a program is in D or not), or must
> be incomplete (there are some computable functions that
> are not included in D).
>
> programs, which means that there is a program Valid_D(x)
> which returns true if x is a program in D, and returns
> false otherwise. Assume that there is a program H_D(x,y)
> that solves the halting problem for domain D. That means
> that
>
> H_D(x,y) = true if x is a program in D
> and x halts on input y
> = false if x is a program in D
> and x does not halt on input y
>
> Then define a new function that takes strings as inputs and
> returns booleans as follows:
>
> f(x) =
> if Valid_D(x) and H_D(x,x) and the return type of program x
> is boolean, then return the negation of the result of running
> x on input x,
> otherwise, return false.
>
> It's clear that if Valid_D is computable, and H_D is computable, then
> f is computable. But it is also clear that f(x) cannot be a program in
> domain D.
>
Right!
But whether it fits in scope of this :
there are some computable functions that are not included in D
since f is an 'ill defined' program, D can still be equivalent in power to
the set of all TMs. ~D are just "junk", they don't do anything useful.
halting problem solved!
Herc
|-|erc
> >> Clearly, the behaviour of LoopIfHalts depends on the behaviour of the
> >> so-called WillHalt.
> >
> >You are the function WillHalt() what is your answer (Yes or No)
> >will this program halt? You are far superior to any mere Turing
> >Machine, aren't you?
>
> Am I? Turing Machines have unlimited memory, whereas AFAIK I don't.
you can use an external tape, we can allow that.
>
> > Certainly you can answer whether this program
> >will halt, can't you?
>
> IF you actually follow the rules and FULLY SPECIFY A PROGRAM then I can indeed
> give you an effective procedure for telling if it will halt.
just a Yes or No will suffice!
Herc
Sander Bruggink
> "Daryl McCullough" <da...@atc-nycorp.com> wrote in message
> news:cb9al...@drn.newsguy.com...
>>the context of a computer program, what is the difference between
>>the "form" of a program and the "syntax" of a program?
>
> The Semantics of the program. Well formed syntax can still
> leave incorrect semantics.
In the context of formal (or even informal *languages*), form and syntax
refer to the same thing. You can of course redefine every word you'd
like, but if you want people to understand you, you should do that with
care.
Also, there are reasons most people (everyone except you) separate
syntax and semantics, and do not confuse the two in one notion. First,
while syntactic correctness is easily checked (every compiler does it),
semantical correctness is not.
Secondly, *every* syntactically correct program has a meaning. Whether
or not it is semantically correct, depends not only on the programming
language, but also on what the program is supposed to do. If I want a
function which returns its input + 10, then the program:
int a(int x) {
return x + 10;
}
is semantically correct, whereas
int b(int x) {
return x + 5;
}
is not. However, if I want a function which returns its input + 5, then
the b is semantically correct, and a is not. Now, if I want a function
to loop forever, then
int loop_forever() {
while (true);
}
is semantically correct, since it does exactly what it's supposed to do.
groente
-- Sander
Sander Bruggink
> Ah, but the counter-example program is not computable.
> You are asking a Yes / No question, and the answer lies
> outside this set.
The notion of computability applies to questions (or problems) only,
*not* to programs.
> You can ask the question can there possibly exist any program
> or function that can correctly determine whether any other
> program will halt that answer is a flat "no".
Yes.
> When you ask WHY this is so, it is because there can possibly
> be formed a program where the answer to the question:
> "Does this Program halt?" has no correct (yes or no) answer,
> yet you have already limited the possible answers to (yes or no)
> so it is your limitation of this question's answer to (yes or no)
> that creates the impossible (thus incorrectly formed) question.
So you disagree with the fact that a program either halts on some input,
or not. May I ask what the third possibility is, then?
groente
-- Sander
Sander Bruggink
What is the WillHalt function? It cannot be the halting function, since
it does not exist, so what is it?
groente
-- Sander
Peter Olcott
"Sander Bruggink" <bruggink.at...@no.spam.please> wrote in message
news:cbbfpd$6nc$1...@husserl.admin.phil.uu.nl...
> Peter Olcott wrote:
> > "Daryl McCullough" <da...@atc-nycorp.com> wrote in message
> > news:cb9al...@drn.newsguy.com...
> >>Think about the context of this discussion, Peter. In
> >>the context of a computer program, what is the difference between
> >>the "form" of a program and the "syntax" of a program?
> >
> > The Semantics of the program. Well formed syntax can still
> > leave incorrect semantics.
>
> In the context of formal (or even informal *languages*), form and syntax
> refer to the same thing. You can of course redefine every word you'd
> like, but if you want people to understand you, you should do that with
> care.
>
> Also, there are reasons most people (everyone except you) separate
> syntax and semantics, and do not confuse the two in one notion. First,
> while syntactic correctness is easily checked (every compiler does it),
> semantical correctness is not.
That's the same way that I divide it.
When I was discussing the {Liar Paradox} these two were not so
easily divided. The problem was that the error of the {Liar Paradox}
lacked as object of reference. An object is a syntactic construct,
yet the fact that the object of reference was missing could only
be discerned by knowing the underlying semantic meaning of the
sentence.
Peter Olcott
>
> Herc
>
That's what I am saying.
Feeding the counter-example program to the Halt() function as
a parameter is just like feeding negative one to a SquareRoot()
function.
Peter Olcott
> >
> > always has an answer. It's just that there is no *program*
> > that can always give the correct answer.
function LoopIfHalts (M, w):
if WillHalt (M, w) then
while true do {}
else
return false;
If it ALWAYS has a correct answer, then you be the
Halt() function and give me the CORRECT ANSWER
for the above program. Does the above program Halt?
Peter Olcott
"Chris Menzel" <cme...@remove-this.tamu.edu> wrote in message
news:slrncdi1sh...@philebus.tamu.edu...
> On Tue, 22 Jun 2004 23:23:34 GMT, Peter Olcott <olc...@worldnet.att.net>
said:
> > > Hm, so you think a TM has something to do with physical
implementations.
> > > I'd say failing to "get" that detail would be a virtue.
> >
> > A TM is a specific definition of a particular physical
> > implementation.
>
> Not by any definition anywhere. No wonder your claims about
> computability and the Halting problem are so confused: You don't even
> know what Turing machine is.
Check with other people on this, you are failing to comprehend a
very basic point.
Peter Olcott
"Sander Bruggink" <bruggink.at...@no.spam.please> wrote in message
You be the Halt() function and tell me whether the above
program would Halt. (or if the question is impossible for
anyone to answer).
Peter Olcott
indeed
> give you an effective procedure for telling if it will halt.
I already told you, you are the Halt() function, can't you meet the
challenge?
>
> >It is an answerable question isn't it?
>
> If you bother to actually fully specify a program, it is. My assertion is
> about programs, not about partial programs plus whatever other weirdness
> you're trying to throw into the mix.
>
> >That's what all my detractors have been so adamantly claiming,
> >after all every Turing Machine either halts or fails to halt.
>
> So you agree with that now? If so, good.
Of course not. No one and nothing can possibly tell if the above
program halts because asking if the above program halts is an
incorrect question. Unless and until you can tell me whether or
not the above program halts, I have already proven my point
completely, and you are just making excuses for not accepting this
proof.
Peter Olcott
indeed
> > give you an effective procedure for telling if it will halt.
>
>
> just a Yes or No will suffice!
>
> Herc
>
answer.
Sander Bruggink
>>>function LoopIfHalts (M, w):
>>> if WillHalt (M, w) then
>>> while true do {}
>>> else
>>> return false;
>>>
>>>Okay then you tell me the answer
>>>Does the above program halt?
>>
>>What is the WillHalt function? It cannot be the halting function, since
>>it does not exist, so what is it?
>
> You be the Halt() function and tell me whether the above
> program would Halt.
I exist. The halting function doesn't. So I cannot be the halting function.
> (or if the question is impossible for
> anyone to answer).
Ok then, I have to guess on the definition of WillHalt then. Let's
presume it is defined as follows:
function WillHalt(M,w):
return false;
Now, yes, your program always halts.
Btw, you miss the difference between a question having an answer (in
principle) and someone being able to answer it.
For example, I do not know the answer to the question "Will the
Netherlands reach the quarter finals of the European Championship?" But
I know that the question does have an answer. We'll see, tonight.
groente
-- Sander
David C. Ullrich
It's remarkable, the way you repeat yourelf without paying
any attention to explanations of why you're wrong. As has
been said _many_ times, the two are not the same at all.
A large difference is that "what is the real square root
of -1" does not _have_ an answer, while for any program
P, "does P halt" _does_ have a correct answer, either yes
or no.
************************
David C. Ullrich
David C. Ullrich
<olc...@worldnet.att.net> wrote:
>> Hm, so you think a TM has something to do with physical implementations.
>> I'd say failing to "get" that detail would be a virtue.
>
>A TM is a specific definition of a particular physical implementation.
>
Huh?
>
>I know what a TM is, I have a copy of "An Introduction to Formal
>Languages and Automata" by Peter Lentz. Why don't you demonstrate
>some knowledge that can not merely be copied verbatim from a book,
>or otherwise tell us what your credentials are?
Why don't _you_ read the book, and then tell us whether its
definition of TM is "specific definition of a particular physical
implementation"?
************************
David C. Ullrich
David C. Ullrich
Uh, right. That's what it says in that book you have, right?
You should really answer the other question he asked:
"BTW, this would be the book by Peter Lentz in which he purports
to demonstrates that the Halting Problem is undecidable? Why do
you trust anything in a book you think contains egregious errors?"
************************
David C. Ullrich
|-|erc
easy, it hasn't halted yet!
Herc
David C. Ullrich
<olc...@worldnet.att.net> wrote:
>> >Until you analyze why this answer is No.
>> >Basically what I am saying is that the Halt() function can work
>> >correctly on every correctly-formed TM, and thus any TM that
>> >the Halt() function can not work correctly on, is thus not correctly
>> >formed.
>> >
>>
>> What do you mean by a correctly-formed TM?
>>
>One that is free from errors in its defined task is the most
>basic definition. In the case of the Halting Problem the
>definition must be much more precise. Most any program
>that has a non-functional infinite loop would be incorrectly
>formed. (Note MS Windows programs have functional
>infinite loops, waiting for the user input).
You're confusing syntax and semantics. The fact that
you deny doing so is irrelevant - that's what you're
doing. You say a program is "correctly formed" if it
does what it's supposed to do - that is _not_ a
syntactic notion. (If it were a syntactic notion
then one could determine whether a program was
correctly formed just by looking at the program.
But your notion of "correctly formed" depends on
what the author _intended_ for it to do! In fact
according to you:
Suppose that Jack wants to write a program that
prints the number 2. He writes this:
print sqrt(4)
Now Jill wants to write a program that prints
the number 0. She writes this:
print sqrt(4)
By your definition Jack's program is "correctly
formed" while Jill's program is not correctly
formed, even though they're exactly the same
program. _Hence_ your "correctly formed" is
not a purely syntactic notion.
(And hence your notion of "correctly formed"
is in fact not something that we can give a
precise mathematical definition of in any case,
because it depends on knowing the intent of
the author... Also even if we could read minds
there would be no algorithmic way to determine
whether a program was correctly formed.)
************************
David C. Ullrich
David C. Ullrich
wrote:
>> No, it's nothing like that. "What real number squared is
>> equal to -1?" has no answer. But "Does program P halt on
>> input q?" does have an answer.
>
>function LoopIfHalts (M, w):
> if WillHalt (M, w) then
> while true do {}
> else
> return false;
>
>Okay then you tell me the answer
>Does the above program halt?
Any _actual_ program halts or not. The
program above does not actually exist
(because there is no WillHalt function).
You really need to read that proof much more
carefully. Note the part where it says that
we're _assuming_ that there exists a WillHalt
function. Find a book on logic and learn what
it means to _assume_ something in a proof by
contradiction.
************************
David C. Ullrich
|-|erc
a minor issue, the analogy still holds. the correct answers are either
"in the domain & halts" or "in the domain & not halts".
the examples outside of the domain, such as infinite loop programs,
do not_have_an answer to the question,
Which of "in the domain & halts" or "in the domain & not halts" is true?
Its no different to making a consistency clause in a set of formula, we discard
paradoxical formula that self reference like t = ~t.
Herc
David C. Ullrich
<olc...@worldnet.att.net> wrote:
>> >function LoopIfHalts (M, w):
>> > if WillHalt (M, w) then
>> > while true do {}
>> > else
>> > return false;
>> >
>> >Okay then you tell me does the above program halt?
>>
>> Be glad to, but first you need to give me the WHOLE program. In
>particular,
>> you need to show me the code for the function named "WillHalt" in the
>program.
>> Clearly, the behaviour of LoopIfHalts depends on the behaviour of the
>> so-called WillHalt.
>
>You are the function WillHalt() what is your answer (Yes or No)
>will this program halt?
Jesus, you're making a fool of yourself here. You ask a question
about a certain program. She points out that she can't answer
the question because you haven't given her the whole program,
and your reply is that _she_ is the part of the program that
you left out? She's not a function.
>You are far superior to any mere Turing
>Machine, aren't you? Certainly you can answer whether this program
>will halt, can't you?
>
>It is an answerable question isn't it?
You haven't asked any question at all yet, until you give
the entire code for the program. At that point the question
_does_ have an answer. It does not follow that the question
is "answerable".
>That's what all my detractors have been so adamantly claiming,
No, people have just been claiming that the question has an
answer. There's a big difference.
>after all every Turing Machine either halts or fails to halt.
>
************************
David C. Ullrich
|-|erc
> wrote:
>
> >> No, it's nothing like that. "What real number squared is
> >> equal to -1?" has no answer. But "Does program P halt on
> >> input q?" does have an answer.
> >
> >function LoopIfHalts (M, w):
> > if WillHalt (M, w) then
> > while true do {}
> > else
> > return false;
> >
> >Okay then you tell me the answer
> >Does the above program halt?
>
> Any _actual_ program halts or not. The
> program above does not actually exist
> (because there is no WillHalt function).
it exists in this thread until you find a contradiction. you can use
an oracle function if you like.
>
> You really need to read that proof much more
> carefully. Note the part where it says that
> we're _assuming_ that there exists a WillHalt
> function. Find a book on logic and learn what
> it means to _assume_ something in a proof by
> contradiction.
well you can't seem to assume very far.
Step 1 assume halt() exists
Step 2 does program q halt?
Step 3 no, because halt() doesn't exist.
TRY AGAIN, YES OR NO
> >function LoopIfHalts (M, w):
> > if WillHalt (M, w) then
> > while true do {}
> > else
> > return false;
Herc
Daryl McCullough
It halts if WillHalt(M,w) returns "false", and doesn't
halt otherwise. So the answer depends on what the function
WillHalt does.
--
Daryl McCullough
Ithaca, NY
Martin Shobe
<olc...@worldnet.att.net> wrote:
>> >Until you analyze why this answer is No.
>> >Basically what I am saying is that the Halt() function can work
>> >correctly on every correctly-formed TM, and thus any TM that
>> >the Halt() function can not work correctly on, is thus not correctly
>> >formed.
>> >
>>
>> What do you mean by a correctly-formed TM?
>>
>One that is free from errors in its defined task is the most
>basic definition.
Would "loop forever doing nothing" be a defined task?
What about "loop forever if and only if the first argument is a
program that halts when given the second argument as input"?
Peter Olcott
indeed
> > give you an effective procedure for telling if it will halt.
>
>
> just a Yes or No will suffice!
>
> Herc
>
Peter Olcott
"David C. Ullrich" <ull...@math.okstate.edu> wrote in message
news:89oid0h56e3fn5gij...@4ax.com...
> On Wed, 23 Jun 2004 10:09:25 GMT, "Peter Olcott"
> <olc...@worldnet.att.net> wrote:
>
> > > q <=> -1 ?
> >>
> >> Herc
> >>
> >
> >That's what I am saying.
> >Feeding the counter-example program to the Halt() function as
> >a parameter is just like feeding negative one to a SquareRoot()
> >function.
>
> It's remarkable, the way you repeat yourelf without paying
> any attention to explanations of why you're wrong.
It's remarkable that you keep reading what I am saying
and continue to fail to comprehend it.
> As has
> been said _many_ times, the two are not the same at all.
> A large difference is that "what is the real square root
> of -1" does not _have_ an answer, while for any program
> P, "does P halt" _does_ have a correct answer, either yes
> or no.
function LoopIfHalts (M, w):
if WillHalt (M, w) then
while true do {}
else
return false;
Then you can take the place of the Halt() function and tell
me whether or not this program halts, (Yes or No)?
Peter Olcott
So what you are saying is that if you are taking the place
of the WillHalt() function, and say that this program Halts,
then it DOES NOT HALT, and if you say that it doesn't
Halt, THEN IT HALTS. But wait a minute, this is not
a correct answer, this is the opposite of the correct
answer, try again.
Aatu Koskensilta
> function LoopIfHalts (M, w):
> if WillHalt (M, w) then
> while true do {}
> else
> return false;
>
> Then [Ullrich] can take the place of the Halt() function and tell
> me whether or not this program halts, (Yes or No)?
Ullrich can't answer the question correctly if you specify that
WillHalt(x,y) = Ullrich's answer. If he answers "Yes" then the correct
answer is "No" and vice versa. That does not mean that there is no
correct answer, only that Ullrich can't give it. We, on the other hand,
can immediatedly solve the question after Ullrich has given his answer.
Too bad for Ullrich, but nothing paradoxical.
Similarly for every program H(x,y) we can find a program E, s.t. H(E,E)
does not correctly answer the question of whether E(E) halts. This
doesn't mean that an answer does not exist, only that H does not provide
it. Given any specific H it's trivial to answer the question of whether
the program constructed in the proof of the unsolvability of the halting
problem halts when given its code as argument. We can even construct a
new machine H' that will correctly answer the question of whether E
halts when given its own code as argument. Of course, for H' there
exists an E' the halting of which H' does not correctly decide and so forth.
--
Aatu Koskensilta (aatu.kos...@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
David C. Ullrich
<olc...@worldnet.att.net> wrote:
This is not a program until you show us the code for
the Halt function. Once you do that it's true that
the program either halts or does not halt. It does
not follow from that that I can _determine_ whether
it halts or not.
This business about how various people should take the
place of the Halt function is really even stupider than
most of the things you've been saying. The subject is
computer programs - what would happen if I were to
take the place of the Halt function, whatever that
means, has no relevance.
>(Yes or No)?
>
************************
David C. Ullrich
David C. Ullrich
There's more than one question here. What you just
said _is_ the correct answer to the question of what
LoopHalts() does. It follows from that that WillHalt
is not giving correct answers about whether or not
an arbitrary program halts. That's the point: no
matter what function we use for WillHalt it doesn't
work right. The halting problem is not solvable.
Duh.
************************
David C. Ullrich
Daryl McCullough
>> >function LoopIfHalts (M, w):
>> > if WillHalt (M, w) then
>> > while true do {}
>> > else
>> > return false;
>So what you are saying is that if you are taking the place
>of the WillHalt() function, and say that this program Halts,
What program? WillHalt(M,w) takes two arguments, M and w.
What value for M and what value for w are you talking about?
>then it DOES NOT HALT, and if you say that it doesn't
>Halt,
What is "it"? Are you asking whether LoopIfHalts halts?
On what input? (It has two input parameters, M and w).
I think you have screwed up your own counterexample,
which shows once again that you post articles without
spending the least effort to make sure you know what
you are talking about.
I assume that what you meant was a completely different
program:
LoopIfHalts(M) :
if WillHalt (M, M) then
while true do {}
else
return false;
Then what you mean to ask is "Does LoopIfHalts halt
when given its own program as input?"
So, you are asking:
Put yourself in the place of WillHalt() trying
to determine whether LoopIfHalts halts when given
its own program as input.
That question really *is* is ill-defined. WillHalt is
a *program*, not a human being. If you substitute a
human being for WillHalt, then the resulting "program"
LoopIfHalts, is no longer a program, either:
LoopIfHalts(M) :
If Daryl says that M halts on input M, then loop forever,
Otherwise halt
That isn't a program, because a program can't branch based on
an arbitrary sentence, it can only branched based on a boolean-valued
expression in the programming language, and "Daryl says that M
halts on input M" isn't a program statement. So it just isn't
clear what the heck you are asking.
Daryl McCullough
>
>> >function LoopIfHalts (M, w):
>> > if WillHalt (M, w) then
>> > while true do {}
>> > else
>> > return false;
>You are the function WillHalt() what is your answer (Yes or No)
>will this program halt? You are far superior to any mere Turing
>Machine, aren't you? Certainly you can answer whether this program
>will halt, can't you?
>
>It is an answerable question isn't it?
>That's what all my detractors have been so adamantly claiming,
>after all every Turing Machine either halts or fails to halt.
It is amazing how many errors you can pack into a single short
post.
1. For one thing, your example is complete gibberish. WillHalt
as you are using it takes two arguments M and w. Similarly,
LoopIfHalts is a function of two arguments. When you ask
"...what is your answer (Yes or No) will this program halt?"
you haven't said on what inputs. LoopIfHalts halts on some
inputs, and fails to halt on other inputs. What value of M
and w are you talking about? You complain about perfectly
meaningful questions being "ill-formed", and then you ask
a question that really *is* complete nonsense.
What I assume you meant was the program that is supposed
to be a counter-example for WillHalt. That counter-example
isn't your LoopIfHalts, instead it is (as has been told
to you many times---the fact that you screwed it up means
that you are paying no attention to the posts you are responding
to)
Q(x): If WillHalt(x,x) then loop forever, otherwise halt.
Then the question that WillHalt gives the wrong answer (wrong
in the sense of the intended meaning of WillHalt) to is:
"Does Q when given its own program as input?"
2. You say "You are the function WillHalt()". That makes
no sense. A human being isn't a computer program. If I were
the function WillHalt, then what I did would depend on how
WillHalt was programmed. I would do whatever I was programmed
to do. Since you haven't specified the program for WillHalt,
then how could I tell you what I would do?
3. You say "You are far superior to any mere Turing
Machine, aren't you?". Who said that human beings are "far
superior to any mere Turing Machine?" Nobody said that
humans can always determine whether a program halts or not.
4. You say "It is an answerable question isn't it?
That's what all my detractors have been so adamantly claiming,
after all every Turing Machine either halts or fails to halt."
You are confused. Nobody said that the question "Does P halt on
input q?" is *answerable*. They only said that it *has* an answer,
not that we always know what that answer is.
Daryl McCullough
>
>"Daryl McCullough" <da...@atc-nycorp.com> wrote
>> You can certainly define a *limited* halt function. There
>> are certainly restricted sets of programs D such that there
>> is a halt function H_D that works on programs in set D. But
>> any such domain D must *either* be undecidable (there is
>> no way to know whether a program is in D or not), or must
>> be incomplete (there are some computable functions that
>> are not included in D).
>>
>> To see this, assume that D is some decidable domain of
>> programs, which means that there is a program Valid_D(x)
>> which returns true if x is a program in D, and returns
>> false otherwise. Assume that there is a program H_D(x,y)
>> that solves the halting problem for domain D. That means
>> that
>>
>> H_D(x,y) = true if x is a program in D
>> and x halts on input y
>> = false if x is a program in D
>> and x does not halt on input y
>>
>> Then define a new function that takes strings as inputs and
>> returns booleans as follows:
>>
>> f(x) =
>> if Valid_D(x) and H_D(x,x) and the return type of program x
>> is boolean, then return the negation of the result of running
>> x on input x,
>> otherwise, return false.
>>
>> It's clear that if Valid_D is computable, and H_D is computable, then
>> f is computable. But it is also clear that f(x) cannot be a program in
>> domain D.
>>
>
>Right!
>
>But whether it fits in scope of this :
>
> there are some computable functions that are not included in D
>
>since f is an 'ill defined' program
But that's not true. f is a perfectly well-defined program.
It is computable. It always halts. It always returns an answer,
either "true" or "false". What's ill-defined about it?
Daryl McCullough
>>> Peter Olcott says...
>>> >function LoopIfHalts (M, w):
>>> > if WillHalt (M, w) then
>>> > while true do {}
>>> > else
>>> > return false;
>There's more than one question here. What you just
>said _is_ the correct answer to the question of what
>LoopHalts() does. It follows from that that WillHalt
>is not giving correct answers about whether or not
>an arbitrary program halts.
Actually, Peter screwed up the counterexample. If you
are asking "Does LoopIfHalts halt?" you need to specify
the inputs. It has two input parameters, M and w. What
is Peter wanting M and w to be? Presumably, he wants
M to be the code for LoopIfHalts. But then what's w?
I think what he meant to write was something more like:
function LoopIfHalts(M):
if WillHalt (M, M) then
while true do {}
else
return false;
Then he would like to ask "Does LoopIfHalts halt when
given (the code for) LoopIfHalts as an input?"
Chris Menzel
>
> "Chris Menzel" <cme...@remove-this.tamu.edu> wrote in message
> news:slrncdi1sh...@philebus.tamu.edu...
> > On Tue, 22 Jun 2004 23:23:34 GMT, Peter Olcott <olc...@worldnet.att.net>
> said:
> > > > Hm, so you think a TM has something to do with physical implementations.
> > > > I'd say failing to "get" that detail would be a virtue.
> > >
> > > A TM is a specific definition of a particular physical
> > > implementation.
> >
> > Not by any definition anywhere. No wonder your claims about
> > computability and the Halting problem are so confused: You don't even
> > know what Turing machine is.
>
> Check with other people on this, you are failing to comprehend a
> very basic point.
There seems to be an echo in here. Listen, once again, you're the one
contradicting basic results in an exceedingly well understood area of
theoretical computer science. Those results depend on clear definitions
of a number of fundamental concepts. If you wish your arguments to be
convincing, you have to show how they follow from true propositions that
actually involve those concepts rather than something vague and fuzzy
(such as your "definition" of a TM above) manufactured out of your own
intellect. So put up or shut up: State your definition of a Turing
machine.
I expect you'll decide actually to consult that text you own but have
obviously not studied (the one in which the undecidability of the
Halting Problem is allegedly proved) to learn the correct answer.
That's great! Doing so might might actually enable you to understand
the dozens of refutations of your arguments that have been posted here.
(See, we *are* a solicitous bunch.)
-cm
Eray Ozkural exa
> Below is the link from which I am basing my discussion.
> http://www.netaxs.com/people/nerp/automata/halting2.html
>
> Because of all of the dialogue of the other threads on this
> subject I am able to state my position much more clearly.
> Below is the best example yet of the proof of my point.
>
> PREMISES:
> (1) The Halting Problem was specified in such a way that a solution
> was defined to be impossible.
No, it wasn't. It's a perfectly legitimate mathematical problem. It's
not even obvious that it wouldn't have an effective solution at first
sight.
Regards,
--
Eray
Peter Olcott
> >> > implementation.
> >>
> >> Not by any definition anywhere. No wonder your claims about
> >> computability and the Halting problem are so confused: You don't even
> >> know what Turing machine is.
> >
> >Check with other people on this, you are failing to comprehend a
> >very basic point.
>
> Uh, right. That's what it says in that book you have, right?
>
> You should really answer the other question he asked:
So do you comprehend that a TM defines a specific physical
implementation?
(Or are you yet another semi-pseudo intellectual?)
Peter Olcott
> definition of TM is "specific definition of a particular physical
> implementation"?
>
>
>
> ************************
>
> David C. Ullrich
I don't learn things by rote like you guys. Instead I fully comprehend
the meanings behind the meanings.
Peter Olcott
> prints the number 2. He writes this:
>
> print sqrt(4)
>
> Now Jill wants to write a program that prints
> the number 0. She writes this:
>
> print sqrt(4)
>
> By your definition Jack's program is "correctly
> formed" while Jill's program is not correctly
> formed, even though they're exactly the same
> program. _Hence_ your "correctly formed" is
> not a purely syntactic notion.
When I use terminology it is only the generic "common"
definitions that I imply. When I use a word like "form", it
is the meaning that applies equally to making things of
clay, as it does to computer programs. I am not referring
to the syntax. FORM, putting something together from
parts.
Peter Olcott
> >>
> >One that is free from errors in its defined task is the most
> >basic definition.
>
> Would "loop forever doing nothing" be a defined task?
>
> What about "loop forever if and only if the first argument is a
> program that halts when given the second argument as input"?
No, both of these would be incorrect programs.
Peter Olcott
"Aatu Koskensilta" <aatu.kos...@xortec.fi> wrote in message
news:mcfCc.2619$je2...@reader1.news.jippii.net...
> Peter Olcott wrote:
>
> > function LoopIfHalts (M, w):
> > if WillHalt (M, w) then
> > while true do {}
> > else
> > return false;
> >
> > Then [Ullrich] can take the place of the Halt() function and tell
> > me whether or not this program halts, (Yes or No)?
>
> Ullrich can't answer the question correctly if you specify that
> WillHalt(x,y) = Ullrich's answer. If he answers "Yes" then the correct
> answer is "No" and vice versa. That does not mean that there is no
> correct answer, only that Ullrich can't give it.
Yeah, Right! Just like there is a correct answer to the last digit of PI,
except that no one anywhere, on the Earth or in Heaven above, can
give this correct answer.
Peter Olcott
> > if WillHalt (M, w) then
> > while true do {}
> > else
> > return false;
> >
> >Then you can take the place of the Halt() function and tell
> >me whether or not this program halts,
>
> This is not a program until you show us the code for
> the Halt function.
Sorry WRONG ANSWER the correct answer must be one
of Yes or No (you are the proxy for the WillHalt() function)
Peter Olcott
> Peter Olcott says...
>
> >> >function LoopIfHalts (M, w):
> >> > if WillHalt (M, w) then
> >> > while true do {}
> >> > else
> >> > return false;
>
> >So what you are saying is that if you are taking the place
> >of the WillHalt() function, and say that this program Halts,
>
> What program? WillHalt(M,w) takes two arguments, M and w.
> What value for M and what value for w are you talking about?
Sorry WRONG ANSWER the correct answer must be one
of Yes or No.
function LoopIfDarylSaysItHalts(bool DarylSaysItHalts):
if DarylSaysItHalts then
while true do {}
else
return false;
So Daryl does it Halt YES or NO?
Any answer besides yes and no is an incorrect answer.
Failure to answer is failure to provide the correct answer.
It has been repeated claimed over and over again that
every program either halts or does not halt, so does it
halt or not halt??? (or were these claims wrong)
|-|erc
> place of the Halt function is really even stupider than
> most of the things you've been saying. The subject is
> computer programs - what would happen if I were to
> take the place of the Halt function, whatever that
> means, has no relevance.
no you are being quite stupid here as part of your evasion. Assigning *some*
existence to the functionality of Halt() function is EXACTLY what Turing did.
All you have to do to answer Peters question is this :
If the function halts, then WillHalt(w, w) equalled 0
If the function doesn't halt, then WillHalt(w,w) = 1
.... contradiction. Turing figured this out, you on the other
hand attack the very same idea of a hypothetical Halt program
posed in an analogous question. The more I read sci.mathematicians
the more I see parrot memory that only works in classic text fields.
Herc
Peter Olcott
> said _is_ the correct answer to the question of what
> LoopHalts() does. It follows from that that WillHalt
> is not giving correct answers about whether or not
> an arbitrary program halts. That's the point: no
No matter who is taking on the role of WillHalt()
the correct answer can not possibly be provided.
> matter what function we use for WillHalt it doesn't
> work right. The halting problem is not solvable.
Only in the same sense as providing the last digit of PI
is not solvable. The Halting Problem is merely an
IMPOSSIBLE QUESTION, and nothing more.
Peter Olcott
I just copied the original, allowing the reader to make
any slight adjustments that may be required.
> are asking "Does LoopIfHalts halt?" you need to specify
> the inputs. It has two input parameters, M and w. What
> is Peter wanting M and w to be? Presumably, he wants
> M to be the code for LoopIfHalts. But then what's w?
>
> I think what he meant to write was something more like:
>
> function LoopIfHalts(M):
> if WillHalt (M, M) then
> while true do {}
> else
> return false;
function LoopIfHalts(bool YouSayItHalts):
if YouSayItHalts then
while true do {}
else
return false;
Is this simple enough for you?
What is the answer YES or NO
Does it Halt?
NOTE (YES or NO) are the only correct answers,
and either of these is fed to the function as a bool.
|-|erc
This is a VALID argument, address the argument its not use quoting the
proof again and again.
Imagine the Halting proof used the GOTO command. An irrefutable
"exceptionally well understood" area of hard computer science, undeniable
theoretical proven theory. Then Dijkstra comes along and says...
we don't need the GOTO command, we can program everything just as
well without a lot of programming faults if we skip it altogether. What
would that do to the Halting proof? Assume the halting proof relied on
the GOTO command to form the contradiction!
Now switch GOTO with INFINITE LOOP, and see the argument.
Herc
Peter Olcott
One other person already agreed with me on this point, and
thought is so obvious that they could not see where the other
person disagreed, even after reading their disagreement.
Are you familiar with the concept of hierarchies of virtual
machines? (If not, then you have no basis to disagree on
this point).