Re: Pathological Self-Reference and the Halting Problem

[Peter Olcott]

On 3/15/2012 8:34 AM, Ben Bacarisse wrote:
> Furthermore, it allows you to obscure that
> crucial distinction between a run of a machine (which you now call "a
> question") and the actual question that a decider must answer correctly.
A question with Pathological Self-Reference is self-evidently a
different question than one without Pathological Self-Reference. If you
would say otherwise, I would suspect that you may be a liar.

[Peter Olcott]

On 3/15/2012 8:34 AM, Ben Bacarisse wrote:

> It's not mathematics, because it has no effect whatsoever on the
> theorems involved. Undecidable set are still undecidable. Halting is
> still undecidable. All you've done is obscure the mathematical results
> behind a collection of definitions with deliberately confusing names.
It is the mathematics of semantics, and thus indirectly related the the
mathematics of the theory of computation. If the Halting Problem is only
based on a logical error, then one merely needs to detect this and
reject the input.

[Peter Olcott]

On 3/15/2012 8:34 AM, Ben Bacarisse wrote:

> Actually it's even worse than this because your terms are so general
> that even decidable problems are "based on an ill-formed question".
> This is, in part, Patricia's point. To get only the desired degree of
> obfuscation you probably intended to limit "ill-formed questions" to be
> ones where*every* machine must fail to decide at least one case
> correctly. You didn't say that because it would make the fact that you
> are just defining the outcome you want far too clear.

Only questions that have no possible correct answer are ill-formed. This
is how ill-formed is defined.
If one machine can possibly correctly answer a question, then it is not
ill-formed for this machine,

[Peter Olcott]

On 3/15/2012 8:34 AM, Ben Bacarisse wrote:

> Yes, and you could just talk about correct answers if you wanted to be
> clear: no TM decides all halting instances correctly.
Not even an omnipotent being can correctly answer ill-formed questions.
Even God can't make a square circle. (must simultaneously meet the
mathematical specification of each)

[Peter Olcott]

On 3/15/2012 8:49 AM, Joshua Cranmer wrote:
> On 3/14/2012 6:52 PM, Peter Olcott wrote:
>> Given this setup, we can ask the volunteer the question:
>> "Will the next word out of the Volunteer’s mouth be 'no'?"
>>
>> Since the question posed to the volunteer has self-reference it is a
>> different question than when this word-for-word question is asked of
>> anyone else.
>
> Not necessarily. The real question that is being asked is not what you
> are saying, but the following question:
> "Will the next word out of Smith's mouth be no?"
>
> This question can be asked to everybody and have a consistent answer.

Yes but, the difference is that both elements of the set {yes, no}
always provide an incorrect answer when the question is posed to the
volunteer. This is not the case when this word-for-word question is
posed to someone besides the one to which pathological Self-Reference
has been applied.

The differing truth values for the question depending upon who is asked
conclusively proves that the semantics of these questions is not the
same between its two instances.

>
>> A semantically ill-formed question is defined as:
>> Any question that lacks a correct answer from the set of all possible
>> answers.
>
> Let me put something in another way. Do you believe that someone can
> be forced to lie? Your definition implies that you do not believe this
> to be the case.
>
> I will also point out: self-reference is not necessary to prove
> undecidability of the Halting problem. I gave proof of this earlier.
> It is merely the easiest way to prove undecidability.
>
Like I said the reasoning that I have provided conclusively proves (by
tautology) that there is either an ill-formed question, or a correct
answer can possibly be provided.

[Peter Olcott]

On 3/15/2012 8:55 AM, Ben Bacarisse wrote:
> Peter Olcott<NoS...@OCR4Screen.com> writes:
>
>> On 3/14/2012 10:29 PM, Ben Bacarisse wrote:
>>>> pecification?
>>> Proper definitions would help. If you defined your terms formally you
>>> might see the absurdity of what you are saying.
>>>
>> If you could point out what you think is missing from my definition I
>> could clarify this.
> What's missing is a degree of formality. How much is up to you, but
> English is terrible way to define subtle issues around computability.
>
Please provide me with the range of possible understandings of what I am
saying, and I will do what I can to reign in this range.

[Peter Olcott]

On 3/15/2012 2:33 PM, Patricia Shanahan wrote:

> On 3/15/2012 2:41 AM, Peter Olcott wrote:
>> On 3/14/2012 10:29 PM, Ben Bacarisse wrote:
>>>> pecification?
>>> Proper definitions would help. If you defined your terms formally you
>>> might see the absurdity of what you are saying.
>>>
>> If you could point out what you think is missing from my definition I
>> could clarify this.
>

> The problem with the current definitions is that I cannot work out what
> is, or is not, an ill-formed question in (b) sense.
>

The example of Pathological Self-Reference that I provided concretely
specifies at least one set of instances of ill-formed question in the
(b) sense.

> It is clear that there are some questions that do not have answers. I'm
> not concerned with those.
>
> The issue is combinations of TM M, a language L defined over M's input
> symbols, and a finite string of M's input symbols, X such that you would
> consider applying M to decide whether X is in L to be an ill-formed
> question.
>
> What features of M, L, and X should I examine?
>
> There are four cases:
>
> 1. X is a member of L, and M returns true.
>
> 2. X is not a member of L, and M returns false.
>
> 3. X is a member of L, and M returns false.
>
> 4. X is not a member of L, and M returns true.
>
> In cases 3 and 4, we know that M is not a decider for L, but I don't
> know whether you consider the question to be ill-formed.
>
> What features of M, L, and X should I consider in trying to interpret a
> type 3 or type 4 result?
>
> For example, suppose M is a TM that always returns false, L is the
> language of even length strings, and X is "00". Is the question
> ill-formed? Why? Or why not?
>
> Similarly, suppose M is a TM that always returns false, L is the
> language of descriptions of TM computations that halt, and X is the TM
> computation that runs M on empty input. Is the question ill-formed? Why?
> Or why not?
>
> Patricia
>
I will have to look into this further. It might be the case that the
symbols and language of mathematics are insufficiently expressive to
represent what I am saying. It might be the case that when a Turing
Machine is translated into set theory, that something is lost in the
translation.

I am gaining a more solid foundation in the theory of computation from
Dexter Kozen's great book. I may be able to answer this question later on.

[Patricia Shanahan]

On 3/15/2012 3:32 PM, Peter Olcott wrote:
> On 3/15/2012 2:33 PM, Patricia Shanahan wrote:

...

>> For example, suppose M is a TM that always returns false, L is the
>> language of even length strings, and X is "00". Is the question
>> ill-formed? Why? Or why not?
>>
>> Similarly, suppose M is a TM that always returns false, L is the
>> language of descriptions of TM computations that halt, and X is the
>> TM computation that runs M on empty input. Is the question
>> ill-formed? Why? Or why not?
>>
>> Patricia
>>
> I will have to look into this further. It might be the case that the
> symbols and language of mathematics are insufficiently expressive to
> represent what I am saying. It might be the case that when a Turing
> Machine is translated into set theory, that something is lost in the
> translation.
>
> I am gaining a more solid foundation in the theory of computation
> from Dexter Kozen's great book. I may be able to answer this question
> later on.

Now you should know why some of us do not think you have defined
"ill-formed question" precisely enough.

I suggest continuing your studies until you either decide the concept is
not a useful one in this context, or produce a definition that anyone,
yourself included, can apply to determine whether a combination of TM,
language, and input string does or does not constitute an "ill-formed
question".

Patricia

[Ben Bacarisse]

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

> On 3/15/2012 8:34 AM, Ben Bacarisse wrote:

>> "Based on" sounds as if you are talking about something fundamental
>> about the problem, when, in fact, none of the questions required to
>> solve the problem are ill-formed,
> The ones involving Pathological Self-Reference are ill-formed.

Yes, I am aware that that is your position. Re-stating it does very
little good. Defining "ill-formed" so that the precise meaning of your
assertions become clear to everyone would help enormously.

Bye the way, breaking your replies to my single post across more than
one reply is not helpful. For one thing, it fragments the thread into
dozens of separate sub-treads.

--
Ben.

[Ben Bacarisse]

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

> On 3/15/2012 8:34 AM, Ben Bacarisse wrote:

>> "ill-formed question" just means that some machine gets some input case
>> wrong but it sounds (from the English meanings of the words) like
>> something quite different.
> It is not that it just happens to get the wrong answer because its
> algorithm has an error, it is that there exists no possible correct
> return value when Pathological Self-Reference is involved.

No, that's not true. If you defined your terms more formally I think
you'd see this. Let me try to show you where your informal terms come
unstuck.

Your classic example (I don't like your confusingly calling it a
"question" but I can't change your mind on that) is h(m, m) where h is
some Turing machine and m is the deviously constructed machine you've
shown a thousand times. It seems to be your contention "that there
exists no possible correct return value" in this case. First, what's a
"correct return value" in this context? My best guess, since this is
all about a halting decider, is that a correct return would be "true" if
m(m) halts and "false" if it does not. Well, as I've said a thousand
times myself, m(m) either halts or it does not. There is no other
option (this fact comes from the definition of a Turing machine). In my
book, that means "there exists" a correct return. h does not compute
it, but it exists none the less.

This is probably not what you meant, but I can't do anything but take my
best guess at what the English means. If you defined an "ill-formed
question" in a formal way, maybe we'd agree on something now and again.

--
Ben.

[Ben Bacarisse]

Eh? What you've just written is a tautology. A thing with some property
and another thing without it are, of course, different things. It's
vacuously correct but I don't see the connection to what I wrote.

--
Ben.

[Ben Bacarisse]

It isn't. You can't. Rice's theorem.

(I'm not going to write more than a few words because you don't seem to
want to talk in anything but sound bites, and now there are at least
three micro-threads all from my one post).

--
Ben.

[Ben Bacarisse]

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

> If one machine can possibly correctly answer a question, then it is
> not ill-formed for this machine,

The question "does machine t halt on input i" is correctly answered by
either the machine that always says "yes" or by the one that always says
"no". It is, according to this latest definition, ill-formed for all
those machines that get it wrong and well-formed for those that get it
right. That's a mind-numbingly useless definition. It means that
ill-formed is not a property of a question at all.

(By the way, my extreme snipping is deliberate).

--
Ben.

[Ben Bacarisse]

Are you feeling OK?

--
Ben.

[Ben Bacarisse]

That's hard because I can't always tell how wide a range of meanings you
ascribe to your terms, and I am not even sure it's strictly a range.
But for starters, when I asked you if you agreed with the statement that
every question of the form "machine t halts on input i" has a correct
true/false answer you answered both yes and no. That suggests you have
at least two widely differing meanings for at least one of the terms,
but I am not sure which word or words they are.

--
Ben.

[Joshua Cranmer]

On 3/15/2012 5:09 PM, Peter Olcott wrote:
> On 3/15/2012 8:49 AM, Joshua Cranmer wrote:
>> This question can be asked to everybody and have a consistent answer.
>
> Yes but, the difference is that both elements of the set {yes, no}
> always provide an incorrect answer when the question is posed to the
> volunteer. This is not the case when this word-for-word question is
> posed to someone besides the one to which pathological Self-Reference
> has been applied.
>
> The differing truth values for the question depending upon who is asked
> conclusively proves that the semantics of these questions is not the
> same between its two instances.

As I am understanding it, you believe that the well-formedness of a
question is not an intrinsic property of the question but a property of
both the question and the person you ask it of. This might explain why
everyone is so confused about what you consider ill-formed questions,
since whether or not a question is ill-formed is context-dependent (and,
incidentally, unknowable :-P).

>> I will also point out: self-reference is not necessary to prove
>> undecidability of the Halting problem. I gave proof of this earlier.
>> It is merely the easiest way to prove undecidability.
>>
> Like I said the reasoning that I have provided conclusively proves (by
> tautology) that there is either an ill-formed question, or a correct
> answer can possibly be provided.

All of your reasoning that I can find boils down to "The counterexample
that people should be excluded because it is 'ill-formed'. Therefore, no
counterexample can exist." A bit of a logical fallacy, if you ask me or
any logician. Well, it might not be if 'ill-formed' really just means
'it returned the wrong answer', at which point the result is
tautologically useless and completely orthogonal to the original proof.

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

[Peter Olcott]

On 3/15/2012 5:55 PM, Ben Bacarisse wrote:
> No, that's not true. If you defined your terms more formally I think
> you'd see this. Let me try to show you where your informal terms come
> unstuck.
>
> Your classic example (I don't like your confusingly calling it a
> "question" but I can't change your mind on that) is h(m, m) where h is
> some Turing machine and m is the deviously constructed machine you've
> shown a thousand times. It seems to be your contention "that there
> exists no possible correct return value" in this case. First, what's a
> "correct return value" in this context? My best guess, since this is
> all about a halting decider, is that a correct return would be "true" if
> m(m) halts and "false" if it does not. Well, as I've said a thousand
> times myself, m(m) either halts or it does not. There is no other
> option (this fact comes from the definition of a Turing machine). In my
> book, that means "there exists" a correct return. h does not compute
> it, but it exists none the less.

From the point of view of Pathological Self-Reference no correct answer
exists because from the point of view of Pathological Self-Reference
neither answer of all possible answers is correct. From the point of
view of Pathological Self-Reference h(m,m) is an ill-defined question.

Since the point of view outside of Pathological Self-Reference does have
a correct answer from the set of all possible answers, this single fact
conclusively proves beyond all possible doubt that this must be a
different question.

Thus showing that question (B) is not ill-formed provides absolutely no
evidence what-so-ever that question (A) is not ill-formed.

[Peter Olcott]

You keep arguing that because the question can be correctly answered
when there is no Pathological Self-Reference, that it is not an
ill-formed question when there is Pathological Self-Reference.

[Peter Olcott]

On 3/15/2012 6:09 PM, Ben Bacarisse wrote:
>> It is the mathematics of semantics, and thus indirectly related the
>> > the mathematics of the theory of computation. If the Halting Problem
>> > is only based on a logical error, then one merely needs to detect this
>> > and reject the input.
> It isn't. You can't. Rice's theorem.

Rice's Theorem does not show that detecting Pathological Self-Reference,
is impossible.

[Peter Olcott]

Just because I can't currently translate it into set theory does not
logically entail that I am incorrect. There is also Pathological
Self-Reference, in the Liar Paradox, and detecting this error of
reasoning did not require any of the details of the theory of computation.

It may be simply that the symbols and language of mathematics simply
fail to represent things such as I am presenting within their
abstraction. When one translates an idea into an abstraction of that
idea details are always lost.

[Peter Olcott]

On 3/15/2012 6:17 PM, Ben Bacarisse wrote:
>> If one machine can possibly correctly answer a question, then it is
>> > not ill-formed for this machine,
> The question "does machine t halt on input i" is correctly answered by
> either the machine that always says "yes" or by the one that always says
> "no". It is, according to this latest definition, ill-formed for all
> those machines that get it wrong and well-formed for those that get it
> right.

Not(ill-formed) != well-formed Which error of reasoning is this I
forget, Non Sequitur?

[Peter Olcott]

On 3/15/2012 6:54 PM, Ben Bacarisse wrote:
> That's hard because I can't always tell how wide a range of meanings you
> ascribe to your terms, and I am not even sure it's strictly a range.
> But for starters, when I asked you if you agreed with the statement that
> every question of the form "machine t halts on input i" has a correct
> true/false answer you answered both yes and no. That suggests you have
> at least two widely differing meanings for at least one of the terms,
> but I am not sure which word or words they are.

Without Pathological Self-Reference the answer may be yes, otherwise it
is no.

[Peter Olcott]

On 3/15/2012 7:01 PM, Joshua Cranmer wrote:
> As I am understanding it, you believe that the well-formedness of a
> question is not an intrinsic property of the question but a property
> of both the question and the person you ask it of. This might explain
> why everyone is so confused about what you consider ill-formed
> questions, since whether or not a question is ill-formed is
> context-dependent (and, incidentally, unknowable :-P).

I have no beliefs only facts and theories.
If a question is asked with Pathological Self-Reference then it can not
possibly be answered correctly.
If a question is asked without Pathological Self-Reference then it can
possibly be answered correctly.

This by itself conclusively proves that the two questions mathematically
map to a different sets of semantic meanings, thus are necessarily
different questions, even if they have identical words.

[Peter Olcott]

On 3/15/2012 7:01 PM, Joshua Cranmer wrote:

>> Like I said the reasoning that I have provided conclusively proves (by
>> tautology) that there is either an ill-formed question, or a correct
>> answer can possibly be provided.
>
> All of your reasoning that I can find boils down to "The
> counterexample that people should be excluded because it is
> 'ill-formed'. Therefore, no counterexample can exist." A bit of a
> logical fallacy, if you ask me or any logician. Well, it might not be
> if 'ill-formed' really just means 'it returned the wrong answer', at
> which point the result is tautologically useless and completely
> orthogonal to the original proof.

Anything that makes providing correct answer impossible derives an
ill-formed question by definition.
If nothing makes providing a correct answer impossible, then the Halting
Problem can not be created.

[Peter Olcott]

On 3/15/2012 7:01 PM, Joshua Cranmer wrote:

> since whether or not a question is ill-formed is context-dependent
> (and, incidentally, unknowable :-P).

How is it unknowable?

[Patricia Shanahan]

This probably isn't the basis of Joshua's comment, but empirically, even
you cannot tell me whether a couple of very simple cases involve
"ill-formed questions".

Patricia

[Joshua Cranmer]

On 3/15/2012 9:00 PM, Peter Olcott wrote:
> On 3/15/2012 7:01 PM, Joshua Cranmer wrote:
>> As I am understanding it, you believe that the well-formedness of a
>> question is not an intrinsic property of the question but a property
>> of both the question and the person you ask it of. This might explain
>> why everyone is so confused about what you consider ill-formed
>> questions, since whether or not a question is ill-formed is
>> context-dependent (and, incidentally, unknowable :-P).
> I have no beliefs only facts and theories.

Another example where you appear to have a different definition of
"belief" than the rest of the world. According to my definition of
belief (one believes something if one holds it to be true), you must
have beliefs if you claim to have facts and theories.

> If a question is asked with Pathological Self-Reference then it can not
> possibly be answered correctly.
> If a question is asked without Pathological Self-Reference then it can
> possibly be answered correctly.
>
> This by itself conclusively proves that the two questions mathematically
> map to a different sets of semantic meanings, thus are necessarily
> different questions, even if they have identical words.

Do you agree or disagree with the following statement:
Whether or not a question (in the sense of a specific instance of any
decision problem) is ill-formed is dependent on only the instance in
question and does not depend on which computing device is being asked to
answer the question.

[Joshua Cranmer]

So, according to your current definitions, your argument reduces to "The
Halting problem is correct, if you exclude all the cases where it is
wrong." So, obviously, the function ADD(M, w) returning a non-zero value
is a correct halting decider, according to your definition. This is the
"tautologically useless" interpretation I mentioned above.

[Ben Bacarisse]

Unless you specify what "the question" is you will always be able to
come up with this sort of equivocation. You asked what needs to be
formalised -- I'd start with that. However, since there is a new cloud
of pixie dust over everything called "Pathological Self-Reference"
I don't expect that alone to be enough to provide clarity.

> Thus showing that question (B) is not ill-formed provides absolutely
> no evidence what-so-ever that question (A) is not ill-formed.

Indeed, yet you make this switch often. You slide effortlessly from the
"ill-formed" h(m, m) to say that the basic question of halting is
ill-formed. It isn't. Not even by the most inclusive reading of this
vague term is it ever ill-formed.

--
Ben.

[Ben Bacarisse]

I asked if *every* question of the form "does machine t halt on input i"
has a correct true/false answer. If your cryptic remarks about
Pathological Self-Reference mean that some of these questions may do and
some don't, then your answer is surely no, they do not *all* have
true/false answers. Can we agree on that?

I fear, however, that the magic of Pathological Self-Reference actually
enables you to answer both yes and no about all of them. Let's hope
not.

I don't suppose there is any chance you'll define this PSR?

--
Ben.

[Ben Bacarisse]

Yours is called "dodging the question". My point remains exactly the
same if you substitute not ill-formed for well-formed:

The question "does machine t halt on input i" is correctly answered by
either the machine that always says "yes" or by the one that always
says "no". It is, according to this latest definition, ill-formed for

all those machines that get it wrong and not ill-formed for those that
get it right.

This means that the term "ill-formed question" that you've used time and
time again has no meaning on its own. Ill-formed is not, it seems, a
property of a question, but of a question "for some machine".

--
Ben.

[Ben Bacarisse]

It does for what you used to call "self-reference", but I presumably
this new property of Pathological Self-Reference is quite different to
that. Now all you need to do is (a) define Pathological Self-Reference,
(b) prove that it is "detectable", and (c) prove that all other hating
instances are decidable.

--
Ben.

[Ben Bacarisse]

To what does the "it" refer? Your remarks above suggest that it is
important that there are two different questions (one with and one
without this PSR, whatever that is) but the sentence form suggests only
one.

Anyway, I'm not arguing about Pathological Self-Reference since I have
no idea what it is. You may think that's what I'm doing, but until you
define it I can't agree or disagree with any remark about it.

--
Ben.

[Patricia Shanahan]

Ben Bacarisse wrote:
> Peter Olcott <NoS...@OCR4Screen.com> writes:

...

>> You keep arguing that because the question can be correctly answered
>> when there is no Pathological Self-Reference, that it is not an
>> ill-formed question when there is Pathological Self-Reference.
>
> To what does the "it" refer? Your remarks above suggest that it is
> important that there are two different questions (one with and one
> without this PSR, whatever that is) but the sentence form suggests only
> one.
>
> Anyway, I'm not arguing about Pathological Self-Reference since I have
> no idea what it is. You may think that's what I'm doing, but until you
> define it I can't agree or disagree with any remark about it.
>

Please could we concentrate on getting "ill-formed question" defined?

Even if Pathological Self-Reference were defined, it would not close out
the ill-formed question issue. As I understand, to the limited extent
that I do understand it, a TM computation does not have to involve
self-reference, pathological or otherwise, in order to be ill-formed.

Patricia

[Patricia Shanahan]

More specifically: "There never was a self-reference requirement within
any of my specifications of ill-formed question."

[https://groups.google.com/group/comp.theory/msg/d53ee3f31bc8c4ed]

So you see, even if you managed to find out exactly what is, and is not,
"Pathological Self-Reference" you would be no closer to finding out what
is, and is not, an "ill-formed question".

Patricia

[Peter Olcott]

On 3/15/2012 9:22 PM, Patricia Shanahan wrote:

I already told you two cases.

[Peter Olcott]

On 3/15/2012 9:39 PM, Joshua Cranmer wrote:
>
> Another example where you appear to have a different definition of
> "belief" than the rest of the world. According to my definition of
> belief (one believes something if one holds it to be true), you must
> have beliefs if you claim to have facts and theories

The way that most people have beliefs is typically with emotional
attachment of some degree, with current working hypotheses subject to
future revision as more information becomes available there typically is
no such emotional attachment.

[Peter Olcott]

On 3/15/2012 9:39 PM, Joshua Cranmer wrote:
>

> Do you agree or disagree with the following statement:
> Whether or not a question (in the sense of a specific instance of any
> decision problem) is ill-formed is dependent on only the instance in
> question and does not depend on which computing device is being asked
> to answer the question.

That statement is illl-formed because in the case of Pathological
Self-Reference the specific instance of the question depends upon
whether or not the computing device being invocated has this
Pathological Self-Reference or not. If we switch machines between one
with Pathological Self-Reference and one without Pathological
Self-Reference then it becomes a different question entirely.

This is completely proven by the fact that in the case of Pathological
Self-Reference there is no possible correct answer whereas the case of
no Pathological Self-Reference there is a correct answer.

[Peter Olcott]

On 3/15/2012 9:43 PM, Joshua Cranmer wrote:
> So, according to your current definitions, your argument reduces to
> "The Halting problem is correct, if you exclude all the cases where it
> is wrong." So, obviously, the function ADD(M, w) returning a non-zero
> value is a correct halting decider, according to your definition. This
> is the "tautologically useless" interpretation I mentioned above.

"The Halting problem is correct, if you exclude all the cases that are
themselves incorrect". In other words if you exclude the semantically
invalid input, the halt decider is always correct.

It is like asking for the square root of an ordinary negative number
without allowing imaginary numbers, the data to the input is invalid,
thus the question is ill-formed:
RealNumber SquaretRoot(-53.65)

[Patricia Shanahan]

I'm talking about the questions I posed in
https://groups.google.com/group/comp.theory/msg/2df0c02388412b73. The
only response I saw was
https://groups.google.com/group/comp.theory/msg/99462b1fbcd0940b, which
answered neither question.

Maybe I missed a more substantive response, but if so the Google groups
archive missed it as well. Perhaps you could re-post.

If you had a workable, usable definition, anyone would be able to look
at a couple of questions involving one of the simplest possible TMs, and
give definitive answers as to whether or not each of them involves an
ill-formed question.

I was hoping to present a series of successively more subtle questions
along this line to try to nail down the definition. The fact that I have
not yet seen answers to even the first two questions in the series is
disappointing.

Also, it would be helpful if you could clarify the following: Are all
ill-formed questions based on self-reference?

Patricia

[Ben Bacarisse]

Patricia Shanahan <pa...@acm.org> writes:

<snip>

> Please could we concentrate on getting "ill-formed question" defined?

Agreed. I'll back off a bit.

I have a feeling, though, that the definition has changed and PSR will
turn out to be central to the new notion of "ill-defined". I hope I am
wrong, but I suspect that Peter can see that the old definition has no
value to him, so something new is need.

<snip>
--
Ben.

[Ben Bacarisse]

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

> On 3/15/2012 9:43 PM, Joshua Cranmer wrote:
>> So, according to your current definitions, your argument reduces to
>> "The Halting problem is correct, if you exclude all the cases where
>> it is wrong." So, obviously, the function ADD(M, w) returning a
>> non-zero value is a correct halting decider, according to your
>> definition. This is the "tautologically useless" interpretation I
>> mentioned above.
>
> "The Halting problem is correct, if you exclude all the cases that are
> themselves incorrect". In other words if you exclude the semantically
> invalid input, the halt decider is always correct.

All undecidable sets have decidable subsets, but the part that's
leftover is, clearly, undecidable. The set, H, of machine/input pairs
that represents the halting problem can be partitioned into those cases
that are "semantically invalid" (I) and those that are not (V). I.e.

H = I ∪ V, and I ∩ V = ∅

(I hope you can see the union, intersection and empty set symbols
there).

Either I or V (or both) is undecidable. No matter how you partition an
undecidable set, one part of it must remain undecidable.

<snip>
--
Ben.

[Patricia Shanahan]

Consider these two statements:

A: X is the only reason TM halting is undecidable.

B: X is the only reason a TM that always returns false is not a decider
for TM halting.

I think Peter would like to find a value of X that gives him an argument
for A without leading to similar, equally valid or invalid, arguments
for B.

When we focus on statement A, he tends to broaden the definition of X,
so that any wrong result from a hypothetical halting decider would
necessarily involve the current X. When we focus on statements like B,
he tends to narrow it, for example by requiring self-reference, or even
"pathological" self-reference, for some undefined value of "pathological".

Keeping the definition of X vague, which is much easier in English than
in mathematical notation, is the only way to make this work.

Patricia

[Ben Bacarisse]

I can't say I've spotted the pattern of widening and narrowing, but it
would certainly explain the feeling of eating Jello-O with chop sticks
that this discussion gives me.

--
Ben.

[Patricia Shanahan]

Incidentally, I don't think this is at all deliberate. It is just that
Peter seems to believe intensely in halting decidability and is
searching for anything that will let him keep that belief, despite
mathematical proof to the contrary.

Patricia

[Peter Olcott]

On 3/15/2012 10:00 PM, Ben Bacarisse wrote:
> Indeed, yet you make this switch often. You slide effortlessly from the
> "ill-formed" h(m, m) to say that the basic question of halting is
> ill-formed. It isn't. Not even by the most inclusive reading of this
> vague term is it ever ill-formed.

That no Turing Machine can determine halting for every input is not an
ill-formed statement.

The reason that not every Turing Machine can not determine halting for
all inputs is that some of these inputs are semantically invalid.

I asked you a long time ago what return value could the invocation of
h(m,m) correctly return and you failed to answer this question too. If
there really is nothing wrong with the question then why can't you
answer it?

[Peter Olcott]

On 3/15/2012 10:15 PM, Ben Bacarisse wrote:
> I asked if*every* question of the form "does machine t halt on input i"

> has a correct true/false answer. If your cryptic remarks about
> Pathological Self-Reference mean that some of these questions may do and

> some don't, then your answer is surely no, they do not*all* have

> true/false answers. Can we agree on that?

They do not all have correct {true, false} answers.

[Peter Olcott]

On 3/15/2012 10:28 PM, Ben Bacarisse wrote:
> The question "does machine t halt on input i" is correctly answered by
> either the machine that always says "yes" or by the one that always
> says "no".

That is a false statement. It seems to be a blatantly false statement.
Are you back to not paying attention again and just spouting off anything?

[Patricia Shanahan]

Maybe you are not understanding what he is saying, but he is right.

For those combinations of t and i for which t does halt with input i,
the machine that always returns true reports the correct answer.

For those combinations of t and i for which t does not halt with input
i, the machine that always returns false reports the correct answer.

What cannot exist is a single machine that reports the correct answer
for every such question.

Patricia

[Peter Olcott]

On 3/15/2012 10:34 PM, Ben Bacarisse wrote:
> It does for what you used to call "self-reference", but I presumably
> this new property of Pathological Self-Reference is quite different to
> that. Now all you need to do is (a) define Pathological Self-Reference,
> (b) prove that it is "detectable", and (c) prove that all other hating
> instances are decidable.

This is all obvious from the examples that I have already provided.
Pathological Self-Reference is self-evidently self reference that
derives ill-formed questions.

If you try and construct an instance of the Halting Problem that will
apply to a machine that only detects Pathological Self-Reference and
does not look at halting, I am pretty sure that you and everyone else
will continue to only fail.

This machine can not be trapped into Pathological Self-Reference because
as soon as it sees it, it merely correctly reports true. There may be
other cases of ill-formed questions besides Pathological Self-Reference
that prevent halting from being correctly decided.

[Peter Olcott]

On 3/15/2012 11:22 PM, Patricia Shanahan wrote:
>
> Please could we concentrate on getting "ill-formed question" defined?
>
> Even if Pathological Self-Reference were defined, it would not close out
> the ill-formed question issue. As I understand, to the limited extent
> that I do understand it, a TM computation does not have to involve
> self-reference, pathological or otherwise, in order to be ill-formed.

I have already exhaustively comprehensively defined ill-formed question
in English completely.
My definition allows any question that can be translated into English to
have a single unambiguous criterion measure to determine whether or not
it is ill-formed.

If by whatever means, the nature of the question prevents a possible
correct answer, then it is an ill-formed question. By applying this
single criterion measure one can divide the universal set of all
questions into ill-formed or not ill-formed.

[Patricia Shanahan]

Then it should only take you a moment to indicate whether a specific
case involves ill-formed questions or not. Please begin with the
questions I already asked.

Thanks,

Patricia

[Ben Bacarisse]

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

> On 3/15/2012 10:00 PM, Ben Bacarisse wrote:
>> Indeed, yet you make this switch often. You slide effortlessly from the
>> "ill-formed" h(m, m) to say that the basic question of halting is
>> ill-formed. It isn't. Not even by the most inclusive reading of this
>> vague term is it ever ill-formed.
> That no Turing Machine can determine halting for every input is not an
> ill-formed statement.
>
> The reason that not every Turing Machine can not determine halting for
> all inputs is that some of these inputs are semantically invalid.

I think you should start by answering Patricia's question. If we can
clear up what you mean by ill-formed there may be some progress.

> I asked you a long time ago what return value could the invocation of
> h(m,m) correctly return and you failed to answer this question too.
> If there really is nothing wrong with the question then why can't you
> answer it?

I have answered it (more than once I think). Do you remember I even
helped you get the construction of m correct? We both know that h(m, m)
can't return the same as halts(m, m) ("halts" being the non-computable
halting function) which is presumably what you mean by "correct" here.
That makes h "wrong" in the sense that it's not a halting decider. If
you want to claim that there's something wrong (ill-formed) about the
input (or the machine + input combination) then please answer Patricia's
questions so that I, too, will know exactly what you mean.

--
Ben.

[Ben Bacarisse]

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

> On 3/15/2012 6:54 PM, Ben Bacarisse wrote:
>> That's hard because I can't always tell how wide a range of meanings you
>> ascribe to your terms, and I am not even sure it's strictly a range.
>> But for starters, when I asked you if you agreed with the statement that
>> every question of the form "machine t halts on input i" has a correct
>> true/false answer you answered both yes and no. That suggests you have
>> at least two widely differing meanings for at least one of the terms,
>> but I am not sure which word or words they are.
> Without Pathological Self-Reference the answer may be yes, otherwise
> it is no.

So is Pathological Self-Reference simply that which makes your assertions
correct? I've seen no clearer definition of it yet.

--
Ben.

[Ben Bacarisse]

Take just one machine t and one input i for which the question "does
machine t halt on input i" does not have a correct {true, false}
answer. What does t do on input i if neither true nor false is a
correct answer to whether it halts?

Its not hard to prove that all Turning, machines runs either halt or
they do not halt, so I can only think that you've been talking all this
time about something other than Turing machines.

--
Ben.

[Ben Bacarisse]

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

> On 3/15/2012 10:34 PM, Ben Bacarisse wrote:
>> It does for what you used to call "self-reference", but I presumably
>> this new property of Pathological Self-Reference is quite different to
>> that. Now all you need to do is (a) define Pathological Self-Reference,
>> (b) prove that it is "detectable", and (c) prove that all other hating
>> instances are decidable.
> This is all obvious from the examples that I have already provided.
> Pathological Self-Reference is self-evidently self reference that
> derives ill-formed questions.

Its not quite the definition I'd hoped for but I think I am starting
to understand it.

> If you try and construct an instance of the Halting Problem that will
> apply to a machine that only detects Pathological Self-Reference and
> does not look at halting, I am pretty sure that you and everyone else
> will continue to only fail.

Sorry, I can't follow this at all, but I don't think that it's important
because of this next remark:

> This machine can not be trapped into Pathological Self-Reference
> because as soon as it sees it, it merely correctly reports true. There
> may be other cases of ill-formed questions besides Pathological
> Self-Reference that prevent halting from being correctly decided.

Yes, I suspect that "ill-formed" is the more important term. Please
return to Patricia's question so that we get pin down what makes a
machine run "ill-formed".

--
Ben.

[Ben Bacarisse]

These ideas, like translation into English, are not unambiguous but,
presumably to help, you gave a definition that applied to the invocation
of a machine on some input string. This form seems to avoid such
notions. Patricia took that definition, gave four cases, and asked you,
the author of the definition, to say which were ill-formed and which
were not. If I recall correctly, you said you'd have to think about two
of them. If the author of a definition has trouble resolving simple
cases, what hope is there for the likes of me?

I think you should resume that thread so that this crucial term can be
pinned down.

--
Ben.

[Joshua Cranmer]

On 3/16/2012 4:25 AM, Peter Olcott wrote:
> On 3/15/2012 9:43 PM, Joshua Cranmer wrote:
>> So, according to your current definitions, your argument reduces to
>> "The Halting problem is correct, if you exclude all the cases where it
>> is wrong." So, obviously, the function ADD(M, w) returning a non-zero
>> value is a correct halting decider, according to your definition. This
>> is the "tautologically useless" interpretation I mentioned above.
>
> "The Halting problem is correct, if you exclude all the cases that are
> themselves incorrect". In other words if you exclude the semantically
> invalid input, the halt decider is always correct.

What makes a case "incorrect"? You attempt to define this as an
"ill-formed question", which context suggests is a slippery definition
for which "the machine cannot provide a correct answer" is not an
incorrect interpretation. But what does it mean to not be able to
provide a correct answer? Again, from context, it seems you make a
distinction between answers which happen to be correct and answers which
are shown to be correct by the algorithm. Under such an interpretation,
any answer that the algorithm gets wrong ought to be excluded as
"semantically invalid", hence the reduction to the tautology "The
halting problem is always right, except for the answers it gets wrong."
That you don't seem to understand why this is not a useful property to
have for your definitions indicates to me that you have some fundamental
gaps in your logic.

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

[Joshua Cranmer]

Am I the only one here to appreciate the (probably unintentional) irony
in this statement?

[Joshua Cranmer]

On 3/16/2012 4:53 PM, Ben Bacarisse wrote:
> I can't say I've spotted the pattern of widening and narrowing, but it
> would certainly explain the feeling of eating Jello-O with chop sticks
> that this discussion gives me.

The "narrowing" step only comes into play when people accuse his
definition of being uselessly wide.

[Joshua Cranmer]

On 3/16/2012 4:18 AM, Peter Olcott wrote:
> On 3/15/2012 9:39 PM, Joshua Cranmer wrote:
>>
>> Do you agree or disagree with the following statement:
>> Whether or not a question (in the sense of a specific instance of any
>> decision problem) is ill-formed is dependent on only the instance in
>> question and does not depend on which computing device is being asked
>> to answer the question.
> That statement is illl-formed because in the case of Pathological
> Self-Reference the specific instance of the question depends upon
> whether or not the computing device being invocated has this
> Pathological Self-Reference or not. If we switch machines between one
> with Pathological Self-Reference and one without Pathological
> Self-Reference then it becomes a different question entirely.

How hard is it to say "I agree" or "I disagree"?

Let me back up a bit and clarify a bit of terminology: when you refer to
a "question", what is the precise mathematical formulation that you are
referring to?

The working definition I am using is as above: a question is a specific
instance of a decision problem; if decision problems are viewed as a set
membership problem, it is a combination of the set which constitutes the
decision problem and the string which we want to know whether or not is
in the set.

If you do not agree with this definition, please give your working
definition in as explicit, precise terminology as above. If you do
agree, please say so by explicitly writing "I agree with this
definition." If you do neither option, I will hound you until you either
give up or you select an option. As there is considerable confusion over
even basic definitions here, it is impossible to try to do any coherent
argumentation before all parties involved can agree on what words
actually mean.

[Ben/Patricia/anyone else following along: if you disagree with this
definition and wish to proffer a better one, feel free to do so.]

> This is completely proven by the fact that in the case of Pathological
> Self-Reference there is no possible correct answer whereas the case of
> no Pathological Self-Reference there is a correct answer.

As far as I can determine, in this sentence, there is one circular
definition, two underdefined terms, and one unproven statement.

[Patricia Shanahan]

To make responding even quicker and easier, here are my questions again:

"The issue is combinations of TM M, a language L defined over M's input
symbols, and a finite string of M's input symbols, X such that you would
consider applying M to decide whether X is in L to be an ill-formed
question."

"For example, suppose M is a TM that always returns false, L is the
language of even length strings, and X is "00". Is the question
ill-formed? Why? Or why not?

Similarly, suppose M is a TM that always returns false, L is the
language of descriptions of TM computations that halt, and X is the TM
computation that runs M on empty input. Is the question ill-formed? Why?
Or why not?"

Patricia

[Peter Olcott]

On 3/16/2012 8:44 AM, Patricia Shanahan wrote:
> If you had a workable, usable definition, anyone would be able to look
> at a couple of questions involving one of the simplest possible TMs, and
> give definitive answers as to whether or not each of them involves an
> ill-formed question.
>
> I was hoping to present a series of successively more subtle questions
> along this line to try to nail down the definition. The fact that I have
> not yet seen answers to even the first two questions in the series is
> disappointing.

If you present a question that requires an enormous learning curve to
comprehend the fact that I can not answer them immediately would not
refute my position.

If the inherent nature of the specific question derives a situation
where no possible correct answer can be provided, then it is an
ill-formed question.

How many feet long is the color of your car?
What is real number square root of -65.2?
(Imaginary numbers not allowed)

What correct return value can the invocation of Halts(M,M) provide?

All of the above are ill-formed questions. I am unfamiliar with any
other Turing Machine instances of ill-formed questions. If by whatever
means another version of the Halting Problem can be created without
using Pathological Self Reference, and this instance by whatever means
makes it impossible for the TM to provide the correct return value
(formally: final accept or reject state) then we have another instance
of an ill-formed question.

[Peter Olcott]

I can not see what is missing from my specification.
Can you tell me in English what in English is missing from this
specification?

[Peter Olcott]

On 3/16/2012 3:00 PM, Ben Bacarisse wrote:
>> "The Halting problem is correct, if you exclude all the cases that are
>> > themselves incorrect". In other words if you exclude the semantically
>> > invalid input, the halt decider is always correct.
> All undecidable sets have decidable subsets, but the part that's
> leftover is, clearly, undecidable. The set, H, of machine/input pairs
> that represents the halting problem can be partitioned into those cases
> that are "semantically invalid" (I) and those that are not (V). I.e.
>
> H = I ∪ V, and I ∩ V = ∅
>
> (I hope you can see the union, intersection and empty set symbols
> there).
>
> Either I or V (or both) is undecidable. No matter how you partition an
> undecidable set, one part of it must remain undecidable.

It would seem that the statement that all undecidable sets have
decidable subsets would have to be incorrect.
The math form of what you said is exactly correct. How did you do the
symbols? (MS Mincho) Every character except the NULL symbol was
completely clear, the NULL symbol was a little too small.

I think that some people with fewer fonts might only see gibberish.

[Patricia Shanahan]

Peter Olcott wrote:
> On 3/16/2012 8:44 AM, Patricia Shanahan wrote:
>> If you had a workable, usable definition, anyone would be able to look
>> at a couple of questions involving one of the simplest possible TMs, and
>> give definitive answers as to whether or not each of them involves an
>> ill-formed question.
>>
>> I was hoping to present a series of successively more subtle questions
>> along this line to try to nail down the definition. The fact that I have
>> not yet seen answers to even the first two questions in the series is
>> disappointing.
> If you present a question that requires an enormous learning curve to
> comprehend the fact that I can not answer them immediately would not
> refute my position.
>

...

Comprehending my questions would require an absolute minimum of basic
knowledge of Turing machines and decidability.

Your inability to answer them proves that one of the following
statements is true:

1. You know nothing about Turing machines and decidability, and are just
stringing words together without the background to make them mean
anything.

[That theory would explain everything about these threads except why you
think you are qualified to make pronouncements about something you know
you have not yet studied and do not understand.]

2. You do not have a workable definition.

Patricia

[Patricia Shanahan]

Peter Olcott wrote:
> On 3/16/2012 3:00 PM, Ben Bacarisse wrote:
>>> "The Halting problem is correct, if you exclude all the cases that are
>>> > themselves incorrect". In other words if you exclude the semantically
>>> > invalid input, the halt decider is always correct.
>> All undecidable sets have decidable subsets, but the part that's
>> leftover is, clearly, undecidable. The set, H, of machine/input pairs
>> that represents the halting problem can be partitioned into those cases
>> that are "semantically invalid" (I) and those that are not (V). I.e.
>>
>> H = I ∪ V, and I ∩ V = ∅
>>
>> (I hope you can see the union, intersection and empty set symbols
>> there).
>>
>> Either I or V (or both) is undecidable. No matter how you partition an
>> undecidable set, one part of it must remain undecidable.
> It would seem that the statement that all undecidable sets have
> decidable subsets would have to be incorrect.

It is easy to show that it is correct. Consider, for example, the empty
set. It is a subset of every set. My current favorite TM, the one that
always returns false, decides it, so it is decidable.

For a larger decidable subset, consider any finite subset of the
undecidable set. All finite sets are decidable - consider a brute-force
TM that just compares its input to the first element of the finite set.
If it matches, return true. If not, test for the second element, etc. If
it gets to the end without matching, return false.

Patricia

[Peter Olcott]

On 3/16/2012 4:05 PM, Patricia Shanahan wrote:
> Consider these two statements:
>
> A: X is the only reason TM halting is undecidable.
>

X is defined as follows:
There are some instances of input to the TM such that providing the
correct return value** from the set of {true,false} is not possible.

** Formally specified as:
The TM will halt in one of two states {accept, reject} such that the
accept state semantically means that the input TM will halt on its input.

> B: X is the only reason a TM that always returns false is not a decider
> for TM halting.
>

A TM that always returns false would be incorrect for all the inputs
that halt on their inputs, X has nothing to do with the reason that this
TM would be incorrect.

> I think Peter would like to find a value of X that gives him an argument
> for A without leading to similar, equally valid or invalid, arguments
> for B.
>
> When we focus on statement A, he tends to broaden the definition of X,
> so that any wrong result from a hypothetical halting decider would
> necessarily involve the current X. When we focus on statements like B,
> he tends to narrow it, for example by requiring self-reference, or even
> "pathological" self-reference, for some undefined value of
> "pathological".
>
> Keeping the definition of X vague, which is much easier in English than
> in mathematical notation, is the only way to make this work.
>
> Patricia

Pathological Self-Reference is a subset of X.

[Ben Bacarisse]

I'll try. What's missing is sufficient precision for you to decide
which, if any, of Patricia's examples are "ill-formed". If you, the
author of it, can't apply it in simple cases the rest of us will surely
be lost.

For reference, the cases were re-posted here:
Message-ID: <TdKdnR200KgioPnS...@earthlink.com>

--
Ben.

[Joshua Cranmer]

On 3/17/2012 8:21 AM, Peter Olcott wrote:
> On 3/16/2012 4:05 PM, Patricia Shanahan wrote:
>> Consider these two statements:
>>
>> A: X is the only reason TM halting is undecidable.
>>
> X is defined as follows:
> There are some instances of input to the TM such that providing the
> correct return value** from the set of {true,false} is not possible.
>
> ** Formally specified as:
> The TM will halt in one of two states {accept, reject} such that the
> accept state semantically means that the input TM will halt on its input.

Can you formally define "semantically means"?

[Peter Olcott]

On 3/16/2012 5:45 PM, Patricia Shanahan wrote:

> On 3/16/2012 2:53 PM, Ben Bacarisse wrote:
>> Patricia Shanahan<pa...@acm.org> writes:
>>
>>> Ben Bacarisse wrote:
>>>> Patricia Shanahan<pa...@acm.org> writes:
>>>>
>>>> <snip>
>>>>> Please could we concentrate on getting "ill-formed question" defined?
>>>>
>>>> Agreed. I'll back off a bit.
>>>>
>>>> I have a feeling, though, that the definition has changed and PSR will
>>>> turn out to be central to the new notion of "ill-defined". I hope
>>>> I am
>>>> wrong, but I suspect that Peter can see that the old definition has no
>>>> value to him, so something new is need.
>>>

>>> Consider these two statements:
>>>
>>> A: X is the only reason TM halting is undecidable.
>>>

>>> B: X is the only reason a TM that always returns false is not a decider
>>> for TM halting.
>>>

>>> I think Peter would like to find a value of X that gives him an
>>> argument
>>> for A without leading to similar, equally valid or invalid, arguments
>>> for B.
>>>
>>> When we focus on statement A, he tends to broaden the definition of X,
>>> so that any wrong result from a hypothetical halting decider would
>>> necessarily involve the current X. When we focus on statements like B,
>>> he tends to narrow it, for example by requiring self-reference, or even
>>> "pathological" self-reference, for some undefined value of
>>> "pathological".
>>>
>>> Keeping the definition of X vague, which is much easier in English than
>>> in mathematical notation, is the only way to make this work.
>>

>> I can't say I've spotted the pattern of widening and narrowing, but it
>> would certainly explain the feeling of eating Jello-O with chop sticks
>> that this discussion gives me.
>>
>

> Incidentally, I don't think this is at all deliberate. It is just that
> Peter seems to believe intensely in halting decidability and is
> searching for anything that will let him keep that belief, despite
> mathematical proof to the contrary.
>
> Patricia
Sorry wrong again on the meaning that I am intending on conveying.
Halting is still undecidable, yet it is only undecidable because of
semantically invalid input.

[Peter Olcott]

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

Neither a machine that always reports true nor a machine that always
reports false ever provides a correct return value to the invocation of
Halts(M,M). The invocation of Halts(M,M) is the question posed to Halts():
"does machine M halt on input M?" and it always gets this wrong.

You *keep* forgetting about Pathological Self-Reference. The question
with PSR is an IFQ, the question without PSR is *not* the same question.
You and Ben keep forgetting that they are *not* the same question.

[Peter Olcott]

On 3/16/2012 9:26 PM, Ben Bacarisse wrote:
>> I asked you a long time ago what return value could the invocation of
>> > h(m,m) correctly return and you failed to answer this question too.
>> > If there really is nothing wrong with the question then why can't you
>> > answer it?
> I have answered it (more than once I think). Do you remember I even
> helped you get the construction of m correct? We both know that h(m, m)
> can't return the same as halts(m, m) ("halts" being the non-computable
> halting function) which is presumably what you mean by "correct" here.
> That makes h "wrong" in the sense that it's not a halting decider. If
> you want to claim that there's something wrong (ill-formed) about the
> input (or the machine + input combination) then please answer Patricia's
> questions so that I, too, will know exactly what you mean.
>
> --

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

Then provide the value that the invocation of Halts(M,M) could correctly
return from the set of {true, false}.
(a) true
(b) false

[Peter Olcott]

Two *different* questions (you keep forgetting this):
(a) A Question *with* Pathological Self-Reference
(b) A Question *without* Pathological Self-Reference

(a) Derives an ill-formed question.
(b) Either derives an ill-formed question not involving Pathological
Self-Reference or it does not derive an ill-formed question.

The fact that (b) does not derive an ill-formed question provides
absolutely no evidence what-so-ever regarding whether or not (a) derives
an ill-formed question.

Why do you keep forgetting this? You already agreed that (a) and (b) are
not the same.

[Peter Olcott]

On 3/16/2012 9:49 PM, Patricia Shanahan wrote:
>> If by whatever means, the nature of the question prevents a possible
>> correct answer, then it is an ill-formed question. By applying this
>> single criterion measure one can divide the universal set of all
>> questions into ill-formed or not ill-formed.
>
> Then it should only take you a moment to indicate whether a specific
> case involves ill-formed questions or not. Please begin with the
> questions I already asked.
>
> Thanks,
>
> Patricia

I am currently lacking the prerequisite knowledge to sufficiently
understand this question.
If you understand it, then simply apply my criterion measure and answer
it for yourself.

[Peter Olcott]

On 3/16/2012 10:57 PM, Joshua Cranmer wrote:
> What makes a case "incorrect"? You attempt to define this as an
> "ill-formed question", which context suggests is a slippery definition
> for which "the machine cannot provide a correct answer" is not an
> incorrect interpretation. But what does it mean to not be able to
> provide a correct answer?

Maybe (just maybe I, could be wrong) but it might possibly be the case
that a halt decider that decides that a TM will halt on its input and
itself halts in its own accept state and when its input is a TM that
will not halt on its input, this TM will halt in its own reject state.

Who knows, maybe *correct* behavior was really for the TM halt decider
to make toast and strawberry jam?

[Peter Olcott]

On 3/16/2012 11:02 PM, Joshua Cranmer wrote:
>> The way that most people have beliefs is typically with emotional
>> attachment of some degree, with current working hypotheses subject to
>> future revision as more information becomes available there typically is
>> no such emotional attachment.
>
> Am I the only one here to appreciate the (probably unintentional)
> irony in this statement?

Do you merely believe that existence exists, or do you comprehend that
even asking this question conclusively proves the resulting answer by
the meaning of the words? Could it possibly be that existence does not
exist right now, or is this 100% completely impossible?

[Peter Olcott]

I think that I may be able to understand these questions well enough to
respond to them.
I just printed them out for further study.

I am taking a wild guess that this might be an example of Rice's
Theorem. If it is an example of Rice's Theorem then it is entirely
appropriate to ask me to apply the reasoning that I am proposing to
Rice's Theorem.

In any case, I will be moving in the direction of showing how my
reasoning applies to Rice's Theorem. It will take me at least a little
while to sufficiently understand Rice's Theorem. My copy of Kozen is at
the office. I will at least briefly look at other resources.

[Peter Olcott]

On 3/17/2012 7:34 AM, Patricia Shanahan wrote:
>>> All undecidable sets have decidable subsets, but the part that's
>>> leftover is, clearly, undecidable. The set, H, of machine/input pairs
>>> that represents the halting problem can be partitioned into those cases
>>> that are "semantically invalid" (I) and those that are not (V). I.e.
>>>
>>> H = I ∪ V, and I ∩ V = ∅
>>>
>>> (I hope you can see the union, intersection and empty set symbols
>>> there).
>>>
>>> Either I or V (or both) is undecidable. No matter how you partition an
>>> undecidable set, one part of it must remain undecidable.
>> It would seem that the statement that all undecidable sets have
>> decidable subsets would have to be incorrect.
>
> It is easy to show that it is correct. Consider, for example, the empty
> set. It is a subset of every set. My current favorite TM, the one that
> always returns false, decides it, so it is decidable.
>
> For a larger decidable subset, consider any finite subset of the
> undecidable set. All finite sets are decidable - consider a brute-force
> TM that just compares its input to the first element of the finite set.
> If it matches, return true. If not, test for the second element, etc. If
> it gets to the end without matching, return false.
>
> Patricia

Quote from above: "undecidable sets have decidable subsets"

If decidable and undecidable are mutually exclusive properties of a set,
then it would be impossible for there to be any intersection between
these sets.

[Peter Olcott]

On 3/17/2012 9:00 AM, Ben Bacarisse wrote:
>> I can not see what is missing from my specification.
>> > Can you tell me in English what in English is missing from this
>> > specification?
> I'll try. What's missing is sufficient precision for you to decide
> which, if any, of Patricia's examples are "ill-formed". If you, the
> author of it, can't apply it in simple cases the rest of us will surely
> be lost.

I think that I can do this. I will try. It seems like a reasonable request.

[Peter Olcott]

On 3/17/2012 9:14 AM, Joshua Cranmer wrote:
> On 3/17/2012 8:21 AM, Peter Olcott wrote:
>> On 3/16/2012 4:05 PM, Patricia Shanahan wrote:
>>> Consider these two statements:
>>>
>>> A: X is the only reason TM halting is undecidable.
>>>
>> X is defined as follows:
>> There are some instances of input to the TM such that providing the
>> correct return value** from the set of {true,false} is not possible.
>>
>> ** Formally specified as:
>> The TM will halt in one of two states {accept, reject} such that the
>> accept state semantically means that the input TM will halt on its
>> input.
>
> Can you formally define "semantically means"?
>

In this instance the accept state of the TM mathematically maps to the
conception {the input TM will halt on its input} . Semantics is all
about the mathematical mapping between word-labels and sets of conceptions.

In the ideal case the conceptions have been specified in a purified form
a natural language that has every detail of every word completely,
correctly, consistently specified in something like an ISO standard
dictionary of English.

To make sure that this specification is complete it is represented in a
form such that a machine can attain complete comprehension of every
word. By complete comprehension I refer to comprehension that at least
matches the most knowledgeable person of each subject in every field,
and no person on Earth has any more comprehension of any subject that is
greater than that of this machine.

I have named such a language Lucid.

[Patricia Shanahan]

I understand the questions. My problem is that your specification makes
no sense to me, so I cannot apply it. Given your admission that you do
not have even a very basic understanding of Turing machines or
decidability, that is most likely to be because it is nonsense.

If and when you have learned enough to understand my questions, and in
the unlikely event that your specification still makes sense to you
after you have that knowledge, I'll be interested in your answers.

Patricia

[Ben Bacarisse]

That just does not follow. Try it with another property a set, one you
don't have misconceptions of: every infinite set has finite subsets.

Decidability is a property of sets not of their elements.

--
Ben.

[Ben Bacarisse]

You've switch question again. I was talking about each and every
question of the form "does machine t halt on input i". Your reply is
about quite another question.

The question "does machine M halt on input M?" has a correct true/false
answer -- there is simply no other possibility. We can't say which
because we don't know exactly what machine M is, but it certainly either
halts or it does not halt (this is true no matter what the input is).
What's more, lots of machines get the answer right. In particular, one
of the two trivial machines I descried gets it right.

You've confused what one machine can do (Halts in your example) with
what other machines can do.

I think the core of your trouble is this. Having cunningly constructed
M to show that Halts can't be a halting decider, -- i.e. that Halts(M,
M) can't be the correct answer as to whether M halts on input M, you
leap, incorrectly, to thinking that this question itself does not have a
correct answer.

> You *keep* forgetting about Pathological Self-Reference. The question
> with PSR is an IFQ, the question without PSR is *not* the same
> question. You and Ben keep forgetting that they are *not* the same
> question.

Hey, yes! There are two questions and you replied to mine by bringing
up another.

--
Ben.

[Ben Bacarisse]

What part of my answer was unclear? Because you don't define things (in
particular "correct"), I have to do it myself. This makes my answers
longer than you'd like. M(M) either halts or it does not. If by
"correct" you mean that Halt(M, M) must return which ever of these is
the case, then it can't. Which ever is the case (M(M) either halting or
not) Halts(M, M) gets the answer wrong.

I don't see why you are so hung up on this. We agree about it. This
case, where Halts is doomed to be wrong, is what you want to call an
ill-formed question. That's fine, go ahead. But it's not a useful term
unless it can be applied more widely because there are lots of machines
that can "fool" Halts that don't look like M above. This is why you
should answer Patricia's questions about what ill-formed really means.

Sadly, I note that you've replied that message without answering the
question, though you do say that now know enough to do so. I hope you
do answer it soon.

--
Ben.

[Ben Bacarisse]

This answer is unresponsive. What third possibility is there? For each
machine t and input i, t either halts on input i or it does not. (this
is easy to prove, by the way, -- it follows quite simply from the
definition of the execution of a Turing machine.) If you won't accept
this, you are not talking about the halting problem.

If can accept the truth of this, we are least talking about the same
problem. If you can't, can you define what it is you mean when you talk
about a halting decider?

--
Ben.

[Peter Olcott]

If you ask does a Turing Machine halt on its input THIS IS NOT ONE
QUESTION IT IS TWO.

[Peter Olcott]

The part where you never get around to choosing (a) or (b)

[Peter Olcott]

My reply is *ALWAYS* about this question you keep trying to change the
subject.

[Ben Bacarisse]

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

> On 3/17/2012 3:28 PM, Ben Bacarisse wrote:
>> Peter Olcott<NoS...@OCR4Screen.com> writes:

<snip>

>>> > M( String Input )
>>> > {
>>> > if ( Halts( Input, Input ) )
>>> > Loop Forever;
>>> > else
>>> > Exit;
>>> > }
>>> >
>>> > Then provide the value that the invocation of Halts(M,M) could
>>> > correctly return from the set of {true, false}.
>>> > (a) true
>>> > (b) false
>> What part of my answer was unclear?
> The part where you never get around to choosing (a) or (b)

What are you? 12? I was perfectly clear, and, what's more, my answer
was just the one you want. Nothing about it prevents you making your
claim about the "question" being ill-formed. However, I won't play your
silly games.

--
Ben.

[Peter Olcott]

On 3/17/2012 2:31 AM, Patricia Shanahan wrote:

> On 3/16/2012 7:49 PM, Patricia Shanahan wrote:
>> Peter Olcott wrote:

>>> On 3/15/2012 11:22 PM, Patricia Shanahan wrote:
>>>>
>>>> Please could we concentrate on getting "ill-formed question" defined?
>>>>
>>>> Even if Pathological Self-Reference were defined, it would not
>>>> close out
>>>> the ill-formed question issue. As I understand, to the limited extent
>>>> that I do understand it, a TM computation does not have to involve
>>>> self-reference, pathological or otherwise, in order to be ill-formed.
>>> I have already exhaustively comprehensively defined ill-formed
>>> question in English completely.
>>> My definition allows any question that can be translated into English
>>> to have a single unambiguous criterion measure to determine whether or
>>> not it is ill-formed.
>>>

>>> If by whatever means, the nature of the question prevents a possible
>>> correct answer, then it is an ill-formed question. By applying this
>>> single criterion measure one can divide the universal set of all
>>> questions into ill-formed or not ill-formed.
>>
>> Then it should only take you a moment to indicate whether a specific
>> case involves ill-formed questions or not. Please begin with the
>> questions I already asked.
>

> To make responding even quicker and easier, here are my questions again:
>
> "The issue is combinations of TM M, a language L defined over M's input
> symbols, and a finite string of M's input symbols, X such that you would
> consider applying M to decide whether X is in L to be an ill-formed
> question."
>
> "For example, suppose M is a TM that always returns false, L is the
> language of even length strings, and X is "00". Is the question
> ill-formed? Why? Or why not?
>
> Similarly, suppose M is a TM that always returns false, L is the
> language of descriptions of TM computations that halt, and X is the TM
> computation that runs M on empty input. Is the question ill-formed? Why?
> Or why not?"
>
> Patricia
>
>
>

It makes no sense trying to evaluate whether or not an ill-formed
question exists when it is given that the TM is constructed to make sure
that it sometimes gets the wrong answer.

The first paragraph by itself is not ill-formed as it is specified.

Dexter Kozen
Automata and Computability 1997
Lecture 32
Pages 235-238
Decidable and Undecidable Problems
It is undecidable whether or not a Turing Machine accepts
(f) The NULL string.

[Ben Bacarisse]

We must stop this particular exchange here because I can't see any way
to make this rather simple int any clearer.

--
Ben.

[Ben Bacarisse]

Can you, then, please define the problem you've been talking about? The
one *I* thought we'd been discussing does not have this property. The
classical halting problem is whether there is a decider for the set of
strings the represent machine/input pairs, such that the machine halts
(in a finite number of steps) when run with the given input.

--
Ben.

[Patricia Shanahan]

On 3/17/2012 3:17 PM, Peter Olcott wrote:
...

> It makes no sense trying to evaluate whether or not an ill-formed
> question exists when it is given that the TM is constructed to make sure
> that it sometimes gets the wrong answer.

We know that *all* Turing machines at least sometimes get wrong answers
when used as halting deciders. I thought your "ill-formed question" idea
was all about how to interpret wrong answers - that somehow a wrong
answer does not really count in some cases, because you classify the
question as ill-formed.

I was trying to find out the rules for when you would classify a wrong
answer as indicating an ill-formed question.

Do you think I could find out about that by asking about TMs that always
get the right answer? Or maybe you think I should have chosen random TMs
and just hoped there would be some interesting wrong answer cases?

> The first paragraph by itself is not ill-formed as it is specified.
>
> Dexter Kozen
> Automata and Computability 1997
> Lecture 32
> Pages 235-238
> Decidable and Undecidable Problems
> It is undecidable whether or not a Turing Machine accepts
> (f) The NULL string.
>

If you think that is relevant to questions about interpretation of
results of an individual, easily analyzed, Turing machine, you really
need to spend a bit more time studying.

Patricia

[Peter Olcott]

On 3/17/2012 8:50 PM, Patricia Shanahan wrote:
> On 3/17/2012 3:17 PM, Peter Olcott wrote:
> ...
>> It makes no sense trying to evaluate whether or not an ill-formed
>> question exists when it is given that the TM is constructed to make sure
>> that it sometimes gets the wrong answer.
>
> We know that *all* Turing machines at least sometimes get wrong answers
> when used as halting deciders. I thought your "ill-formed question" idea
> was all about how to interpret wrong answers - that somehow a wrong
> answer does not really count in some cases, because you classify the
> question as ill-formed.
>
> I was trying to find out the rules for when you would classify a wrong
> answer as indicating an ill-formed question.
>
> Do you think I could find out about that by asking about TMs that always
> get the right answer? Or maybe you think I should have chosen random TMs
> and just hoped there would be some interesting wrong answer cases?

This is not at all what I have been saying. The idea is to screen out
the invalid input so that all the answers are correct, and the invalid
input is rejected. Or simpler still don't produce the artificially
contrived invalid input in the first place.

[Ben Bacarisse]

Apart from using a different perspective, I can't see a lot of
difference between your words and Patricia's, but no matter. Taking
your description of what you are doing, it's clearly crucial to pin down
what these invalid input cases are. A closely related question is
whether you think these cases can be detected by a machine, i.e. whether
the set of invalid machine+input strings is, itself, decidable.

You accept (and have stated more than once now) that halting is not
decidable. Once invalid inputs have been screened out, there remains a
new set (i.e. a new problem) where "all the answer are correct". Do you
mean to say that you believe this new set to be decidable?

There can be no greater priority (for you) than to specify these invalid
input cases in such away that you, at least, can say (and, ideally,
prove) whether the set they form is decidable and if the set that
remains after they are removed from the set of all machine+input
strings is decidable.

--
Ben.

[Peter Olcott]

yes.

> There can be no greater priority (for you) than to specify these invalid
> input cases in such away that you, at least, can say (and, ideally,
> prove) whether the set they form is decidable and if the set that
> remains after they are removed from the set of all machine+input
> strings is decidable.
>

Another TM named InvalidInput() filters the input to Halts() such that
Halts() never sees semantically invalid input.

if (InvalidInput(Halts, M, M)
return true;
else
Halts(M,M); // different set of final states

As far as I can tell this is the one decider that can't be fooled by
Pathological Self-Reference or any other kind of invalid input (semantic
or otherwise).

I don't know if it is possible to prove that the InvalidInput() decider
always works, it might simply be the case that no one ever derives proof
that it does always not work.

Since I am unaware of any Turing Machine related instances of ill-formed
question besides Pathological Self-Reference, thus this might be the
best place to begin:

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

Can anyone provide a single valid counter-example showing that the
invocation of of (InvalidInput(Halts, M, M) is not a decider? (feel free
to modify M to make your point).

[Joshua Cranmer]

On 3/17/2012 2:32 PM, Peter Olcott wrote:
> On 3/17/2012 9:14 AM, Joshua Cranmer wrote:
>> On 3/17/2012 8:21 AM, Peter Olcott wrote:
>>> On 3/16/2012 4:05 PM, Patricia Shanahan wrote:
>>>> Consider these two statements:
>>>>
>>>> A: X is the only reason TM halting is undecidable.
>>>>
>>> X is defined as follows:
>>> There are some instances of input to the TM such that providing the
>>> correct return value** from the set of {true,false} is not possible.
>>>
>>> ** Formally specified as:
>>> The TM will halt in one of two states {accept, reject} such that the
>>> accept state semantically means that the input TM will halt on its
>>> input.
>>
>> Can you formally define "semantically means"?
>>
>
> In this instance the accept state of the TM mathematically maps to the
> conception {the input TM will halt on its input} . Semantics is all
> about the mathematical mapping between word-labels and sets of conceptions.

You have the most informal notion of formality I have seen in quite some
time. This is still rather unclear: do you mean this property holds for
every input to the TM or for any input?

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

[Peter Olcott]

What difference are you intending between "every input" and "any input"?
(These seem to be semantically identical) I would simply call these the
universal set of all input X.

There exists elements in set X such that neither element of the set
{true,false} provides a correct return value to the invocation of
Halts(M,M).

I think that I can get a little more formal on the concept of correct
return value.
{true} mathematically maps to the input TM halting in either its accept
state or its reject state.
{false} mathematically maps to the input TM looping on its input.

I don't know of any way that we can formally define exactly what the
term halt means.
Although we can say that it means there is a state transition from some
internal state to some final state, we now have to define what this
means, on and on recursively such that the complete specification can
not be feasibly provided concisely.

Since every word is defined in terms of many other words, exhaustively
defining most words requires a degree of knowledge representation (KR)
that has not yet been sufficiently fully elaborated.

[Patricia Shanahan]

Also, one reminder. The response to my question about the machine that
always returns false as a decider for even length strings shows that it
is possible for a TM to get an answer wrong even in the absence of an
ill-formed question.

We don't know whether there is any TM that reports correctly whether a
TM computation halts in all cases that are not ill-formed questions for
that TM.

Patricia