The Halting Problem is based on an ill-formed question (2012-03-09)

[Peter Olcott]

M( String Input )
{
if ( H( Input, Input ) )
Loop Forever;
else
Exit;
}

H specifies an infinite set of Turing Machines included within template M
h is one element of set H
m represents template M that has been instantiated using h

Neither element from the set of {true, false} provides a correct return
value to the invocation of every element referred to by h(m,m).

An ill-formed question is defined as:
(a) Any question that lacks a correct answer from the set of all
possible answers.

(b) Any invocation of a machine that lacks a correct return value from
the set of all possible return values.

Since the invocation of h(m,m) lacks a correct return value from the set
of {true,false} the invocation of h on input data m derives an
ill-formed question.

Another example of an ill-formed question is:
What is the smallest negative integer (the answer must be numeric)
greater than five ?

[Daryl McCullough]

Peter Olcott wrote:
> M( String Input )
> {
> if ( H( Input, Input ) )
> Loop Forever;
> else
> Exit;
> }
>
> H specifies an infinite set of Turing Machines included within template M
> h is one element of set H
> m represents template M that has been instantiated using h
>
> Neither element from the set of {true, false} provides a correct return
> value to the invocation of every element referred to by h(m,m).

What is h?

> An ill-formed question is defined as:
> (a) Any question that lacks a correct answer from the set of all
> possible answers.

What question are you talking about?

> (b) Any invocation of a machine that lacks a correct return value from
> the set of all possible return values.

That doesn't make any sense. Programs don't "answer questions", they
compute outputs from inputs.

> Since the invocation of h(m,m) lacks a correct return value from the set
> of {true,false} the invocation of h on input data m derives an
> ill-formed question.

In the case of the halting problem, the question at hand is:
Does the program number m halt on input m? It's a perfectly
good question, for absolutely any m whatsoever.

What you seem to be saying is that it's inappropriate to ask
that question to machine h, since you know (by construction)
that h is going to give the wrong answer. That doesn't make
the *question* ill-formed, it just makes h an inappropriate
program for computing the answer.

What you are saying makes no more sense than if I have
a program f(x) defined by:

if x > 0, return true
otherwise return false

and then I use f(6) to answer the question "Is 6 a prime
number?" f is not going to give the correct answer to
that question. But that doesn't mean that the question
is ill-formed--it means that f is not the correct program
for answering it.

Anyway, what you're doing is just making a simple claim
more complicated than it needs to be. Fine, you want to
say that for certain programs h(x,y), and for certain
values of m, it is an "ill-formed question" to ask h
whether m halts on input m.

Then we can reformulate the issue for the halting problem
as follows: For every program h(x,y), Let Q(h) be
the collection of questions that are well-formed for h,
and let QH be the collection of questions of the form
"Does program number m halt on input m?"

Then the claim of the unsolvability of the halting problem
is that there is no h such that Q(h) contains all of QH.

> Another example of an ill-formed question is: What is the
> smallest negative integer (the answer must be numeric)
> greater than five ?

The halting problem is nothing like that.

[Ben Bacarisse]

Do you agree that no "halting questions" are ill-defined in that sense?
I.e. that there is always a true/false answer to the question "does t
halt on input i?"

--
Ben.

[Peter Olcott]

Not at all. There are two semantically different questions here:
(a) Does m halt on input m?
(b) The invocation of h(m,m).

The latter one is ill-formed because there exists no possible correct

return value from the set of all possible return values.

The former one is also ill-formed in this specific case because the
details of the inner workings of h are not provided. If these details
would have been provided, then this question would not be ill-formed.

[Peter Olcott]

On 3/9/2012 9:58 AM, Daryl McCullough wrote:
> Peter Olcott wrote:
>> > M( String Input )
>> > {
>> > if ( H( Input, Input ) )
>> > Loop Forever;
>> > else
>> > Exit;
>> > }
>> >
>> > H specifies an infinite set of Turing Machines included within template M
>> > h is one element of set H
>> > m represents template M that has been instantiated using h
>> >
>> > Neither element from the set of {true, false} provides a correct return
>> > value to the invocation of every element referred to by h(m,m).
> What is h?

I just said that immediately above.

>
>> > An ill-formed question is defined as:
>> > (a) Any question that lacks a correct answer from the set of all
>> > possible answers.
> What question are you talking about?
>
>> > (b) Any invocation of a machine that lacks a correct return value from
>> > the set of all possible return values.
> That doesn't make any sense. Programs don't "answer questions", they
> compute outputs from inputs.

The invocation of a program that provides a return value is analogous to
and therefore equivalent to asking a person a question. This invocation
is the means by which one asks a program a question.

The return value from this program is is analogous to and therefore
equivalent to the program's answer to its invocation. This return value
is the means by the program provides its answer.

>
>> > Since the invocation of h(m,m) lacks a correct return value from the set
>> > of {true,false} the invocation of h on input data m derives an
>> > ill-formed question.
> In the case of the halting problem, the question at hand is:
> Does the program number m halt on input m? It's a perfectly
> good question, for absolutely any m whatsoever.

There are two semantically distinct questions:

(a) Does m halt on input m?
(b) The invocation of h(m,m).

The latter one is ill-formed because there exists no possible correct

[Daryl McCullough]

On Friday, March 9, 2012 12:42:39 PM UTC-5, Peter Olcott wrote:
> On 3/9/2012 9:58 AM, Daryl McCullough wrote:
> > Peter Olcott wrote:
> >> > M( String Input )
> >> > {
> >> > if ( H( Input, Input ) )
> >> > Loop Forever;
> >> > else
> >> > Exit;
> >> > }
> >> >
> >> > H specifies an infinite set of Turing Machines included within template M
> >> > h is one element of set H
> >> > m represents template M that has been instantiated using h
> >> >
> >> > Neither element from the set of {true, false} provides a correct return
> >> > value to the invocation of every element referred to by h(m,m).
> > What is h?
>
> I just said that immediately above.

No, you didn't. You said that h is one element of the set H.
But what set is that? The set of all programs that take two
arguments and return {true, false}?

> The invocation of a program that provides a return value is analogous to
> and therefore equivalent to asking a person a question.

No, it isn't. If I write a program to compute square-roots,
it doesn't make any sense to ask an arbitrary question of it.
It can only answer the questions that it was programmed to answer,
namely ones like "What is the square root of 5?"

In the case of h, what question was it programmed to answer?
You haven't said what h is.

> > In the case of the halting problem, the question at hand is:
> > Does the program number m halt on input m? It's a perfectly
> > good question, for absolutely any m whatsoever.
> There are two semantically distinct questions:
>
> (a) Does m halt on input m?
> (b) The invocation of h(m,m).

The unsolvability of the halting problem is the claim that
there is no program that can correctly answer the question
"Does m halt on input m?" for every value of m.

"The invocation of h(m,m)" is not a question. Note the lack of
a question mark. It's a procedure intended to answer a
question, perhaps.

> The latter one is ill-formed because there exists no possible correct
> return value from the set of all possible return values.

That makes no sense at all. "The invocation of h(m,m)" is not
a question at all, so in particular it makes no sense to call
it an ill-formed question.

The unsolvability of the halting problem is just the claim:
There is no program h(x,y) that, for every pair of inputs x
and y will return true if program number x halts on input y,
and returns false otherwise.

There is nothing ill-formed about this.

[Daryl McCullough]

On Friday, March 9, 2012 12:03:41 PM UTC-5, Peter Olcott wrote:
> On 3/9/2012 10:54 AM, Ben Bacarisse wrote:

> >> Another example of an ill-formed question is:
> >> What is the smallest negative integer (the answer must be numeric)
> >> greater than five ?
> > Do you agree that no "halting questions" are ill-defined in that sense?
> > I.e. that there is always a true/false answer to the question "does t
> > halt on input i?"
>
>
> Not at all. There are two semantically different questions here:
> (a) Does m halt on input m?

That's the only question that is relevant to the unsolvability
of the halting problem.

> (b) The invocation of h(m,m).

That isn't a question at all.

> The latter one is ill-formed because there exists no possible correct
> return value from the set of all possible return values.
>
> The former one is also ill-formed in this specific case because the
> details of the inner workings of h are not provided.

The "former" is the question "Does machine m halt on input m?"
There is no "h" in that question.

[Peter Olcott]

The invocation of a program that provides a return value is analogous to

[Daryl McCullough]

On Friday, March 9, 2012 2:28:41 PM UTC-5, Peter Olcott wrote:

> The invocation of a program that provides a return value is analogous to
> and therefore equivalent to asking a person a question.

No, it's really not. Programs don't answer questions, they compute
functions of their inputs. If the question you want to ask is
"What is the value of this function for this input?" then I guess
you could say that running the program is a way to get your answer.
But it doesn't make any sense to ask an arbitrary question to a
program.

> This invocation is the means by which one asks a program a question.
> The return value from this program is is analogous to and therefore
> equivalent to the program's answer to its invocation. This return value
> is the means by the program provides its answer.

The unsolvability of the halting problem isn't about asking questions
of programs. As I said, the unsolvability of the halting problem is
simply the claim: There is no program h(x,y) that takes two arguments,
x and y, both naturals, and returns "true" if program number x halts on

[Peter Olcott]

A program can not provide the smallest negative integer that is greater
than than five because:
of the possible set of return values {negative integers} no element
provides a correct result.

h(m,m) can not provide the correct return value because:
of the possible set of return values {true, false} no element provides a
correct result.

[Ben Bacarisse]

Hmm... Interesting. Why did you, yet again, not answer the question?

--
Ben.

[Daryl McCullough]

On Friday, March 9, 2012 3:13:06 PM UTC-5, Peter Olcott wrote:

> A program can not provide the smallest negative integer that is greater
> than than five because:
> of the possible set of return values {negative integers} no element
> provides a correct result.

That's true, but has nothing to do with the
unsolvability of the halting problem.

> h(m,m) can not provide the correct return value because:
> of the possible set of return values {true, false} no
> element provides a correct result.

The correct answer to what question?

[Peter Olcott]

Now you are responding to my reply without even looking at the words
that I wrote?

[Peter Olcott]

Now you are refuting things that I did not even say.
Where in my last reply did I use the word: "question" ???

[Daryl McCullough]

What does "correct return value" mean, then? You don't
mean the correct answer to some question, so what do you
mean?

[Daryl McCullough]

I'm assuming that you created the title of this thread, namely
"The Halting Problem is based on an ill-formed question".
Notice the word "question" in that phrase? What question are
you talking about?

[Peter Olcott]

It returns true iff m(m) halts and false iff m(m) fails to halt.

[Peter Olcott]

You had a hard time accepting that the invocation of a machine with a
return value is equivalent to asking a question so I changed the
comparison to be between two machines.

[Daryl McCullough]

On Friday, March 9, 2012 3:47:27 PM UTC-5, Peter Olcott wrote:

> > What does "correct return value" mean, then? You don't
> > mean the correct answer to some question, so what do you
> > mean?
> It returns true iff m(m) halts and false iff m(m) fails to halt.

It's certainly true that h(m,m) doesn't do that. That's why h is
not a solution to the halting problem, since a solution to the
halting problem would be a program h(x,y) that always returns
true if program x halts on input y, and returns false otherwise.
h doesn't do that, so it's not a solution to the halting problem.

But what does that have to do with "ill formed questions"? (To refresh
your memory, "ill formed question" is in the title of this thread.)

[Daryl McCullough]

On Friday, March 9, 2012 4:09:43 PM UTC-5, Peter Olcott wrote:

> You had a hard time accepting that the invocation of a machine with a
> return value is equivalent to asking a question so I changed the
> comparison to be between two machines.

So you are no longer claiming that the unsolvability of the halting
problem has anything to do with "ill formed questions"? Good, since
it doesn't.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/9/2012 2:18 PM, Ben Bacarisse wrote:
>> Peter Olcott<NoS...@OCR4Screen.com> writes:
>>
>>> On 3/9/2012 10:54 AM, Ben Bacarisse wrote:

<snip>

>>>> Do you agree that no "halting questions" are ill-defined in that sense?
>>>> I.e. that there is always a true/false answer to the question "does t
>>>> halt on input i?"
>>>>
>>> Not at all. There are two semantically different questions here:
>>> (a) Does m halt on input m?
>>> (b) The invocation of h(m,m).
>>>
>>> The latter one is ill-formed because there exists no possible correct
>>> return value from the set of all possible return values.
>>>
>>> The former one is also ill-formed in this specific case because the
>>> details of the inner workings of h are not provided. If these details
>>> would have been provided, then this question would not be ill-formed.
>> Hmm... Interesting. Why did you, yet again, not answer the question?
>>
> Now you are responding to my reply without even looking at the words
> that I wrote?

No, I read it carefully. How else would I know that you did not answer
the question? You brought up two other questions and answered those
yourself (nothing wrong with that), but they don't answer the one I was
interested in.

I want to know the answer simply to clarify your position. Much of what
you've written suggests that you want to answer "no" (and you certainly
want to imply that the answer is "no" -- just look at the thread title)
but the fact that won't say either way is, let's say, curious.

So you don't have to copy it from the quoted material, here it is again:
Do you agree that no "halting questions" are ill-formed in your sense of
the term? I.e. that there is always a true/false answer to the question
"does machine t halt on input i?"

--
Ben.

[Peter Olcott]

On 3/9/2012 3:41 PM, Ben Bacarisse wrote:
>>>>> Do you agree that no "halting questions" are ill-defined in that sense?
>>>>> >>>> I.e. that there is always a true/false answer to the question "does t
>>>>> >>>> halt on input i?"
>>>>> >>>>
>>>> >>> Not at all. There are two semantically different questions here:
>>>> >>> (a) Does m halt on input m?
>>>> >>> (b) The invocation of h(m,m).
>>>> >>>
>>>> >>> The latter one is ill-formed because there exists no possible correct
>>>> >>> return value from the set of all possible return values.
>>>> >>>
>>>> >>> The former one is also ill-formed in this specific case because the
>>>> >>> details of the inner workings of h are not provided. If these details
>>>> >>> would have been provided, then this question would not be ill-formed.
>>> >> Hmm... Interesting. Why did you, yet again, not answer the question?
>>> >>
>> > Now you are responding to my reply without even looking at the words
>> > that I wrote?
> No, I read it carefully. How else would I know that you did not answer
> the question?

You:
Do you agree:
Me:
Not at all (see above)

[Peter Olcott]

The entire possible solution set is {true,false} and neither of these
represent a correct return value from h when invoked with m input.

[Peter Olcott]

No I am claiming that you can not see that it has to do with ill-formed
question so I simplified it for you.

[Ben Bacarisse]

Oh, right! A paragraph break would have helped. I thought the whole
thing, with your two new questions, was the answer. It looked like you'd
misinterpreted the question and were answering what you thought was a
re-working of it!

So, what happens in those cases where there is no true/false answer to
the question "does t halt on input i"? Do you have proof of this
startling fact, or is it just a guess at the moment? Maybe you even
have a method to construct a machine that neither halts nor does not
halt on some particular input?

--
Ben.

[Daryl McCullough]

What does "correct return value" mean? Correct is relative to whatever
it was h was supposed to do.

[Daryl McCullough]

Well, in your simplification, it has nothing to do with ill-formed
questions. So what is your

After simplifying it, it has nothing to do with anything being
"ill-formed". You're just repeating the claim of the original
proof of the unsolvability of the halting problem, which is that
whatever h(m,m) outputs, it is not the case that
h(m,m) = true if and only if m halts on input m. So you're
just repeating the proof that h is not a solution to the halting
problem.

[Peter Olcott]

I already told you that a few minutes ago, go back and look it up.

[Peter Olcott]

On 3/9/2012 4:35 PM, Daryl McCullough wrote:
>
> On Friday, March 9, 2012 4:52:37 PM UTC-5, Peter Olcott wrote:
>> > On 3/9/2012 3:12 PM, Daryl McCullough wrote:
>>> > > On Friday, March 9, 2012 4:09:43 PM UTC-5, Peter Olcott wrote:
>>> > >
>>>> > >> You had a hard time accepting that the invocation of a machine with a
>>>> > >> return value is equivalent to asking a question so I changed the
>>>> > >> comparison to be between two machines.
>>> > > So you are no longer claiming that the unsolvability of the halting
>>> > > problem has anything to do with "ill formed questions"? Good, since
>>> > > it doesn't.
>>> > >
>> > No I am claiming that you can not see that it has to do with ill-formed
>> > question so I simplified it for you.
> After simplifying it, it has nothing to do with anything being
> "ill-formed". You're just repeating the claim of the original
> proof of the u

Therefore you can provide a correct negative integer value that is
greater than five, because question does have a correct answer
(according to what you just said above) and the answer is?

[Peter Olcott]

The TM does not halt in either an accept state, nor a reject state, yet
it halts, thus indicating semantically invalid input. I already know
that this is unconventional behavior for a TM , after reading Chapter 29
of Automata and Computability by Kozen. Conventional behavior would
force the TM to get the wrong answer.

I currently see no reason why another Turing Machine could not be
constructed that always consistently detects at least the self-reference
pattern of semantically invalid input. This Turing Machine would then
invoke the other Turing Machine if the input is semantically valid,
otherwise it would halt in its own reject state.

If someone turns this TM's input into the Halting Problem, this machine
simply correctly reports false. I see no way that this TM could be
thwarted from always providing the correct return value.

[Daryl McCullough]

> > After simplifying it, it has nothing to do with anything being
> > "ill-formed". You're just repeating the claim of the original
> > proof of the u
> Therefore you can provide a correct negative integer value that is
> greater than five, because question does have a correct answer
> (according to what you just said above) and the answer is?

Okay, so you're not actually talking about the halting problem,
you're talking about the difficulty of finding a negative integer
that is greater than 5. I agree that that's a hard problem, because
there is no negative integer greater than 5.

But what does that have to do with the halting problem?

[Peter Olcott]

Just like there are no elements from the set {negative integers} that
are greater than five, that a program could provide as a return value,

there are no elements from the set {true, false} that the invocation of
h(m,m) could provide as a return value that correctly indicates whether
or not m(m) will halt.

[Daryl McCullough]

Okay, let me rephrase what I think you might be driving at.

I think that you are confusing two different things:

(1) Having a *question* that is ill-formed, in the sense
that there is no correct answer.

(2) Asking someone (or some thing) to perform a task
such that there is no way to perform the task (subject
to the constraints of the problem).

The halting problem is really *not* an instance of either
one of these. Computer programs are programmed to do something
specific. They are not trying to please you or trying to
carry out your wishes. They do whatever they were programmed
to do, and if that isn't what you wanted, then that's the
programmer's fault, not the program's fault.

But let's change the problem a little, and suppose that instead
of programs, we are talking about people with free will who are
trying to carry whatever tasks were given to them. Then we can
certainly come up with an impossible task for them.

You tell the volunteer that he will be asked a series of yes-no
questions. For each question, he must either say the word "yes"
or the word "no". The volunteer is not allowed any other form
of communication. The volunteer will be given some kind of reward
for answering correctly.

Given this setup, we can ask the volunteer the question:
"Will the next word out of your mouth be 'no'?"

The volunteer simply cannot answer the question correctly,
subject to the rules. That doesn't make the question "ill-formed".
It certainly *has* a correct answer, which we will know as soon
as the volunteer says anything. It's just that the volunteer
can't give the correct answer.

[Peter Olcott]

On 3/9/2012 6:47 PM, Daryl McCullough wrote:
> You tell the volunteer that he will be asked a series of yes-no
> questions. For each question, he must either say the word "yes"
> or the word "no". The volunteer is not allowed any other form
> of communication. The volunteer will be given some kind of reward
> for answering correctly.
>
> Given this setup, we can ask the volunteer the question:
> "Will the next word out of your mouth be 'no'?"
>
> The volunteer simply cannot answer the question correctly,
> subject to the rules. That doesn't make the question "ill-formed".

> It certainly*has* a correct answer, which we will know as soon

> as the volunteer says anything. It's just that the volunteer
> can't give the correct answer.

In this case there are two semantically distinct questions one is
ill-formed and the other is not.
The volunteer can not provide a correct answer from the possible
solution set of {yes,no} because neither of these answers form a correct
answer to the question posed to the volunteer.

Since an ill-formed question is defined as any question that lacks a
correct answer from the possible solution set, and the possible solution
set is {yes, no} and neither of these answers are correct when provided
by the volunteer, this exactly meets the definition of ill-formed
question when applied to the question posed to the volunteer.

The question posed to the volunteer is a distinctly different question
that the same question posed to everyone else.

That was an excellent example.

[Peter Olcott]

On 3/9/2012 6:47 PM, Daryl McCullough wrote:

> You tell the volunteer that he will be asked a series of yes-no
> questions. For each question, he must either say the word "yes"
> or the word "no". The volunteer is not allowed any other form
> of communication. The volunteer will be given some kind of reward
> for answering correctly.
>
> Given this setup, we can ask the volunteer the question:
> "Will the next word out of your mouth be 'no'?"
>
> The volunteer simply cannot answer the question correctly,
> subject to the rules. That doesn't make the question "ill-formed".

> It certainly*has* a correct answer, which we will know as soon

> as the volunteer says anything. It's just that the volunteer
> can't give the correct answer.
>

That may be better than an excellent example, that may be a perfect
example. It does seem much more clear than any of the examples that I
provided, and it is exactly analogous to the Halting Problem.

[Peter Webb]

"Peter Olcott" <NoS...@OCR4Screen.com> wrote in message
news:dO2dnaNHjrQICsfS...@giganews.com...

Firstly, there are plenty of TMs for which we cannot determine if they halt
which do not have any form of self-reference. A self-reference was used by
Turing in his example because it makes the proof work, but plenty of other
TMs have the same problem.

For example, consider the Goldbach conjecture, that very even number greater
than 2 is the the sum of two primes. This is true or false. A TM which just
checked even numbers 4, 6, 8 ... until it found an exception and then halted
will either halt or not halt. See anything ill formed about this question?
Any idea how to build a TM to answer it? Maybe you can (maybe a proof of
Goldbach exists), but you don't know. There are plenty of TMs which we know
must halt, which do not involve any form of self-reference, but for which we
know there is no TM which will correctly determine that they halt on input.

Secondly, you should be able to see a very good "reason why another Turing

Machine could not be constructed that always consistently detects at least

the self-reference pattern of semantically invalid input.". TMs have no
"semantically invalid input" unless you decide to arbitrarily lable some
inputs as invalid, for which you have provided no definition. And they will
still halt or not halt. Secondly, I doubt you can provide a definition or
algorithm of a "self reference pattern", another undefined term. Lastly, fix
this up, and you will be able to see exactly why "another TM" can't perform
this task; Turing proved it was impossible.

>This Turing Machine would then invoke the other Turing Machine if the input
>is semantically valid, otherwise it would halt in its own reject state.
>

This argument is analogous to the the purported disproof of Cantor's
theorem, whereby you find a value missing from one list and create a new
list containing it. This new list will suffer from exactly the same problem,
but with different missing numbers. Same deal here. You are now considering
a different TM, and it will suffer from the same problems as the original
TM, just with different inputs.

> If someone turns this TM's input into the Halting Problem, this machine
> simply correctly reports false. I see no way that this TM could be
> thwarted from always providing the correct return value.

1. Because Turing proved it to be impossible.

2. And nor have you provided any idea of how so a TM could be constructed.

[Peter Olcott]

On 3/9/2012 7:20 PM, Peter Webb wrote:
>> I currently see no reason why another Turing Machine could not be
>> constructed that always consistently detects at least the
>> self-reference pattern of semantically invalid input.
>
> Firstly, there are plenty of TMs for which we cannot determine if they
> halt which do not have any form of self-reference. A self-reference
> was used by Turing in his example because it makes the proof work, but
> plenty of other TMs have the same problem.
>
> For example, consider the Goldbach conjecture, that very even number
> greater than 2 is the the sum of two primes. This is true or false. A
> TM which just checked even numbers 4, 6, 8 ... until it found an
> exception and then halted will either halt or not halt. See anything
> ill formed about this question? Any idea how to build a TM to answer
> it? Maybe you can (maybe a proof of Goldbach exists), but you don't know.

I see now. It would take an infinite amount of time to find that no
exception exists, if no exception exists and we simply tested every
combination until we encountered an exception.

There is a way around it that would take less than an infinite amount of
time. Find the pattern of the reason why it works, and use mathematical
induction to show that this pattern continues to hold true for the set
of even natural Numbers > 2. A genetic algorithm and neural networks
might be employed so that the system can learn this pattern on its own.
Once the pattern is known proving its holds true should be relatively
straight forward.

[Owen Jacobson]

On 2012-03-09 19:28:41 +0000, Peter Olcott said:

> analogous to and therefore equivalent to

I'm surprised that nobody has pointed it out to you yet, but this is
clearly a mistake. There are no widely-used rhetorical frameworks where
analogy implies equivalence, never mind formal-logic frameworks.

-o

[Peter Olcott]

On 3/9/2012 7:20 PM, Peter Webb wrote:

>> If someone turns this TM's input into the Halting Problem, this
>> machine simply correctly reports false. I see no way that this TM
>> could be thwarted from always providing the correct return value.
>
> 1. Because Turing proved it to be impossible.

Turing showed that self-reference makes providing a universal halt
analyzer that works for every input (including semantically invalid
inputs) impossible. He did not show that detected self-reference is
impossible.

This is the one thing that can not be transformed into an instance of
the Halting Problem, because when it detects the otherwise impossible
instance of the Halting Problem, it simply correctly returns false (or
halts in its reject state).

[Daryl McCullough]

On Friday, March 9, 2012 8:13:30 PM UTC-5, Peter Olcott wrote:
> On 3/9/2012 6:47 PM, Daryl McCullough wrote:
> > You tell the volunteer that he will be asked a series of yes-no
> > questions. For each question, he must either say the word "yes"
> > or the word "no". The volunteer is not allowed any other form
> > of communication. The volunteer will be given some kind of reward
> > for answering correctly.
> >
> > Given this setup, we can ask the volunteer the question:
> > "Will the next word out of your mouth be 'no'?"
> >
> > The volunteer simply cannot answer the question correctly,
> > subject to the rules. That doesn't make the question "ill-formed".
> > It certainly*has* a correct answer, which we will know as soon
> > as the volunteer says anything. It's just that the volunteer
> > can't give the correct answer.
>
> In this case there are two semantically distinct questions one is
> ill-formed and the other is not.
> The volunteer can not provide a correct answer from the possible
> solution set of {yes,no} because neither of these answers form a correct
> answer to the question posed to the volunteer.

That doesn't make the question ill-formed. It just means that the
volunteer cannot correctly answer it. A question doesn't become
ill-formed because you tape up the volunteer's mouth.

[Joshua Cranmer]

On 3/9/2012 7:20 PM, Peter Webb wrote:

> Firstly, there are plenty of TMs for which we cannot determine if they
> halt which do not have any form of self-reference. A self-reference was
> used by Turing in his example because it makes the proof work, but
> plenty of other TMs have the same problem.

Considering that Mr. Olcott seems to believe that anything that relies
on self-reference is necessarily erroneous, a simpler way to prove this
is to prove that, if you can solve the Halting problem, you can solve
Kolmogorov complexity, and then show that the latter function is
uncomputable via other means.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

[Daryl McCullough]

That's not true. If m(m) halts, then the correct answer is "true",
otherwise, the correct answer is "false".

[Ben Bacarisse]

Quoting lloks messed up so here's a summary of the old stuff:

Me:

Do you agree that no "halting questions" are ill-defined in that sense?
I.e. that there is always a true/false answer to the question "does t
halt on input i?"

Peter:
Not at all.

Peter Olcott <NoS...@OCR4Screen.com> writes:
<snip>

> On 3/9/2012 4:30 PM, Ben Bacarisse wrote:

<snip>

>> Oh, right! A paragraph break would have helped. I thought the whole
>> thing, with your two new questions, was the answer. It looked like you'd
>> misinterpreted the question and were answering what you thought was a
>> re-working of it!
>>
>> So, what happens in those cases where there is no true/false answer to
>> the question "does t halt on input i"?
> The TM does not halt in either an accept state, nor a reject state,
> yet it halts,

Hang on. In that case it halts, so there is a true/false answer to the
question "does t halt on input i?" (to be specific: "true"). So far, you
are not disagreeing with the statement you claim to disagree with.

> thus indicating semantically invalid input. I already
> know that this is unconventional behavior for a TM , after reading
> Chapter 29 of Automata and Computability by Kozen. Conventional
> behavior would force the TM to get the wrong answer.

It may well not matter (since most models of computation are equivalent)
but if you are going to use a non-standard definition of a Turing
machine, you should give it so we all know what you are talking about.
What is the formal definition of these "unconventional" machines?

> I currently see no reason why another Turing Machine could not be
> constructed that always consistently detects at least the
> self-reference pattern of semantically invalid input.

First, the input is not invalid in the same sense that you've been using
the term up to now (i.e. as making an unanswerable, ill-formed
question). Until you can support your "not at all" remark, it looks as
if you actually agree with the simple statement that every question of
the form "does machine m halt on input i?" has a correct true/false
answer. Until then it is unreasonable to call any input "semantically
invalid".

Second, the self-reference is not a pattern -- it's a behaviour and as
such is subject to Rice's theorem. For every case like m(m) there are
infinitely many others, m(m'), m(m'') and so on, where m, m' and m'' all
behave the same but are different machines.

> This Turing
> Machine would then invoke the other Turing Machine if the input is
> semantically valid, otherwise it would halt in its own reject state.
>
> If someone turns this TM's input into the Halting Problem, this
> machine simply correctly reports false. I see no way that this TM
> could be thwarted from always providing the correct return value.

Then you don't understand the proof of the halting theorem, since it
applies to all Turing machines, and what you describe here is, no matter
how cunning, still a Turing machine.

--
Ben.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/9/2012 7:20 PM, Peter Webb wrote:
>>> If someone turns this TM's input into the Halting Problem, this
>>> machine simply correctly reports false. I see no way that this TM
>>> could be thwarted from always providing the correct return value.
>>
>> 1. Because Turing proved it to be impossible.
>
> Turing showed that self-reference makes providing a universal halt
> analyzer that works for every input (including semantically invalid
> inputs) impossible.

That's a miss-characterisation of the result, because the argument works
just as well if the "special" machine m (the one constructed from h)
does not have, or use, a copy of h. All it needs is a machine that
behaves the same way that h does, and there are infinitely many of
those. This is not just playing with words because...

> He did not show that detected self-reference is
> impossible.

No, but Rice's theorem does. Self-reference (as a static property of
the input) is not the problem. What matters is the behaviour of the
machine encoded in the input, and detecting all the encoding of machines
that behave is the same way as the "obvious" one is not possible.

Needless to say this has been said more than once.

> This is the one thing that can not be transformed into an instance of
> the Halting Problem, because when it detects the otherwise impossible
> instance of the Halting Problem, it simply correctly returns false (or
> halts in its reject state).

--
Ben.

[Peter Olcott]

On 3/9/2012 8:35 PM, Ben Bacarisse wrote:
>> The TM does not halt in either an accept state, nor a reject state,
>> > yet it halts,
> Hang on. In that case it halts, so there is a true/false answer to the
> question "does t halt on input i?" (to be specific: "true"). So far, you
> are not disagreeing with the statement you claim to disagree with.
>
>> > thus indicating semantically invalid input. I already
>> > know that this is unconventional behavior for a TM , after reading
>> > Chapter 29 of Automata and Computability by Kozen. Conventional
>> > behavior would force the TM to get the wrong answer.
> It may well not matter (since most models of computation are equivalent)
> but if you are going to use a non-standard definition of a Turing
> machine, you should give it so we all know what you are talking about.
> What is the formal definition of these "unconventional" machines?
>

I just answered that above. If you are not paying attention it is not
worth my time responding to you.

[Peter Olcott]

You are not paying close enough attention to see what I am saying.

[Ben Bacarisse]

Joshua Cranmer <Pidg...@verizon.invalid> writes:

> On 3/9/2012 7:20 PM, Peter Webb wrote:
>> Firstly, there are plenty of TMs for which we cannot determine if they
>> halt which do not have any form of self-reference. A self-reference was
>> used by Turing in his example because it makes the proof work, but
>> plenty of other TMs have the same problem.
>
> Considering that Mr. Olcott seems to believe that anything that relies
> on self-reference is necessarily erroneous, a simpler way to prove
> this is to prove that, if you can solve the Halting problem, you can
> solve Kolmogorov complexity, and then show that the latter function is
> uncomputable via other means.

But that introduces a whole new field of study. Most people won't be
persuaded by arguments that involve subjects they have not yet met, and
self-taught halting deniers often have a narrow focus.

It might be more fruitful to show a "first principles" proof that the
busy beaver function is not computable since that involves only Turing
machines.

--
Ben.

[Peter Webb]

"Peter Olcott" <NoS...@OCR4Screen.com> wrote in message

news:dICdnfihse9OJcfS...@giganews.com...

> On 3/9/2012 7:20 PM, Peter Webb wrote:
>>> I currently see no reason why another Turing Machine could not be
>>> constructed that always consistently detects at least the self-reference
>>> pattern of semantically invalid input.
>>
>> Firstly, there are plenty of TMs for which we cannot determine if they
>> halt which do not have any form of self-reference. A self-reference was
>> used by Turing in his example because it makes the proof work, but plenty
>> of other TMs have the same problem.
>>
>> For example, consider the Goldbach conjecture, that very even number
>> greater than 2 is the the sum of two primes. This is true or false. A TM
>> which just checked even numbers 4, 6, 8 ... until it found an exception
>> and then halted will either halt or not halt. See anything ill formed
>> about this question? Any idea how to build a TM to answer it? Maybe you
>> can (maybe a proof of Goldbach exists), but you don't know.
> I see now. It would take an infinite amount of time to find that no
> exception exists, if no exception exists and we simply tested every
> combination until we encountered an exception.
>
> There is a way around it that would take less than an infinite amount of
> time. Find the pattern of the reason why it works, and use mathematical
> induction to show that this pattern continues to hold true for the set of
> even natural Numbers > 2.

That is not guaranteed to work. Nobody has ever found a proof of Goldbach's
conjecture using induction. There may not be one. Indeed, there may be no
proof or counter-example at all to Goldbach's conjecture.

> A genetic algorithm and neural networks might be employed so that the
> system can learn this pattern on its own. Once the pattern is known
> proving its holds true should be relatively straight forward.

"Once the pattern is known ....". This assumes there is a pattern to find.
You can't do that.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/9/2012 8:35 PM, Ben Bacarisse wrote:
>>> The TM does not halt in either an accept state, nor a reject state,
>>> > yet it halts,
>> Hang on. In that case it halts, so there is a true/false answer to the
>> question "does t halt on input i?" (to be specific: "true"). So far, you
>> are not disagreeing with the statement you claim to disagree with.

No comment on this? Are you now agreeing?

>>> > thus indicating semantically invalid input. I already
>>> > know that this is unconventional behavior for a TM , after reading
>>> > Chapter 29 of Automata and Computability by Kozen. Conventional
>>> > behavior would force the TM to get the wrong answer.
>> It may well not matter (since most models of computation are equivalent)
>> but if you are going to use a non-standard definition of a Turing
>> machine, you should give it so we all know what you are talking about.
>> What is the formal definition of these "unconventional" machines?
>>
> I just answered that above. If you are not paying attention it is not
> worth my time responding to you.

Then don't respond. It's would for better for everyone if these threads
of yours consisted of a post by you and a some posts by others that
explained why (in the poster's opinion of course) you are wrong. There
would be no need for the endless repetition, and readers could decide
for themselves which position they found most compelling.

--
Ben.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:
<snip>

> You are not paying close enough attention to see what I am saying.

Ah, the lament of brilliant teachers the world over! "I taught them,
but they didn't learn".

--
Ben.

[Owen Jacobson]

On 2012-03-09 14:23:16 +0000, Peter Olcott said:

> M( String Input )
> {
> if ( H( Input, Input ) )
> Loop Forever;
> else
> Exit;
> }
>
> H specifies an infinite set of Turing Machines included within template M
> h is one element of set H
> m represents template M that has been instantiated using h
>
> Neither element from the set of {true, false} provides a correct return
> value to the invocation of every element referred to by h(m,m).
>
> An ill-formed question is defined as:
> (a) Any question that lacks a correct answer from the set of all
> possible answers.
>
> (b) Any invocation of a machine that lacks a correct return value from

> the set of all possible return values.
>

> Since the invocation of h(m,m) lacks a correct return value from the
> set of {true,false} the invocation of h on input data m derives an
> ill-formed question.

Bear with me, here. I'll get to your point about "ill-formed questions"
eventually, but as I've taken the time to read your post, do me the
credit of taking the time to read and consider mine.

1. Let's take as a given that Turing machines[0] exist.

2. It can be shown that Turing machines are composable and that the
composition of a finite number of Turing machines is itself a Turing
machine.

3. It can be shown that any Turing machine can be encoded as a finite
number, and it can be shown that any tape can be encoded as a finite
number.
3a. It can be shown that any finite sequence of finite numbers can be
represented by a Turing machine tape.

4. For every (Turing machine, initial tape) pair, either the machine
eventually halts when started with that initial tape, or it does not
halt. These options are mutually exclusive and exhaustive: there is no
third outcome and the answer can't be "both".

5. It can be shown that there exists a _function_ h(m, t) whose domain
is pairs (m, t) of numbers, where m is a number that encodes a Turing
machine and t is a number that encodes a tape, that is equal to 1 if
the Turing machine whose encoding is m, when run with the initial tape
whose encoding is t, halts, and is equal to 0 otherwise.

6. A Turing machine F is said to compute a function f if and only if
the machine F, when started with a tape containing a representation of
the parameters p0, p1, … pn, halts after a finite number of steps with
a representation of the value of f(p0, p1, … pn) stored on the tape.
(What the machine F does when started with a tape that does not contain
a representation of the parameters of f is not constrained.)

The halting problem is this:

Does there exist a _Turing machine_ that computes the function h?

There are only two answers to this question: "yes", and "no". These
answers are mutually exclusive and exhaustive, so exactly one of them
must be correct unless the question depends on invalid assumptions. As
I've enumerated the assumptions behind the question, I feel confident
that this isn't a problem.

What, of the above, qualifies as an "ill-formed" question?

It seems to me that the halting problem (that is, the question above)
is *not* an ill-formed question by your definition, because we can show
that it has a correct answer. Specifically, we can show that the answer
"yes" is not correct by showing that the existence of a Turing machine
that computes the function h, in tandem with property 2, would lead to
a paradoxical situation. Since the answer "no" does not lead to a
paradox, we can conclude that no Turing machine exists that computes
the function h and that the halting problem (that is, the question
above) is a well-formed question in the sense you mean.

Note that even if no Turing machine that computes h exists, a
machine[1] that computes the algorithm described by

> M( String Input )
> {
> if ( H( Input, Input ) )
> Loop Forever;
> else
> Exit;
> }

may still exist -- look up Oracle machines and the arithmetic
hierarchy. However, if the machine H computes the function h, then
neither the machine H nor the machine M is a Turing machine. If M is a
non-Turing-computable machine, then (machine, input) pairs involving
the machine M (or rather, the encoding of M as a number) are not in the
domain of the function h, and no paradox arises.

-o

PS. I'm surprised you would come back to this. You've left the halting
problem alone for quite a while now, and you really seemed to have "got
it" last time around. How disappointing.

[0] "Turing machines" in the 7-tuple sense given at
<https://en.wikipedia.org/wiki/Turing_machine#Formal_definition>, for
the sake of clarity. These are purely mathematical constructs intended
to represent an idealized model of mechanical computation.
[1] In a related sense of the word "machine" to [0].

[Peter Webb]

"Peter Olcott" <NoS...@OCR4Screen.com> wrote in message

news:zfudndT_xP9gJMfS...@giganews.com...

> On 3/9/2012 7:20 PM, Peter Webb wrote:
>>> If someone turns this TM's input into the Halting Problem, this machine
>>> simply correctly reports false. I see no way that this TM could be
>>> thwarted from always providing the correct return value.
>>
>> 1. Because Turing proved it to be impossible.
>
> Turing showed that self-reference makes providing a universal halt
> analyzer that works for every input (including semantically invalid
> inputs) impossible.

No. He proved that no universal halt analysing TM is possible. He used an
example which was self-referential. Non self referential TMs which have the
same property exist (and have been explicitly described). He just used
self-referential machine as an easy example.

For an example, Google Goodstein Theorem. No TM can prove that a TM which
accepts any number and forms its Goodstein sequence will always halt. This
is in no way self-referential. However, the proof is much harder.

> He did not show that detected self-reference is impossible.
>

Doesn't help. Its not just self-referential statements that have this issue,
lots of other things do. And if you can detect self reference with a TM, it
still doesn't solve your problem.

> This is the one thing that can not be transformed into an instance of the
> Halting Problem, because when it detects the otherwise impossible instance
> of the Halting Problem, it simply correctly returns false (or halts in its
> reject state).

Its not the one thing.

[Peter Olcott]

Your position is from the analytical framework, terminology and concepts
of the theory of computation.

My position is from the framework of pure semantics. From a pure
semantics point of view the examples that I have provided showed that
the m input to h, did meet the specification of ill -formed question as
defined. That assertion can not be correctly denied because the self
evident truth of it is completely verified by the meaning of its words.

[Peter Olcott]

I carefully read your whole post and agree with every aspect of it, yet
you did not bother to address the issue that I raised. I am certainly
not as adept at the nuances of the details of the Theory of Computation
as most everyone here.

The approach that I am taking is from the point of view of pure
semantics. In other words what exactly and precisely is the meaning of
meaning? If there was such a thing as an ill-formed question what
exactly would its properties be? How could these properties be specified
clearly and unequivocally ? How would we go about determining which
elements would meet the specification of ill-formed question?

Let me see if you can now directly address the issue that I raised.

[Ben Bacarisse]

My point entirely. You've said this a dozen times and I've agreed to
the true bits equally as often. None of it has anything to do with
halting questions, though, because they are not ill-formed in that way.

Whatever pure semantics is, it seems to have little to add to the
theory of computation, since nothing you've said alters any of its
theorems.

--
Ben.

[Peter Olcott]

On 3/9/2012 9:21 PM, Peter Webb wrote:
>> He did not show that detected self-reference is impossible.
>>
>
> Doesn't help. Its not just self-referential statements that have this
> issue, lots of other things do. And if you can detect self reference
> with a TM, it still doesn't solve your problem.
>
>
>> This is the one thing that can not be transformed into an instance of
>> the Halting Problem, because when it detects the otherwise impossible
>> instance of the Halting Problem, it simply correctly returns false
>> (or halts in its reject state).
>
> Its not the one thing.
>

Its the one thing that would refute Godel's Incompleteness Theorem.

[Peter Webb]

"Peter Olcott" <NoS...@OCR4Screen.com> wrote in message

news:u7SdnZSghoiXU8fS...@giganews.com...

You are the person going on about "ill formed questions", and claiming that
the Halting problem is an example.

Its up to you to provide a definition. Then show the Halting problem is such
a question (meets your definition). Then show that the definition of "ill
formed" that you have provided mean these functions have some interesting
property, and therefore that the Halting Problem has this interesting
property.

Lots of luck.

> Let me see if you can now directly address the issue that I raised.
>
>

The current issue seems to be that you claim that the Halting question is
"ill formed", but you don't actually have a definition for ill-formed, so it
is impossible to determine if this is true or not.

[Peter Webb]

"Peter Olcott" <NoS...@OCR4Screen.com> wrote in message

news:qsKdnWNXz4LHV8fS...@giganews.com...

No. The function/question is not ill-formed. It always has an answer. The
problem is that no TM can tell you the answer. You constantly conflate the
question/function h (not ill formed) with the fact that no TM can answer it,
ie there is no TM which evaluates this function (rather the point of
Turing's construction).

[Joshua Cranmer]

On 3/9/2012 9:08 PM, Ben Bacarisse wrote:
> Joshua Cranmer<Pidg...@verizon.invalid> writes:
>
>> On 3/9/2012 7:20 PM, Peter Webb wrote:
>>> Firstly, there are plenty of TMs for which we cannot determine if they
>>> halt which do not have any form of self-reference. A self-reference was
>>> used by Turing in his example because it makes the proof work, but
>>> plenty of other TMs have the same problem.
>>
>> Considering that Mr. Olcott seems to believe that anything that relies
>> on self-reference is necessarily erroneous, a simpler way to prove
>> this is to prove that, if you can solve the Halting problem, you can
>> solve Kolmogorov complexity, and then show that the latter function is
>> uncomputable via other means.
>
> But that introduces a whole new field of study. Most people won't be
> persuaded by arguments that involve subjects they have not yet met, and
> self-taught halting deniers often have a narrow focus.

I earlier gave a fairly comprehensive derivation of the uncomputability
of Kolomogrov complexity.

> It might be more fruitful to show a "first principles" proof that the
> busy beaver function is not computable since that involves only Turing
> machines.

The easiest way to prove uncomputability of the Busy Beaver is because
of the undecidability of the Halting Problem, which Mr. Olcott is
objecting to in the first place.

[Ben Bacarisse]

"Peter Webb" <r.peter...@gmail.com> writes:
<snip>

> The current issue seems to be that you claim that the Halting question
> is "ill formed", but you don't actually have a definition for
> ill-formed, so it is impossible to determine if this is true or not.

Well, there's this, taken from the message you replied to:

>>>> An ill-formed question is defined as:
>>>> (a) Any question that lacks a correct answer from the set of all
>>>> possible answers.
>>>>
>>>> (b) Any invocation of a machine that lacks a correct return value
>>>> from the set of all possible return values.

Despite it being informal, it's pretty clear it does not apply,
directly, to halting questions. That's been the main topic in my recent
exchanges with the OP.

--
Ben.

[Peter Olcott]

On 3/9/2012 9:45 PM, Ben Bacarisse wrote:
>> Your position is from the analytical framework, terminology and
>> > concepts of the theory of computation.
>> >
>> > My position is from the framework of pure semantics. From a pure
>> > semantics point of view the examples that I have provided showed that
>> > the m input to h, did meet the specification of ill -formed question
>> > as defined. That assertion can not be correctly denied because the
>> > self evident truth of it is completely verified by the meaning of its
>> > words.
> My point entirely. You've said this a dozen times and I've agreed to
> the true bits equally as often. None of it has anything to do with
> halting questions, though, because they are not ill-formed in that way.

If it was not ill-formed in the way that I defined ill-formed you would
be able to provide the value that h(m,m) could correctly return form the
set of {true,false}.

Since you have already acknowledged that h(m,m) can not provide a
correct return value from the set of {true, false} and this exactly and
precisely meets the specified definition of ill-formed question, then
the invocation of h(m,m) is an ill-formed question within the specific
scope of this specified definition.

You can not possibly correctly deny this because the truth of the above
statement is completely proven by the meaning of the words in the sentence.

If you want to argue this point further, you could argue that the
specified definition of ill-formed question itself is erroneous in some
way.

[Peter Olcott]

The invocation of h(m,m) is a question posed to h on input m such that
no element of the set of {true,false} provides a correct return value to
this invocation.

The problem is that people here just can't get over the fact a question
with identical words can possibly have an entirely different semantic
meaning as another question with the same words. Everyone here seems to
think that if two questions have identical words then they must be the
same question and therefore have the same meaning. This is not true in
this case.

In this case who is asked this question with identical words drastically
alters the meaning of this question.
If h(m,m) is asked does m halt on input m, this is an entirely different
question than if any other Turing Machine, is asked this same question,
even if the words seems to specify the very same question, it is not the
same question. Between the two instances the same words map to an
entirely different set of underlying meanings.

So when I say the invocation of h(m,m) is an ill-formed question, this
does not logically entail that y(m,m) would also derive an ill-formed
question. Although the question has an answer, the fact that h can not
provide a correct answer from the set of all possible answers, logically
entails that the invocation of h(m,m) derives an ill-formed question as
defined previously.

[Peter Webb]

"Ben Bacarisse" <ben.u...@bsb.me.uk> wrote in message
news:0.a325236993ca067ce502.2012...@bsb.me.uk...

> "Peter Webb" <r.peter...@gmail.com> writes:
> <snip>
>
>> The current issue seems to be that you claim that the Halting question
>> is "ill formed", but you don't actually have a definition for
>> ill-formed, so it is impossible to determine if this is true or not.
>
> Well, there's this, taken from the message you replied to:
>
>>>>> An ill-formed question is defined as:
>>>>> (a) Any question that lacks a correct answer from the set of all
>>>>> possible answers.
>>>>>
>>>>> (b) Any invocation of a machine that lacks a correct return value
>>>>> from the set of all possible return values.
>

You snipped the bit I was replying to:

"If there was such a thing as an ill-formed question what
exactly would its properties be? How could these properties be specified
clearly and unequivocally ? How would we go about determining which
elements would meet the specification of ill-formed question?"

> Despite it being informal, it's pretty clear it does not apply,
> directly, to halting questions. That's been the main topic in my recent
> exchanges with the OP.

He appears to have walked away from his earlier definition; now he is quite
clearly saying that he doesn't have a definition of "ill formed question".
Hence my comment.


>
> --
> Ben.

[Peter Webb]

"Peter Olcott" <NoS...@OCR4Screen.com> wrote in message

news:xKGdnR9i2o71RcfS...@giganews.com...

So h(m,m) is the question "does Turing machine m halt on input m"? Well, if
m is the number of a TM which purportedly answers the halting question, the
answer is that it doesn't.

> on input m such that no element of the set of {true,false} provides a
> correct return value to this invocation.
>

Untrue. The function always returns true or false, as every TM either halts
or it doesn't.

> The problem is that people here just can't get over the fact a question
> with identical words can possibly have an entirely different semantic
> meaning as another question with the same words. Everyone here seems to
> think that if two questions have identical words then they must be the
> same question and therefore have the same meaning. This is not true in
> this case.
>

Philosophical twaddle.

> In this case who is asked this question with identical words drastically
> alters the meaning of this question.
> If h(m,m) is asked does m halt on input m, this is an entirely different
> question than if any other Turing Machine, is asked this same question,
> even if the words seems to specify the very same question, it is not the
> same question. Between the two instances the same words map to an entirely
> different set of underlying meanings.
>

More philosophical twaddle.

> So when I say the invocation of h(m,m) is an ill-formed question, this

Is h(m,m) supposed to represent a question (ie a function from m to
{true,false})? If so, it is perfectly well defined. If h(m,m) is suposed to
represent a TM which answers the halting question, then it doesn't exist and
hence you can't discuss what its output would be.

> does not logically entail that y(m,m) would also derive an ill-formed
> question. Although the question has an answer, the fact that h can not
> provide a correct answer from the set of all possible answers, logically
> entails that the invocation of h(m,m) derives an ill-formed question as
> defined previously.

h(m,m) has a correct answer. Its just that you can't produce a TM which
answers it. As proved first by Turing.

[Peter Webb]

"Peter Olcott" <NoS...@OCR4Screen.com> wrote in message

news:r5udnc23La5jTsfS...@giganews.com...

> On 3/9/2012 9:45 PM, Ben Bacarisse wrote:
>>> Your position is from the analytical framework, terminology and
>>> > concepts of the theory of computation.
>>> >
>>> > My position is from the framework of pure semantics. From a pure
>>> > semantics point of view the examples that I have provided showed that
>>> > the m input to h, did meet the specification of ill -formed question
>>> > as defined. That assertion can not be correctly denied because the
>>> > self evident truth of it is completely verified by the meaning of its
>>> > words.
>> My point entirely. You've said this a dozen times and I've agreed to
>> the true bits equally as often. None of it has anything to do with
>> halting questions, though, because they are not ill-formed in that way.
> If it was not ill-formed in the way that I defined ill-formed you would be
> able to provide the value that h(m,m) could correctly return form the set
> of {true,false}.
>

The answer is "false", it never terminates.

> Since you have already acknowledged that h(m,m) can not provide a correct
> return value from the set of {true, false} and this exactly and precisely
> meets the specified definition of ill-formed question, then the invocation
> of h(m,m) is an ill-formed question within the specific scope of this
> specified definition.
>

h(m,m) is a function? Its answer is "false". If m implements a UTM which
determines whether a given TM halts, and you feed it the number for the UTM
itself, then it won't terminate.

> You can not possibly correctly deny this because the truth of the above
> statement is completely proven by the meaning of the words in the
> sentence.
>
> If you want to argue this point further, you could argue that the
> specified definition of ill-formed question itself is erroneous in some
> way.

No, the problem lies in you conflating the concepts of the function h(m,m)
(which is a perfectly reasonable and well defined function) with the TM
which implements this function (non-existent). I suspect you know this
already, because you deliberately use the word "invocation" without
specifying whether you are talking about the function or the corresponding
TM. Substitute the word "TM" or "function" wherever you use "invocation",
and your argument collapses.

[Peter Webb]

"Joshua Cranmer" <Pidg...@verizon.invalid> wrote in message
news:jjeju3$k40$1...@dont-email.me...

> On 3/9/2012 9:08 PM, Ben Bacarisse wrote:
>> Joshua Cranmer<Pidg...@verizon.invalid> writes:
>>
>>> On 3/9/2012 7:20 PM, Peter Webb wrote:
>>>> Firstly, there are plenty of TMs for which we cannot determine if they
>>>> halt which do not have any form of self-reference. A self-reference was
>>>> used by Turing in his example because it makes the proof work, but
>>>> plenty of other TMs have the same problem.
>>>
>>> Considering that Mr. Olcott seems to believe that anything that relies
>>> on self-reference is necessarily erroneous, a simpler way to prove
>>> this is to prove that, if you can solve the Halting problem, you can
>>> solve Kolmogorov complexity, and then show that the latter function is
>>> uncomputable via other means.
>>
>> But that introduces a whole new field of study. Most people won't be
>> persuaded by arguments that involve subjects they have not yet met, and
>> self-taught halting deniers often have a narrow focus.
>
> I earlier gave a fairly comprehensive derivation of the uncomputability of
> Kolomogrov complexity.
>

Which in fact relies on the result that we are trying to prove, as it uses
the undecidability of the halting problem in its construction. Unless you
have a proof which doesn't rely on this fact, which I very much doubt.

[Owen Jacobson]

Well, I was trying to draw out whether you thought the question

Does there exist a _Turing machine_ that computes the function h?

was ill-formed, and if so, why. Since you agree with the rest of my
post, can I take it that (A) you think that that question is not
ill-formed and (B) that you think that the answer to it is "no"?

> The approach that I am taking is from the point of view of pure
> semantics. In other words what exactly and precisely is the meaning of
> meaning? If there was such a thing as an ill-formed question what
> exactly would its properties be? How could these properties be
> specified clearly and unequivocally ? How would we go about determining
> which elements would meet the specification of ill-formed question?
>
> Let me see if you can now directly address the issue that I raised.

If you are attempting to prove that the answer to the question above is
"no" by alternate means, you should say so. You've previously tried to
prove that the answer to the question above is "yes", as I recall, and
I honestly thought your recent threads were either another attempt at
the same or an attempt to argue that the question

Does there exist a _Turing machine_ that computes the function h?

is somehow unanswerable. If I've misunderstood, then I apologize.

-o

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/9/2012 9:45 PM, Ben Bacarisse wrote:
>>> Your position is from the analytical framework, terminology and
>>> > concepts of the theory of computation.
>>> >
>>> > My position is from the framework of pure semantics. From a pure
>>> > semantics point of view the examples that I have provided showed that
>>> > the m input to h, did meet the specification of ill -formed question
>>> > as defined. That assertion can not be correctly denied because the
>>> > self evident truth of it is completely verified by the meaning of its
>>> > words.
>> My point entirely. You've said this a dozen times and I've agreed to
>> the true bits equally as often. None of it has anything to do with
>> halting questions, though, because they are not ill-formed in that way.

> If it was not ill-formed in the way that I defined ill-formed you
> would be able to provide the value that h(m,m) could correctly return
> form the set of {true,false}.

Oh dear. Here we are again. Fourth time? Fifth time? I've lost
count.

In your terminology, h(m,m) is not a halting question. h is just any TM
and it's being run on some input or other. This particular h might me
testing if the input has two consecutive zeros in it, or it might be
testing if the machine encoded by the input would ever write a zero. We
don't know, of course, exactly what h is doing, but we do know that it
is not a halting analyser.

Halting questions look like this: "does machine t halt when run with
input i?" and none of the these are ill-formed (using your own rather
odd definition of ill-formed). You've said you disagree with this --
that you think there are questions of this form that have no correct
true/false answer, but there been nothing to back up that extraordinary
stance.

> Since you have already acknowledged that h(m,m) can not provide a
> correct return value from the set of {true, false} and this exactly
> and precisely meets the specified definition of ill-formed question,
> then the invocation of h(m,m) is an ill-formed question within the
> specific scope of this specified definition.

You are free to call h(m,m) anything you like. "Ill-formed" seems a
silly term for it, but your definitions are your own business (provided
you don't want others to share them). However, it is not a halting
question.

> You can not possibly correctly deny this because the truth of the
> above statement is completely proven by the meaning of the words in
> the sentence.

I have never denied your right to make these definitions, so that the
above becomes vacuously true. I /would/ like to know what you think you
gain by saying it, and I do deny the suitability of the terms you use
(because they carry ordinary English meanings that are inappropriate in
this situation), but have at it. Define away.

> If you want to argue this point further, you could argue that the
> specified definition of ill-formed question itself is erroneous in
> some way.

"This point" is not in dispute. Your definitions are your own business.
(Nobody else is likely to take them up but I certainly don't care about
that).

I do care that you apparently disagree with the plain fact that halting
questions ("does machine t halt when run with input i?") all have
correct true/false answers. Such nonsense suggests that all your hot
air might have been about some other problem altogether (and thus a
waste of time for people who thought you were talking about TM halting)
or that your study of pure semantics has caused you to loose contact
with reality.

It's not too late to come out and agree with this obvious fact. I may
have just misunderstood your earlier "not at all" reply to it.

--
Ben.

[Daryl McCullough]

On Friday, March 9, 2012 9:18:37 PM UTC-5, Peter Olcott wrote:

> Turing showed that self-reference makes providing a universal halt
> analyzer that works for every input (including semantically invalid

> inputs) impossible. He did not show that detected self-reference is
> impossible.

The problem in determining halting is *not* due to self-reference.

Let EQ be the set of equations that can be written in the form
t_1 = t_2, where t_1 and t_2 are terms formed from
(1) Variables x,y,z, x_1, y_1, z_1, x_2, y_2, z_2, etc.
(2) Numerals (in base 10, say), 0, 1, 2, ...
(3) +
(4) *
(5) Parenthesis for grouping

So an example would be the equation
x*x + y*y = z*z

Now consider a computer program solve(eq) that takes an equation eq as an
argument, and then searches for a solution, where a solution would be
a list of numerals n_1, n_2, ... such that replacing the first variable
by n_1, replacing the second variable by n_2, etc, results in a true
statement. solve(eq) then returns the first solution it finds.
So for example, solve("x*x + y*y = z*z") would return (0,0,0) since
0*0 + 0*0 = 0*0. If there is no solution, then solve(eq) runs forever.

Well, sometimes solve(eq) will return an answer, and sometimes it will
run forever, since not all equations have solutions. But
(1) There is no self-reference involved in solve(eq).
(2) There is no program that can predict whether solve(eq) will run
forever, or not.

So even if you restrict yourself to non-self-referencing programs,
there is no way to detect whether programs will halt, or not.

[Peter Olcott]

On 3/10/2012 7:36 AM, Daryl McCullough wrote:
> On Friday, March 9, 2012 9:18:37 PM UTC-5, Peter Olcott wrote:
>
>> > Turing showed that self-reference makes providing a universal halt
>> > analyzer that works for every input (including semantically invalid
>> > inputs) impossible. He did not show that detected self-reference is
>> > impossible.
> The problem in determining halting is*not* due to self-reference.

That is a false statement. What you meant to say is:
The problem in determining halting is *not* ALWAYS due to self-reference.

Try to treat English as a mathematical formalism and our communication
will be much more effective.

In this sense the key is that words are assigned 100% completely precise
sets of semantic meanings. If you ever use a word that is not the very
first (thus default) sense meaning in the dictionary, make sure that you
explicitly specify this and say exactly which sense meaning is being
used. This also applies when you use terms that art such as the term
"decider".

For any new terms (such as ill-formed question) please make sure that
they are specified such that their meaning can not possibly be
misunderstood. When new terms such as this are specified make sure that
you always precisely apply the exact set of semantic meanings that were
specified.

The problem that I am having here is that I specify ill-formed
question(X) and everyone keeps saying that I am wrong because ill-formed
question(Y) does not apply to this case.

[Daryl McCullough]

On Saturday, March 10, 2012 12:19:38 AM UTC-5, Peter Webb wrote:
> "Peter Olcott" <NoS...@OCR4Screen.com> wrote

> > The problem is that people here just can't get over the fact a question
> > with identical words can possibly have an entirely different semantic
> > meaning as another question with the same words. Everyone here seems to
> > think that if two questions have identical words then they must be the
> > same question and therefore have the same meaning. This is not true in
> > this case.
> >
>
> Philosophical twaddle.

I don't think it's entirely twaddle. In trying to understand what
Olcott was getting at, I suggested switching the problem from programs
to people. You have a person, called the subject, who is asked a series
of yes/no questions. He agrees to answer truthfully, using only the words
"yes" and "no". So the researcher asks him the question:
"Will the next word out of your mouth be 'no'?"

On the one hand, it's a perfectly good question, and it has a perfectly
good answer. It's possible, if you know enough about the subject and
the way he responds to questions, to answer the question correctly.
But it's not possible for the *subject* of the experiment to answer
the question correctly.

[Daryl McCullough]

On Saturday, March 10, 2012 9:16:14 AM UTC-5, Peter Olcott wrote:

> The problem that I am having here is that I specify ill-formed
> question(X) and everyone keeps saying that I am wrong because ill-formed
> question(Y) does not apply to this case.

The problem other people are having with you is that nothing
about the halting problem has anything to do with ill-formed
questions.

[Daryl McCullough]

On Saturday, March 10, 2012 9:16:14 AM UTC-5, Peter Olcott wrote:

> Try to treat English as a mathematical formalism and our communication
> will be much more effective.

I doubt it.

[Peter Olcott]

On 3/10/2012 7:01 AM, Ben Bacarisse wrote:
> Peter Olcott<NoS...@OCR4Screen.com> writes:
>
>> > On 3/9/2012 9:45 PM, Ben Bacarisse wrote:
>>>> >>> Your position is from the analytical framework, terminology and
>>>>> >>> > concepts of the theory of computation.
>>>>> >>> >
>>>>> >>> > My position is from the framework of pure semantics. From a pure
>>>>> >>> > semantics point of view the examples that I have provided showed that
>>>>> >>> > the m input to h, did meet the specification of ill -formed question
>>>>> >>> > as defined. That assertion can not be correctly denied because the
>>>>> >>> > self evident truth of it is completely verified by the meaning of its
>>>>> >>> > words.
>>> >> My point entirely. You've said this a dozen times and I've agreed to
>>> >> the true bits equally as often. None of it has anything to do with
>>> >> halting questions, though, because they are not ill-formed in that way.
>> > If it was not ill-formed in the way that I defined ill-formed you
>> > would be able to provide the value that h(m,m) could correctly return
>> > form the set of {true,false}.
> Oh dear. Here we are again. Fourth time? Fifth time? I've lost
> count.
>
> In your terminology, h(m,m) is not a halting question.

That is a false statement: (From the original posting of this thread)

An ill-formed question is defined as:
(a) Any question that lacks a correct answer from the set of all
possible answers.

(b) Any invocation of a machine that lacks a correct return value from
the set of all possible return values.

In order to actually communicate with me you must do more than glance at
a couple of words and then refute, refute, refute.

[Joshua Cranmer]

On 3/9/2012 11:29 PM, Peter Webb wrote:
> Which in fact relies on the result that we are trying to prove, as it
> uses the undecidability of the halting problem in its construction.
> Unless you have a proof which doesn't rely on this fact, which I very
> much doubt.

Sure I do. Loosely, here's one:
Assume you had a machine K(s) that computes the complexity of a string.
Then you can write the following function f(n):

f(n):
For each natural number i in increasing order:
If K(i) = n:
return i

f(n) returns the smallest number that has a complexity of n. Note that
this function has some complexity C. If you passed in, say, f(C^2), you
would compute a number whose minimum complexity is C^2 with a machine
whose complexity is C + 2 lg C, which is a contradiction. Hence f(n),
and K(s) by further analysis, are uncomputable.

Another one you could use is an adaptation of Chaitin's Incompleteness
Theorem.

[George Greene]

Dear Peter Olcott: you CAN'T always GET what you WANT.
In particular, here, you want Templates. You CAN'T HAVE them.
The TM universe is a VERY SIMPLE place. The tape is a STRING.
Each TM is ALSO a STRING (its program, encoded as a string).
That is ALL that is going on in this universe. You DON'T GET
to create new things like "templates" UNLESS YOU GIVE DEFINITIONS
for them. Since you have NOT DEFINED "template" in what follows,
we could say that "an example of an ill-formed sci.logic post
is one in which terms are used before they are defined".

On Friday, March 9, 2012 9:23:16 AM UTC-5, Peter Olcott wrote:
> M( String Input )
> {
> if ( H( Input, Input ) )
> Loop Forever;
> else
> Exit;
> }
>
> H specifies an infinite set of Turing Machines included within template M

No, really, it doesn't. And, more to the point, if H (being an infinite
set) is not recursive, then this is of no value to anyone, because it is no
longer clear HOW to TELL whether a given TM h does-or-does-not even belong
to H IN THE FIRST PLACE. After that, we would still face the problem of
how to tell whether h was or was not "included within template M" -- since,
presumably, what it means for H to be "included within template M" is that
every h in H is "included within template M". You haven't said what templates
are or what this inclusion might mean. YOU are the one who is ill-formed (and
ill-informed).

> h is one element of set H
> m represents template M that has been instantiated using h

You can't instantiate a template until you "use" a TM with it???
This gets more and more ridiclous! Especially if all these things
are undefined!

> Neither element from the set of {true, false} provides a correct return
> value to the invocation of every element referred to by h(m,m).

Now,you are simply off the deep end: your presumption to evaluate a return
value to an invocation of a TM as "correct" (or "incorrect") is ENTIRELY mis-
guided. EVERY such invocation simply RETURNS THE VALUE IT RETURNS -- IF it returns. Some invocations may not halt, in which case NO value is returned.
But that does NOT mean that ANYthing is "ill-formed"!! "Does not halt" is a
MEANINGFUL and WELL-formed outCOME of the invocation, DESPITE the fact that makes it impossible for there to be an outPUT!!

[George Greene]

On Friday, March 9, 2012 5:30:51 PM UTC-5, Ben Bacarisse wrote:

> So, what happens in those cases where there is no true/false answer to

> the question "does t halt on input i"?

Ben, come ON!! This NEVER happens! This CAN'T happen!
If t and i are well-defined, then, for EVERY t and EVERY i,
t either halts on i OR IT DOESN'T!!

THAT IS WHY we use TMs.

Of course, we may not be able to TELL whether t halts on i, or doesn't.
There are some t's and i's that work so diligently with each other that
all we can do is run t on i for a very long time and WAIT TO SEE if it halts.
If it halts SOON enough, then we know, but if it takes too long, then we DON'T know whether it will EVENTUALLY halt later, or whether it will just never halt. But EVEN when we don't KNOW, it is still TRUE that it either halts or it doesn't. The fact that the outcome is not YET known to us does NOT make the outcome doubtful. THERE IS A FACT of the matter. ALWAYS!

[George Greene]

On Friday, March 9, 2012 11:28:23 PM UTC-5, Peter Olcott wrote:
> The invocation of h(m,m) is a question posed to h on input m

OK, fine. m ( or m,m ) is a question and h is a TM that might or might
not answer it, correctly or incorrectly.

> such that no element of the set of {true,false}
> provides a correct return value to
> this invocation.

THIS, on the other hand, IS NOT POSSIBLE.

h simply returns the value it returns, IF it returns.
If h does not halt on m,m then h does not return anything,
so there is no relevant question about what "the set of {true,false} provides".
You CAN'T TALK that way. SETS do NOT *provide*!! TMs provide!! IF they halt!!

[George Greene]

On Saturday, March 10, 2012 11:47:05 AM UTC-5, Peter Olcott wrote:
> In order to actually communicate with me you must do more than glance at
> a couple of words and then refute, refute, refute.

I hereby refute that. I just glanced at these couple of words and
decided to refute them. You really do have to get it through your
thick head that if you have said a couple of things that are easily
refutable, YOU REALLY DO HAVE TO CORRECT THEM AND TRY AGAIN
before whatEVER it was you THOUGHT you were trying to communicate
can get discussed.

[George Greene]

> "Peter Olcott" wrote in message

> >>>>>>>> I already
> >>>>>>>> know that this is unconventional behavior for a TM , after
> >>>>>>>> reading
> >>>>>>>> Chapter 29 of Automata and Computability by Kozen. Conventional
> >>>>>>>> behavior would force the TM to get the wrong answer.

Well, if you KNOW that, why are we here?
Why haven't you just CONCEDED this and moved on?
ANY answer the TM gives is "wrong", BUT IF IT HALTS, IT GIVES ONE.
You do NOT GET to talk about conventional vs. unconventional behavior
for TMs. TMs behave the way they behave;the definitions are ALREADY
conventionally accepted. If you are talking about "unconventional"
behavior then you are talking about something that IS NOT a TM.

> h(m,m) has a correct answer. Its just that you can't produce a TM which
> answers it. As proved first by Turing.

Well, yes, but if he DEFINED h AS a TM, well, then......

[Peter Olcott]

Yes that is the common false presumption.
The specification that I provided for ill-formed question(b) (see below)
exactly corrsponds to the invocation of h(m,m) (also shown below).

M( String Input )
{
if ( H( Input, Input ) )
Loop Forever;
else
Exit;
}

H specifies an infinite set of Turing Machines included within template M

h is one element of set H
m represents template M that has been instantiated using h

Neither element from the set of {true, false} provides a correct return
value to the invocation of every element referred to by h(m,m).

[Peter Olcott]

The (b) specification of ill-formed question that I provided in my
original posting in this thread exactly corresponds to the invocation of
the set of Turing Machine referred to by h(m,m).

Maybe you did not see this original (b) specification?
I provided it to Ben ten times and he never saw it once yet.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/10/2012 7:01 AM, Ben Bacarisse wrote:

<snip>

>> Oh dear. Here we are again. Fourth time? Fifth time? I've lost
>> count.
>>
>> In your terminology, h(m,m) is not a halting question.
> That is a false statement: (From the original posting of this thread)

From the part you've snipped:

Halting questions look like this: "does machine t halt when run with

input i?".

and from the top post:

H specifies an infinite set of Turing Machines included within template M
h is one element of set H
m represents template M that has been instantiated using h

so you can see that h(m, m) is just a run of a Turing machine (with a
pair of encoded machines as input). It can't possible be a halting
question.

If you really, really, think it is one, you'll have a lot of trouble
following any discussion of the halting theorem. A question, and a
machine that tries to answer it, are in entirely separate categories.

> An ill-formed question is defined as:
> (a) Any question that lacks a correct answer from the set of all
> possible answers.
>
> (b) Any invocation of a machine that lacks a correct return value from
> the set of all possible return values.
>
> In order to actually communicate with me you must do more than glance
> at a couple of words and then refute, refute, refute.

I have no idea what I need to do to communicate with you. Any other
tips gratefully received.

--
Ben.

[Peter Olcott]

No such Turing Machine exists because some inputs to some halting
deciders are semantically ill-formed.

The only reason why h(m,m) is not a halting decider is that m forms
semantically invalid input and is thus analogous to asking a Turing
Machine to provide an integer greater than five and less than three.
The answer must be numeric and the TM must respond with a return value.

Note the question does m halt in input m? has a possible correct answer
from the set of {true false}, and it thus not inherently ill-formed.

The invocation of of h(m,m) does not have a possible correct return
value from the set of {true,false} thus exactly meeting the provided
specification for ill-formed question(b). (shown in the original
posting of this thread).

[Peter Olcott]

You can not produce a TM that correctly answers it because the
invocation of h(m,m) has no possible correct return value from the set
of {true,false} thus exactly meeting the (b) specification of an
ill-formed question that I provided.

It is not that h is mute, it is not that h is erroneous, it is not that
h has any short-comings, it is that the m input to h is semantically
invalid.

[Peter Olcott]

On 3/10/2012 3:25 PM, Ben Bacarisse wrote:
>> > On 3/10/2012 7:01 AM, Ben Bacarisse wrote:
> <snip>
>>> >> Oh dear. Here we are again. Fourth time? Fifth time? I've lost
>>> >> count.
>>> >>
>>> >> In your terminology, h(m,m) is not a halting question.
>> > That is a false statement: (From the original posting of this thread)

I am not going to address anything else until you first address the above.
h(m,m) is a halting question within my terminology.
If you bothered to look at what I said you would have realized this fact
20 posts ago.

[Peter Olcott]

On 3/10/2012 3:25 PM, Ben Bacarisse wrote:

> so you can see that h(m, m) is just a run of a Turing machine (with a
> pair of encoded machines as input). It can't possible be a halting
> question.

It is defined as a halting question in my original post.
Words are merely placeholders for sets of semantic meanings.
I explicitly assigned the semantic meaning

ILL_FORMED_QUESTION <assignment_operator>
{Any invocation of a machine that lacks a correct return value from the

set of all possible return values}

It is like a premise in deductive logical inference, (or a "given" in
Geometry) it is indisputable even if it is wrong.

Within the scope of the above definition the reason that h(m,m) can not
provide a correct response from the set of {true,false} is that its m
input is semantically invalid.

The Theory of Computation addresses this same issue with fallacious
circular reasoning (Petitio Principii):
The TM can not decide because it is not a decider.

Why is it not a decider?
Because its just not that's all.

Why not?
Just because.

It couldn't be a problem with the input?
Of course not. Isn't "Just because" a good enough reason?

Not hardly.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/10/2012 3:25 PM, Ben Bacarisse wrote:
>>> > On 3/10/2012 7:01 AM, Ben Bacarisse wrote:
>> <snip>
>>>> >> Oh dear. Here we are again. Fourth time? Fifth time? I've lost
>>>> >> count.
>>>> >>
>>>> >> In your terminology, h(m,m) is not a halting question.
>>> > That is a false statement: (From the original posting of this thread)

> I am not going to address anything else until you first address the
> above.

What's to address? I defined what a halting question is, and h(m, m)
isn't one. If you've also defined that term (differently) somewhere
else there can't be any confusion because I repeated the meaning every
single time I used the term:

Halting questions look like this: "does machine t halt when run with

input i?" and none of the these are ill-formed (using your own rather
odd definition of ill-formed).

> h(m,m) is a halting question within my terminology.

That's fine. Please direct me to (or repeat) your definition so that I
can follow what you mean by the term when you use it. Are you clear
that when I use it it mean questions of the form "does machine t halt

when run with input i"?

If this is just a matter of two different uses of the same term, what's
the problem? Can I conclude that you agree with me that your h(m, m) is
not a question of the form "does machine t halt when run with input i?"
and that no questions of that latter form are ill-formed (using your
meaning of ill-formed)? It would be good to make one small step forward
by getting this fact out of the way. (Actually it's not a small step,
it's a huge one -- and you know it. That's why you won't come out and
say you agree, nor will you explain how it could be otherwise).

> If you bothered to look at what I said you would have realized this
> fact 20 posts ago.

That makes no sense. I can't "realise" something that is wrong.

By the way, why do you keep snipping key details such as the part where
I quoted your definitions of h and m? Other posters have used h with
quite a different meaning to yours -- one in which h(m, m) is, indeed, a
halting question (though now no longer ill-formed, of course). It looks
fishy to me.

--
Ben.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/10/2012 3:25 PM, Ben Bacarisse wrote:
>> so you can see that h(m, m) is just a run of a Turing machine (with a
>> pair of encoded machines as input). It can't possible be a halting
>> question.
> It is defined as a halting question in my original post.

That's fine (for the moment) but how on Earth could you have been
confused? I included an explanation of the how I used the term every
time I used it:

Halting questions look like this: "does machine t halt when run with

input i?" and none of the these are ill-formed (using your own rather
odd definition of ill-formed).

> Words are merely placeholders for sets of semantic meanings.
> I explicitly assigned the semantic meaning

Sure, but that goes for me too. I assigned the term a meaning every
time I used it, precisely because I suspected that you are confused by
it. Using my meaning:

Halting questions look like this: "does machine t halt when run with

input i?" and none of the these are ill-formed (using your own rather
odd definition of ill-formed).

do you now agree that your h(m, m) is not such a question? More
importantly, do you agree that no halting question (my meaning of the
term, of course) is ill-formed (by your meaning of "ill-formed")?

> ILL_FORMED_QUESTION <assignment_operator>
> {Any invocation of a machine that lacks a correct return value from
> the set of all possible return values}
>
> It is like a premise in deductive logical inference, (or a "given" in
> Geometry) it is indisputable even if it is wrong.
>
> Within the scope of the above definition the reason that h(m,m) can
> not provide a correct response from the set of {true,false} is that
> its m input is semantically invalid.
>
> The Theory of Computation addresses this same issue with fallacious
> circular reasoning (Petitio Principii):
> The TM can not decide because it is not a decider.
>
> Why is it not a decider?
> Because its just not that's all.
>
> Why not?
> Just because.
>
> It couldn't be a problem with the input?
> Of course not. Isn't "Just because" a good enough reason?
>
> Not hardly.

We can go into what's wrong with all that later (if you think there is
any point) but I'd rather clear up the issue of what I call halting
questions and you opinion of whether they can be ill-formed.

--
Ben.

[Peter Olcott]

On 3/10/2012 5:29 PM, Ben Bacarisse wrote:
> Peter Olcott<NoS...@OCR4Screen.com> writes:
>
>> > On 3/10/2012 3:25 PM, Ben Bacarisse wrote:
>>> >> so you can see that h(m, m) is just a run of a Turing machine (with a
>>> >> pair of encoded machines as input). It can't possible be a halting
>>> >> question.
>> > It is defined as a halting question in my original post.
> That's fine (for the moment) but how on Earth could you have been
> confused? I included an explanation of the how I used the term every
> time I used it:

I have never been confused at all. I have ALWAYS meant the meaning
specified in my original post. You keep saying that I don't mean that,
but, that never changes the fact that I do mean that meaning.

> Halting questions look like this: "does machine t halt when run with
> input i?" and none of the these are ill-formed (using your own rather
> odd definition of ill-formed).
>
>> > Words are merely placeholders for sets of semantic meanings.
>> > I explicitly assigned the semantic meaning
> Sure, but that goes for me too.

Not when it come to my terms you don't.

I say that X is Y, and you say that X is not Y, yet I have already
specified that X is Y.

When you change the meaning of my terms that is the error of reasoning
known as the fallacy of equivocation.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/10/2012 5:29 PM, Ben Bacarisse wrote:
>> Peter Olcott<NoS...@OCR4Screen.com> writes:
>>
>>> > On 3/10/2012 3:25 PM, Ben Bacarisse wrote:
>>>> >> so you can see that h(m, m) is just a run of a Turing machine (with a
>>>> >> pair of encoded machines as input). It can't possible be a halting
>>>> >> question.
>>> > It is defined as a halting question in my original post.
>> That's fine (for the moment) but how on Earth could you have been
>> confused? I included an explanation of the how I used the term every
>> time I used it:
> I have never been confused at all.

I think we'll have to agree to disagree on that point.

> I have ALWAYS meant the meaning
> specified in my original post. You keep saying that I don't mean that,
> but, that never changes the fact that I do mean that meaning.
>
>> Halting questions look like this: "does machine t halt when run with
>> input i?" and none of the these are ill-formed (using your own rather
>> odd definition of ill-formed).
>>
>>> > Words are merely placeholders for sets of semantic meanings.
>>> > I explicitly assigned the semantic meaning
>> Sure, but that goes for me too.
> Not when it come to my terms you don't.
>
> I say that X is Y, and you say that X is not Y, yet I have already
> specified that X is Y.
>
> When you change the meaning of my terms that is the error of reasoning
> known as the fallacy of equivocation.

Just a guess, but I suspect irony is not your strong suit.

So is my "equivocation" the current reason why you won't answer the key
question? it needn't get in the way.

Since I am not allowed to define a term that you've reserved
to yourself, here it is without it: Do you agree that all questions of
the form "does machine t halt when run with input i?" have a true/false
answer? If so, no such question would fit either

(a) Any question that lacks a correct answer from the set of all
possible answers.

or

(b) Any invocation of a machine that lacks a correct return value from
the set of all possible return values.

and therefore would not be ill-formed (by your definition).

I am really surprised that you could not work out that this is what I've
been asking for so long, but no matter. Do you understand the question
now?

--
Ben.

[George Greene]

On Saturday, March 10, 2012 3:48:58 PM UTC-5, Peter Olcott wrote:
> The (b) specification of ill-formed question that I provided in my
> original posting in this thread exactly corresponds to the invocation of
> the set of Turing Machine referred to by h(m,m).

NO, it DOESN'T.
It IS NOT POSSIBLE for an invocation of a TM to "correspond
to a specification of ill-formed question".

More to the point, your specification is just incoherent.
Is English even your native language?? You said,

"Neither element from the set of {true, false} provides a correct return
value to the invocation of every element referred to by h(m,m)."

Well, OF COURSE "neither element" provides that!
If you could READ ENGLISH, you would know that you had just required
either that "true" (that's one element from the set of {true,false}
"provide a correct return value to the invocation of every element
referred to by h(m,m)" or that "false" (that's the other element)
"provide a correct return value to the invocation of every element
referred to by h(m,m)." In the first place, that's not even what
you meant. You didn't mean for h to return, trivially and universally,
true over all these implications (or false over all of them).
If you are going to say this in natural language then you have got to
learn to avoid QUANTIFIER DYSLEXIA.

In the second place, you CANNOT SAY "every element referred to by h(m,m)".
h is ONE thing. m is ONE thing. There is ONLY ONE "invocation" of
h(m,m). h is ONE Turing Machine. m is ONE input to it. There are NO
"references" to any "elements" INVOLVED here! h either halts on m,m
OR IT DOESN'T. IF it halts, then (for the purposes we are using here)
it either halts returning true or it halts returning false. There is
ABSOLUTELY NO POSSIBILITY of the value it returns being "correct" or
"incorrect"! It just IS WHAT IT IS, NECESSARILY! It is necessarily the
only possible value that could be returned and therefore necessarily the
CORRECT value. Now, if you WANTED h(m,i) to MEAN "return the truth-value of
m halts on i", then it may indeed be the case that the value that h returns
on m,m is not that truth-value, i.e., is the unWANTed truth value. But all
that means is that h IS NOT WHAT YOU WANTED h TO BE.
That is NOT *h*'s FAULT -- THAT IS *YOUR* fault. If you want a better (i.e.
"correct") answer then you are going to have to ASK ANOTHER TURING MACHINE,
NOT h.
The point is, there canNOT EXIST an h that always gives the desired answer
for all m,m. So rather than talking about an ill-formed question, what you
NEED to be talking about is an inconsistent specification of a TM.
If you are going to say "I want a TM that always returns X" then you can't
ALWAYS GET what you WANT! Sometimes, there simply EXISTS NO such TM!

The non-existence of a TM satisfying some criterion dreamt up by Peter Olcott
does NOT entail the existence OF ANY "ill-formed questions".

[George Greene]

On Saturday, March 10, 2012 5:08:17 PM UTC-5, Peter Olcott wrote:

> You can not produce a TM that correctly answers it because

Because NO SUCH TM EXISTS, DUMBASS, since if it did, that would entail
a contradiction.

> the invocation of h(m,m) has no possible correct return value from the set
> of {true,false}

THIS IS BULLSHIT.
The invocation of h(m,m) ALWAYS HAS EXACTLY THE TRUTH VALUE IT HAS.
Whatever value it has IS ALWAYS correct! Who are you to say that
the value that a TM returns on an input is "incorrect"? It necessarily
is exactly what it is! If it is not the same truth-value as "m halts on m"
then all THAT means is that h IS NOT "a TM that returns the truth-value matching whether its 1st input halts on its 2nd input". It is hardly surprising that h is not such a TM, since NO SUCH TM CAN EXIST.

> thus exactly meeting the (b) specification of an
> ill-formed question that I provided.

No, it DOESN'T meet the specification of an ill-formed question that
you provided. What you provided IS NOT a specification of an ill-formed
question, or any other kind of specification either, since it can't even
get its quantifiers straight. What you are actually asking for is a
TM h that FOR ALL m, returns the truth-value of "the machine specified
by string m halts when given, as input, the string m". That is what you
are trying AND FAILING to say. But as long as you insist on saying it your
way instead of that way, you will never be able to see.

>
> It is not that h is mute, it is not that h is erroneous,

It IS SO TOO that h is "erroneous", if by NON-erroneous, you mean
it always gives the desired truth-value. The whole point is that EVERY
h is erroneous for SOME m, SOMEtime, SOMEwhere. No h is ALWAYS right about
ALL halting questions for all machines and all inputs.

> it is not that h has any short-comings,

OF COURSE h does not have any shortcomings! It is "erroneous" but that
is only because the specification it is being asked to fulfill is one
that it is inherently impossible FOR ANY TM to fulfill!

> it is that the m input to h is semantically invalid.

BULLSHIT!!!!! The input m to h IS JUST A MACHINE SPECIFICATION!
The second m IS JUST A STRING to be fed as input to that machine!
h ABSOLUTELY IS a TM that semantically VALIDLY expects its first input
TO BE A SPECIFICATION OF A TM! If its first input IS that then
it IS, NECESSARILY, *BY*DEFINITION*, BY *YOUR* definitions, semantically valid!

[George Greene]

On Friday, March 9, 2012 1:49:53 PM UTC-5, Daryl McCullough wrote:
> No, you didn't. You said that h is one element of the set H.
> But what set is that? The set of all programs that take two
> arguments and return {true, false}?

This is sort of a good question, but I would prefer to play
offense if you are going to play defense (against this crackpottery).
Another approach is to tell him he simply MAY NOT HAVE any "template"
because it violates Occam's razor, because it's a newer bigger kind of
thing, that he can't create without first demonstrating some necessity.
One of the MAIN things TMs ARE FOR is SPECIFYING SETS! Anybody who
wants to talk about a particular set of TMs therefore bears the burden
of HOW to specify THAT set! If he's not going to use a TM then what is
he going to use?!?!??? It is NOT like ANYthing else is STRONGER!!!!
If he is going to use a TM (to specify a set of TMs?!?!???) then the
circularity gets vicious rather quickly.

[George Greene]

On Saturday, March 10, 2012 4:29:28 PM UTC-5, Peter Olcott wrote:

> No such Turing Machine exists because some inputs to some halting
> deciders are semantically ill-formed.

This is JUST BULLSHIT.

The kinds of TMs in question (like h) ABSOLUTELY CAN accept ordered
pairs of strings as input. If you want to assert semantic constraints
then they ABSOLUTELY CAN successfully and validly constraint their
inputs to represent objects of certain types. In particular, ALL
THE MYRIAD h's under consideration here absolutely can insist -- SEMANTICALLY --
AND VALIDLY -- that their first input string represents a TM and that their
second input string should be -- SEMANTICALLY -- interpreted as input to
the TM specified by the first string. THERE IS *NEVER ANYTHING*
"ill-formed" about that, semantically OR OTHERwise.

[Peter Olcott]

On 3/10/2012 8:13 PM, Ben Bacarisse wrote:
> Since I am not allowed to define a term that you've reserved
> to yourself, here it is without it: Do you agree that all questions of
> the form "does machine t halt when run with input i?" have a true/false
> answer?

No the current case proves that.
Why don't you try to correctly answer it without having access to the
internals of h?
I would agree that a machine will either halt or it will fail to halt.
There are numerous reasons why your question can not be correctly
answered, not knowing the machine's response to an input is one of them.

[Peter Olcott]

On 3/10/2012 9:37 PM, George Greene wrote:
> On Saturday, March 10, 2012 3:48:58 PM UTC-5, Peter Olcott wrote:
>> > The (b) specification of ill-formed question that I provided in my
>> > original posting in this thread exactly corresponds to the invocation of
>> > the set of Turing Machine referred to by h(m,m).
> NO, it DOESN'T.

Why don't you re-read it again until you comprehend what I am saying.

[Peter Olcott]

On 3/10/2012 9:47 PM, George Greene wrote:
>> > the invocation of h(m,m) has no possible correct return value from the set
>> > of {true,false}
> THIS IS BULLSHIT.
> The invocation of h(m,m) ALWAYS HAS EXACTLY THE TRUTH VALUE IT HAS.

See that you can't pay enough attention to comprehend what I am saying.
Your paraphrase of what I am saying is completely incorrect.
Maybe you don't know what a return value is?

I will put it directly in Turing Machine terminology:
A Turing Machine has only three choices:
(a) Halt in the accept state
(b) Halt in the reject state
(c) Fail to Halt

Neither (a) nor (b) provides a correct answer regarding whether or not m
will halt on input m, and those are the only possible values within the
entire solution set.

[Peter Webb]

"Peter Olcott" <NoS...@OCR4Screen.com> wrote in message
news:aNmdnQu_ZPLuuMHS...@giganews.com...

You have long since moved from the category of "somebody trying to
understand something" to "crank".

You originally said something wrong - that the question of whether a TM
halts on a given input is "ill defined". A dozen or more people responded,
all identifying the same flaw in your argument.

"Somebody trying to understand something" would have then said, gee guys,
thanks for putting me straight. And would have walked away from the thread
having learned something.

Not you. You tried changing your definitions, making your claim vaguer,
stating things shown to be false as facts, in fact doing everything you can
to try and demonstrate that Turing's Theorem is false, you have found the
fault, and every mathematician in this group and in the world is wrong, and
you are correct.

This is the mark of a crank.

But lets try a little test. Here are two statements. Which one do you
believe to be correct:

1. Turing's Theorem concerning the Halting problem is correct, and Olcott's
problem with it is that he doesn't understand it fully, or

2. Turing's Theorem concerning the Halting Problem is false, and Olcott has
found a fault in it which has eluded every other mathematician?

The first statement would be considered true by somebody trying to
understand Turing's Theorem. The second statement would be considered true
by a crank. Which do you consider true?

[Peter Olcott]

On 3/11/2012 12:12 AM, Peter Webb wrote:
>
> But lets try a little test. Here are two statements. Which one do you
> believe to be correct:
>
> 1. Turing's Theorem concerning the Halting problem is correct, and
> Olcott's problem with it is that he doesn't understand it fully, or
>
> 2. Turing's Theorem concerning the Halting Problem is false, and
> Olcott has found a fault in it which has eluded every other
> mathematician?

What I am saying is coming from a brand new field of mathematics that is
yet nearly fully elaborated. It is the mathematics of the meaning of
words.

It is true that Turing's Theorem shows that the Halting Problem can not
be solved for all inputs.
It is true that every Turing Machine either halts or fails to halt.

There is no error in what I have said in the first post of this thread.
The meaning of the words of the first posting of this thread completely
prove the truth of these words.