halting problem proof analysis
Matthias Blume
> In article <aqd4nb$8v0$1...@news01.cit.cornell.edu>,
> Cagdas Ozgenc <co19@map's'pam.cornell.edu> wrote:
> >But the ultimate conclusion is the following: "a
> >machine cannot decide its own halting problem".
>
> Whoever is telling you that this is supposed to be the ultimate conclusion
> is mistaken. The proof certainly doesn't show that a machine can't decide
> its own halting problem. For example, consider the following class C of
> machines: The class contains only one element, namely the machine that
> always outputs "yes," and then halts. The machine in this class successfully
> decides the halting problem for all machines in the class C.
Indeed. The Halting Problem is undecidable for (at least) those
classes C of machines that have all the necessary ingredients for making
the usual diagonalization proof work. This means:
- there is a universal function U for C in C
- C is closed under certain simple operations such as
"take M and construct an M' that reports the opposite of M",
"take binary M and construct a unary M' so that M'(x) = M(x,x)",
etc.
With this the diagonalization proof goes like this:
- Assume the Halting Problem for C is decidable, i.e.,
\exists H such that H(i,x) = 1 iff U(i,x) halts
H(i,x) = 0 otherwise
- construct
F(x) = if H(x,x) = 1 then U(x,x) + 1 else 0
(I am assuming that C is closed wrt. the if-then-else construct,
the operation of supplying the same value to both arguments of a binary
function, adding 1, ...)
- take f so that F(x) = U(f,x) forall x (must exist because F is in C
and U is universal for C)
- consider F(f):
F(f) = if H(f,f) = 1 then U(f,f) + 1 else 0
= if H(f,f) = 1 then F(f) + 1 else 0
Now, if H(f,f) = 1 then
F(f) = F(f) + 1 -- contradiction
or, if H(f,f) = 0 then
F(f) = 0 -- contradiction because H now mispredicts whether
F halts on f or not
As Tim pointed out via example, not all classes C of machines have all
the necessary properties to make this construction go through. But for
those that do, the corresponding Halting Problem /is/ undecidable.
There might also be other classes of machines where the Halting Problem
is undecidable but which require a different style of proof for this fact.
--
-Matthias
Cagdas Ozgenc
> As Tim pointed out via example, not all classes C of machines have all
> the necessary properties to make this construction go through. But for
> those that do, the corresponding Halting Problem /is/ undecidable.
> There might also be other classes of machines where the Halting Problem
> is undecidable but which require a different style of proof for this fact.
Yes. Any interesting machine will have the necessary properties as Godel
points out. For some reason Tim always wants to astray from the essence of
the topic.
Cagdas Ozgenc
<tc...@lsa.umich.edu> wrote in message news:aqdmv6$jtu$1...@galois.mit.edu...
> In article <aqe286$cdc$1...@news01.cit.cornell.edu>,> >The proof of the halting problem tells us the following: "A system cannot
> >decide its own halting problem if the system is decent".
>
> I think we agree that the proof (call it P) that the halting problem (for
> TM's) is undecidable (by TM's) *as it currently stands* does not show that
> "a system cannot decide its own halting problem if the system is decent"
> (call this claim S).
Sure. I am not interested about the proof of halting problem for TMs. Claim
S is Godel's claim not mine. In the meantime decency is subjective, I agree.
> I gather that your feeling is that P can be *generalized* to prove S.
> It's certainly true, as someone else on this thread has pointed out,
> that P can be generalized to classes of machines other than the class
> of TM's. Whether these generalizations prove S---well, that's a matter
> of opinion, because it depends on what "decent" means. I can declare
Maybe one can come up with some decency axioms, like the other fellow
pointed out.
> that anything other than TM's are indecent, and then P *does* prove S.
Well at least when saying "other than TMs" you should also exclude models
with equal power to TMs, because they are at equal decency.
> Conversely, if *everything* is decent, then S is false. It looks like
> you're going through the exercise of trying to determine just how weak
> a condition one can place on the system without breaking the proof.
> That's not a bad exercise to go through, as long as you don't annoy
> people along the way by claiming that there are errors or gaps in certain
> proofs, when the reality is that they prove just fine what they're
> *claiming* to prove. Just because they don't prove what you *want*
> them to prove isn't their fault.
I am trying to analyze the proof in detail (as you said it is an exercise),
and learn more from it that is all. I have no intensions of trying to
invalidate the proof or annoy anyone. If you find digging up computation
theory, or not being a slave of existing books on theory annoying them
simply not contribute in the discussion. Other than that I apologize if you
are annoyed or offended.
> If you're hoping that P can be generalized to prove that no machine
> that can be *physically built* can ever solve the halting problem for
> all machines that can be physically built, then you're out of luck.
> As we discussed, physical claims aren't decidable by pure logic. You
> will have to introduce some non-mathematical principle like the Church-
> Turing thesis.
You had provided good insights regarding that matter. I will try to come up
with my own precise restrictions (or decency axioms). My intension is not to
provide a more powerful machine than a TM, as I said before. The idea that I
would like to pursue is whether HP is undecidable within the limitations
that I put forward, which will rest my soul and believe that it is the limit
of computation.
Matthias Blume
Wrong. There are *very* interesting machine models that do not have
the necessary properties. Examples are finite-state machines,
primitive recursive functions, or the second-order typed lambda
calculus (which, unlike primitive recursive functions, /can/ express
the Ackermann function while still being strongly normalizing -- which
means that all programs eventually halt).
--
-Matthias
tc...@lsa.umich.edu
one or two remarks:
In article <aqe7bf$m32$1...@news01.cit.cornell.edu>,
>Sure. I am not interested about the proof of halting problem for TMs. Claim
>S is Godel's claim not mine. In the meantime decency is subjective, I agree.
Claim S is certainly *not* Goedel's claim, even given generous leeway for
sloppy statement. The undecidability of the halting problem is due to
Turing, and postdates Goedel's work by a long time. The two theorems
are closely related but definitely distinct.
>I am trying to analyze the proof in detail (as you said it is an exercise),
>and learn more from it that is all. I have no intensions of trying to
>invalidate the proof or annoy anyone. If you find digging up computation
>theory, or not being a slave of existing books on theory annoying them
>simply not contribute in the discussion. Other than that I apologize if you
>are annoyed or offended.
I was not annoyed or offended, nor do I think anyone was necessarily
annoyed by what you said. I was just warning you to be wary of how you
say things lest you annoy people. Note that there was at least one other
person (not me) on this thread who had the impression that you were not
really listening to what others on this thread were trying to tell you,
so be careful about accusing people of not listening to you or missing
the point until you're sure that *you* are listening to others and are
not missing the point yourself.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
David Wagner
><tc...@lsa.umich.edu> wrote in message news:aqdfqq$hu4$1...@galois.mit.edu...
>> Cagdas Ozgenc <co19@map's'pam.cornell.edu> wrote:
>> >But the ultimate conclusion is the following: "a
>> >machine cannot decide its own halting problem".
>>
>> Whoever is telling you that this is supposed to be the ultimate conclusion
>> is mistaken.
>
>the proof of halting problem.
Not to put too fine a point on it, but your interpretation is wrong,
or at least, incomplete, as others have pointed out. Maybe what you
wrote is not what you intended.
David Wagner
>> you're going through the exercise of trying to determine just how weak
>> a condition one can place on the system without breaking the proof.
>> That's not a bad exercise to go through, as long as you don't annoy
>> people along the way by claiming that there are errors or gaps in certain
>> proofs, when the reality is that they prove just fine what they're
>> *claiming* to prove. Just because they don't prove what you *want*
>> them to prove isn't their fault.
>
>I am trying to analyze the proof in detail (as you said it is an exercise),
>and learn more from it that is all.
That would be fine if it were true, but you were previously making claims
that were false. In the future, you might get a more positive response
through studying and asking questions rather than making pronouncements.
And it would be more polite to put some effort into studying the material
first on your own, before posting here asking for help; otherwise,
some readers might rightly feel that you are wasting their time.
Michael N. Christoff
"Cagdas Ozgenc" <co19@map's'pam.cornell.edu> wrote in message
news:aqe5b3$j6o$1...@news01.cit.cornell.edu...
What Goedel meant by "interesting" is that any axiomatic system that was at
least as powerful as the Peano postulates of arithmetic would be incomplete.
That is what Goedel meant by "interesting" or "decent".
l8r, Mike N. Christoff
Cagdas Ozgenc
"Michael N. Christoff" <mchri...@MAPSONsympatico.ca> wrote in message
news:JpLy9.12011$3e2.1...@news20.bellglobal.com...
Sure. My whole point on this discussion was to bring different point of view
to what Godel, or Turing claimed, not to repeat them. Godel certainly did
not say what I wrote, I just would like to interpret Godel from Turing point
of view, and Turing from Godel point of view.
Cagdas Ozgenc
> That would be fine if it were true, but you were previously making claims
> that were false. In the future, you might get a more positive response
> through studying and asking questions rather than making pronouncements.
> And it would be more polite to put some effort into studying the material
> first on your own, before posting here asking for help; otherwise,
You haven't provided any useful insight to the discussion other than
criticizing me. Simply don't contribute if you don't like. I don't remember
responding to any of your posts. What's the ego problem?
Nick Maclaren
In article <fo65v9z...@trex9.cs.bell-labs.com>,
Matthias Blume <matt...@shimizu-blume.com> writes:
|>
|> As Tim pointed out via example, not all classes C of machines have all
|> the necessary properties to make this construction go through. But for
|> those that do, the corresponding Halting Problem /is/ undecidable.
|> There might also be other classes of machines where the Halting Problem
|> is undecidable but which require a different style of proof for this fact.
And there might even be classes of machines that are NOT subject
to the Goedel/Turing limits!
For example, the diagonalisation proof fails horribly for any
machine which can support an uncountable number of programs. Now,
I can produce a couple of examples, but am completely out of my
depth when coming to analyse them. They might still be subject
to the Goedel/Turing limits, they might be inconsistent, or
anything.
A simple example is one where each 'cell' of the Turing machine
may hold a (general) real number, and there are a reasonable
number of the usual operations available. You obviously can't
diagonalise, and equally obviously can't create even a 'finite'
general program using a standard Turing machine.
What properties does that have? I don't have a clue :-)
Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QH, England.
Email: nm...@cam.ac.uk
Tel.: +44 1223 334761 Fax: +44 1223 334679
tc...@lsa.umich.edu
Nick Maclaren <nm...@cus.cam.ac.uk> wrote:
>A simple example is one where each 'cell' of the Turing machine
>may hold a (general) real number, and there are a reasonable
>number of the usual operations available. You obviously can't
>diagonalise, and equally obviously can't create even a 'finite'
>general program using a standard Turing machine.
>
>What properties does that have? I don't have a clue :-)
What you're describing is very similar, if not identical, to what often
goes by the name of "models of real computation." A prominent example,
though not the only one, is the one described in the book _Complexity_
_and_Real_Computation_ by Blum, Cucker, Shub, and Smale. An amusing
application of this theory is the ability to make precise the statement
that "the Mandelbrot set is undecidable."
I recall that you have expressed doubts about the competence of some of
the people who have worked in this area. Perhaps the fact that Smale is
one of the authors may allay your suspicions.
Nick Maclaren
In article <aqgaf5$1eu$1...@galois.mit.edu>, tc...@lsa.umich.edu writes:
|>
|> What you're describing is very similar, if not identical, to what often
|> goes by the name of "models of real computation." A prominent example,
|> though not the only one, is the one described in the book _Complexity_
|> _and_Real_Computation_ by Blum, Cucker, Shub, and Smale. An amusing
|> application of this theory is the ability to make precise the statement
|> that "the Mandelbrot set is undecidable."
|>
|> I recall that you have expressed doubts about the competence of some of
|> the people who have worked in this area. Perhaps the fact that Smale is
|> one of the authors may allay your suspicions.
In this case, the person who isn't competent to follow the
mathematics is me! I can often spot complete nonsense, such
as applying discrete results regardless, but that is unlikely
to be the case with those authors!
Working on complex systems over uncountable sets is thoroughly
unintuitive and full of traps, and I know just about enough to
know that I can't handle it in general.
Bryan Olson
Cagdas Ozgenc wrote:
> Dave Wagner wrote:
>>That would be fine if it were true, but you were previously making claims
>
> You haven't provided any useful insight to the discussion other than
> criticizing me. Simply don't contribute if you don't like. I don't
remember
> responding to any of your posts. What's the ego problem?
The problem is that there's no doubt who understands and who does
not. Tim Chow's posts have been excellent. You act as if he
brushes off your posts without really understanding what you are
saying. Exactly the opposite is the case.
--
--Bryan
Casey Hawthorne
1-tape TM?
Although a TM on a 2D grid or a TM with multiple read/write heads
represents no increase in power over a 1-tape TM: wouldn't the above
TM represent something similar to the concepts between aleph-null and
aleph-one?
>A simple example is one where each 'cell' of the Turing machine
>may hold a (general) real number, and there are a reasonable
>number of the usual operations available. You obviously can't
>diagonalise, and equally obviously can't create even a 'finite'
>general program using a standard Turing machine.
>
>What properties does that have? I don't have a clue :-)
>
>Regards,
>Nick Maclaren,
>University of Cambridge Computing Service,
>New Museums Site, Pembroke Street, Cambridge CB2 3QH, England.
>Email: nm...@cam.ac.uk
>Tel.: +44 1223 334761 Fax: +44 1223 334679
Regards,
Casey
Cagdas Ozgenc
> The problem is that there's no doubt who understands and who does
> not. Tim Chow's posts have been excellent. You act as if he
> brushes off your posts without really understanding what you are
> saying. Exactly the opposite is the case.
Any you happen to be Tim's lawyer? I think he can settle down himself if he
has a personal problem with me. You are simply insulting Tim as if he is not
capable of defending himself. Neither we have a problem with Tim, nor he is
in need of defending himself.
Nick Maclaren
Casey Hawthorne <cas...@istar.ca> wrote:
>Wouldn't this be like a 1-tape TM where each cell also represents a
>1-tape TM?
>
>Although a TM on a 2D grid or a TM with multiple read/write heads
>represents no increase in power over a 1-tape TM: wouldn't the above
>TM represent something similar to the concepts between aleph-null and
>aleph-one?
Yes and no. Commutativity again. If you use that model, and limit
each of those machines to performing one operation at each step,
then you have merely squared Aleph-0, and still have Aleph-0. If
I recall, such a system is the closest that you can get to a real
(physical) realisation of an NDTM - I vaguely remember convincing
myself that they were mathematically similar.
You then have to work out what on earth the rules for binding the
machines together should be, which is where the problems arise.
If you require each cell to be able to run its program to completion
in a fixed time, then you have an entirely different scenario. No,
I have no ideas what properties that would have.
Nick Maclaren
Enough is enough.
No, that is NOT so. Let's leave Tim Chow out of it, as he has been
posting reasonably - it is some of the other posts where I feel that
Cagdas Ozgenc is being unreasonably attacked. I shall not name names,
but could.
Cagdas Ozgenc's postings have been very confusing, yes, but I have
NEVER read them to say what many people are claiming that he is saying.
And he has always said that such claimed statements were not what he
meant. Well, I for one believe him. No, I am not entirely sure what
he is asking, though I have the glimmering of an idea, and I think
that he is attempting to ask some serious questions.
It isn't unreasonable for people to post a "playpit level" response
to seriously confused postings, but it is unjustified to attack the
poster when he attempts to say that what he is trying to ask is more
complicated. I have no idea whether he is fundamentally confused or
merely having difficulty expressing himself, but he seems to be doing
his honest best to explain his points.
This newsgroup (and others) would be a lot better off if more people
would allow for honestly misphrased postings and try to work out what
the poster really meant (or just ask him!), rather than looking for
weaknesses in the wording to score cheap points off. It is nearly
as bad as Prime Minister's Question Time, for heaven's sake!
Bryan Olson
> [...] I just would like to interpret Godel from Turing point
> of view, and Turing from Godel point of view.
Then I can suggest some questions you might look into:
Does there exist a Turing machine that accepts the set of theorems
of formal number theory? Does there exist one that decides this
set?
Is number theory powerful enough to Godel-number Turing machines
and their configurations, and describe the transitions as
operations on such numbers? Can we write the halting problem as a
property of the Godel numbers? Are turning machines powerful
enough to automatically perform the Godel-numbering?
If so, suppose we attempt to solve the halting problem by building
a Turing machine that Godel-numbers the machine described in the
input, and writes the assertion that it reaches the halt state as
a proposition of formal number theory. Next the machine
enumerates all the theorems until it finds either this assertion
or its negation. Why does this solution fail?
Can a Turing machine take a proposition of number theory and
search for counterexamples? If the proposition is neither a
theorem nor contradicted by a theorem, will the search halt? Could
another machine determine in general whether such searches halt?
--
--Bryan
David Wagner
>This newsgroup (and others) would be a lot better off if more people
If it's a case of a honest misphrasing, that's one thing.
If it's a case of someone who hasn't even read the proof of the
undecidability of the halting problem before making wild claims about
undecidability, that's a little different.
For the latter, the best thing we can do is encourage people to
put in a little effort to study the field on their own before posting
such wild claims about where the conventional wisdom has gone wrong.
It's only polite for the poster to put in a little time on his own
before asking the readers here to teach the subject to him.
Bryan Olson
>>The problem is that there's no doubt who understands and who does
>>not. Tim Chow's posts have been excellent. You act as if he
>>brushes off your posts without really understanding what you are
>>saying. Exactly the opposite is the case.
>
>
> Any you happen to be Tim's lawyer?
No, I'm a cryptographer by trade, and like you I'm a Usenet
participant. Clear?
> I think he can settle down himself if he
> has a personal problem with me. You are simply insulting Tim as if he
is not
> capable of defending himself. Neither we have a problem with Tim, nor
he is
> in need of defending himself.
Then you missed what I was saying. Tim's posts have been
excellent. If you doubt his claims, you can check them out in the
usual theory texts. He may or may not continue to work on
bringing you to an understanding of the issues. There's no need
for him to "defend" anything.
One final remark: wrong posts will, and should, draw negative
comments. At first, responders should simply point out the
problems. Then the original author should look into the matter
and make the corrections. If he repeatedly fails to do so, then
there is nothing inappropriate about other writers telling him how
things are. Dave Wagner's post was about appropriate issues. I
believe my post was about appropriate issues. Your remark: "Any
you happen to be Tim's lawyer?", is a invalid personal attack.
--
--Bryan
Nick Maclaren
David Wagner <d...@mozart.cs.berkeley.edu> wrote:
>Nick Maclaren wrote:
>>This newsgroup (and others) would be a lot better off if more people
>>would allow for honestly misphrased postings [...]
>
>If it's a case of a honest misphrasing, that's one thing.
>
>If it's a case of someone who hasn't even read the proof of the
>undecidability of the halting problem before making wild claims about
>undecidability, that's a little different.
That is not how I have read his postings. And, upon rereading the ones
you object to, I still can't see why you draw the conclusions you do.
I think that you are being unreasonably condemnatory.
In article <ZXoz9.26$V34.3...@newssvr21.news.prodigy.com>,
Bryan Olson <fakea...@nowhere.org> wrote:
> I
>believe my post was about appropriate issues. Your remark: "Any
>you happen to be Tim's lawyer?", is a invalid personal attack.
In my view so was the following, which was the trigger to his remark:
The problem is that there's no doubt who understands and who does
not. Tim Chow's posts have been excellent. You act as if he
brushes off your posts without really understanding what you are
saying. Exactly the opposite is the case.
As I reread the thread, Tim Chow HAS misunderstood Cagdas Ozgenc,
because I read the latter's postings to be asking questions that are
a lot deeper than the simplistic ones. On the other hand, I am not
sure that I understand Cagdas Ozgenc's points well enough to try to
clarify his questions. They are certainly unclear to me.
Cagdas Ozgenc would do well to read or reread those references, but
mainly to learn how to translate his questions into the jargon that
most posters to this group understand. It is very likely that the
reason that I read them differently is because I have touched on so
many different fields of mathematics in my career.
My advice to him would be to back off, attempt to learn how to phrase
his questions in your jargon, and to try again. But that is NOT the
same as making a judgement on who has misunderstood whom.
David Wagner
>Cagdas Ozgenc would do well to read or reread those references, but
>mainly to learn how to translate his questions into the jargon that
>most posters to this group understand.
It's not just "jargon". The term "undecidable" has a standard,
precise definition. Yes, it would have helped to understand the standard
definition when phrasing his questions. Anyway, now that we are aware of
that miscommunication, I think Tim Chow's excellent posts have adequately
his questions about as well as possible. Kudos to Chow.
tc...@lsa.umich.edu
David Wagner <d...@mozart.cs.berkeley.edu> wrote:
>I think Tim Chow's excellent posts have adequately
>his questions about as well as possible. Kudos to Chow.
I appreciate your support. On the other hand, I'm not sure I have really
answered Ozgenc's questions "as well as possible." With the benefit of
hindsight, I think this is what he has been trying to say.
Goedel's theorem says that any "reasonable" first-order theory ("reasonable"
meaning being at least as strong as PA, so that it has some claim to being a
foundation for mathematics, and having a recursive axiomatization, so that
you can't cheat by making "everything" an axiom) is either inconsistent or
incomplete.
In view of the close connection between completeness (of a theory) and
decidability, one might hope that there is an analogous theorem for
computation, that in imprecise terms would say, "No `reasonable' model
of computation can decide all computational questions." "Reasonable"
here should mean that the model of computation is sufficiently powerful
to encompass what are more-or-less-universally agreed to be well-defined
computational processes, but also physically realizable, so that you
can't cheat by making an oracle for every problem.
Skimming the literature, one finds something that looks close, which is
the undecidability of the halting problem for Turing machines. In fact
one could argue that this is *exactly* what we are looking for, *if* one
accepts the Church-Turing thesis that the Turing machine precisely captures
the intuitive concept of "*the* reasonable model of computation." But if
one doesn't accept the Church-Turing thesis, then the undecidability of
the halting problem for Turing machines may taste great, but is less than
filling.
Perhaps, though, we can get what we want by tinkering with the proof of
the undecidability of the halting problem for Turing machines. Most of
the proof seems to proceed at a "high level," making no use of the
detailed definition of a Turing machine. So we might be able to generalize
the proof to prove what we want---which if you recall was "No reasonable
model of computation can decide all computational questions"---by coming
up with an axiomatic definition of "reasonable model of computation" and
showing that the diagonalization argument applies to *any* model of
computation satisfying the axioms.
One would still need to make a Church-Turing-like leap of faith that the
axioms captured "reasonable model of computation" correctly, but if the
axioms were chosen well, perhaps the leap would be reduced. That is,
instead of having to buy the argument that "recursive functions, lambda
calculus, and Turing machines are all equivalent, so this must be the
right answer---after all, nobody's come up with anything better yet,"
one would only have to buy the argument that "look at these axioms;
they must surely be satisfied by any reasonable model of computation."
So the question is, what are the right axioms?
Barb Knox
[snip]
> Perhaps, though, we can get what we want by tinkering with the proof of
> the undecidability of the halting problem for Turing machines. Most of
> the proof seems to proceed at a "high level," making no use of the
> detailed definition of a Turing machine. So we might be able to generalize
> the proof to prove what we want---which if you recall was "No reasonable
> model of computation can decide all computational questions"---by coming
> up with an axiomatic definition of "reasonable model of computation" and
> showing that the diagonalization argument applies to *any* model of
> computation satisfying the axioms.
>
> One would still need to make a Church-Turing-like leap of faith that the
> axioms captured "reasonable model of computation" correctly, but if the
> axioms were chosen well, perhaps the leap would be reduced. That is,
> instead of having to buy the argument that "recursive functions, lambda
> calculus, and Turing machines are all equivalent, so this must be the
> right answer---after all, nobody's come up with anything better yet,"
> one would only have to buy the argument that "look at these axioms;
> they must surely be satisfied by any reasonable model of computation."
>
> So the question is, what are the right axioms?
FWIW, here's an idea. How about "reverse engineering" Scott's
denotational semantics for the lambda calculus to produce a set of axioms
that generate an equivalent model.
--
---------------------------
| BBB b \ barbara minus knox at iname stop com
| B B aa rrr b |
| BBB a a r bbb |
| B B a a r b b |
| BBB aa a r bbb |
-----------------------------
Cagdas Ozgenc
trying to say.
I will study some more and come back to ditch the diagonalization proof yet
even more.
<tc...@lsa.umich.edu> wrote in message news:aqml12$t7t$1...@galois.mit.edu...
Nick Maclaren
The term "undecidable" has more than one such meaning, as well as
several precise but less standard ones. You may be aware of only
one, but that is not the point.
Nick Maclaren
>David Wagner <d...@mozart.cs.berkeley.edu> wrote:
>>I think Tim Chow's excellent posts have adequately
>>his questions about as well as possible. Kudos to Chow.
>
>I appreciate your support. On the other hand, I'm not sure I have really
>answered Ozgenc's questions "as well as possible." With the benefit of
>hindsight, I think this is what he has been trying to say.
That accords with my understanding, too, as far as it goes.
>So the question is, what are the right axioms?
Absolutely. But I would separate the properties of the machine from
those of its use (i.e. go back to Turing). E.g. a random bit primitive
is a property of the machine, but being prepared to accept a suitable
probabilistic result is a property of its use.
While merging them has led to some very fruitful developments, the
belief that they are integral has led to some very harmful ones.
However, I don't believe that changes anything much in this respect.
What might do so (mathematically) is breaking out of countability,
because it destroys diagonalisation limits (and proofs). But it is
SO hairy to work with that I can see why it has never got very far.
Matthias Blume
> In article <aqml12$t7t$1...@galois.mit.edu>, <tc...@lsa.umich.edu> wrote:
> >In article <aqmtm2$2u4c$2...@agate.berkeley.edu>,
> >David Wagner <d...@mozart.cs.berkeley.edu> wrote:
> >>I think Tim Chow's excellent posts have adequately
> >>his questions about as well as possible. Kudos to Chow.
> >
> >I appreciate your support. On the other hand, I'm not sure I have really
> >answered Ozgenc's questions "as well as possible." With the benefit of
> >hindsight, I think this is what he has been trying to say.
>
> That accords with my understanding, too, as far as it goes.
>
> >So the question is, what are the right axioms?
>
> Absolutely. But I would separate the properties of the machine from
> those of its use (i.e. go back to Turing). E.g. a random bit primitive
> is a property of the machine, but being prepared to accept a suitable
> probabilistic result is a property of its use.
>
> While merging them has led to some very fruitful developments, the
> belief that they are integral has led to some very harmful ones.
>
> However, I don't believe that changes anything much in this respect.
> What might do so (mathematically) is breaking out of countability,
> because it destroys diagonalisation limits (and proofs). But it is
> SO hairy to work with that I can see why it has never got very far.
Also, it would almost certainly break the "implementable" constraint
that Tim mentioned.
--
-Matthias
Nick Maclaren
In article <fo65v4x...@trex9.cs.bell-labs.com>,
Matthias Blume <matt...@shimizu-blume.com> writes:
|> nm...@cus.cam.ac.uk (Nick Maclaren) writes:
|>
|> > However, I don't believe that changes anything much in this respect.
|> > What might do so (mathematically) is breaking out of countability,
|> > because it destroys diagonalisation limits (and proofs). But it is
|> > SO hairy to work with that I can see why it has never got very far.
|>
|> Also, it would almost certainly break the "implementable" constraint
|> that Tim mentioned.
Indeed. Arguably little more than "NDTM"s do, though whether that
would be so would depend on the details of the development of the
'uncountable' models. It isn't something that I have a feel for.
The models that I am more interested in are the ones with doubly
bounded errors, and they are both extremely realistic and used in
practice. But I don't think that there is much chance of even a
probabilistic solution to the halting problem, though a proof one
way or the other would be MOST interesting.
Actually, I would put it more strongly. A proof that there can
be no such algorithm would be most interesting, and a proof that
there is one would turn automaton theory inside out.
Bryan Olson
> What might do so (mathematically) is breaking out of countability,
> because it destroys diagonalisation limits (and proofs).
Why do you that?
--
--Bryan
Nick Maclaren
In article <ppQz9.1198$b35.47...@newssvr14.news.prodigy.com>,
What a bizarre question! Why does a pure mathematician choose any
particular model? Because it looks interesting.
Actually, there are also some practical reasons for considering
some models of that nature. They include some of the ones that
model analogue and quantum computing devices, for a start. Please
note that the repetition of "some" was deliberate.
David Wagner
>The term "undecidable" has more than one such meaning, as well as
>several precise but less standard ones. You may be aware of only
>one, but that is not the point.
Please post a reference. My understanding is that the definition of
the term "undecidable" is pretty standard in the CS theory community --
but please, prove me wrong.
Nick Maclaren
In article <aqonbc$aes$1...@agate.berkeley.edu>,
Where did I say that I was referring to that small cabal?
As you should know, the matter of decidability (including both
Goedel's and Turing's results) was researched and largely settled
by mathematicians before what you call the CS theory community
existed. There are decidability concepts in many areas of
mathematics, including statistics, and the term "undecidable" is
quite commonly used.
For example, decision theory predates computer science by decades,
and I have seen the term "undecidable" used to refer to decision
problems where the data carried no information on the parameters
used to make the decision.
Furthermore, please note that many of these uses refer to the very
issues that are being discussed, though sometimes from a different
viewpoint, and often have done since before what you call the CS
theory community existed.
Try broadening your horizons.
David Wagner
>d...@mozart.cs.berkeley.edu (David Wagner) writes:
>|> Nick Maclaren wrote:
>|> >The term "undecidable" has more than one such meaning, as well as
>|> >several precise but less standard ones. You may be aware of only
>|> >one, but that is not the point.
>|>
>|> Please post a reference. My understanding is that the definition of
>|> the term "undecidable" is pretty standard in the CS theory community --
>|> but please, prove me wrong.
>
>Where did I say that I was referring to that small cabal?
Well, this is a theory newsgroup, after all... And when the original
poster mentioned the halting problem, shouldn't it be pretty clear we're
not talking about, say, statistics?
Bryan Olson
> In article <ppQz9.1198$b35.47...@newssvr14.news.prodigy.com>,
> Bryan Olson <fakea...@nowhere.org> writes:
> |> Nick Maclaren wrote:
> |>
> |> > What might do so (mathematically) is breaking out of countability,
> |> > because it destroys diagonalisation limits (and proofs).
> |>
> |> Why do you that?
>
> What a bizarre question!
Yep. It was supposed to read: Why do you think that? Sorry.
--
--Bryan
Nick Maclaren
Well, a diagonalisation limit and/or proof is dependent on two things:
firstly, being able to put a total order on the set of programs (or
whatever) and, secondly, being able to create a new one by taking
one element from each.
In the general case of uncountable sets, both prerequisites fail,
and this isn't just theoretical. There is a diagonalisation proof
that the rationals are not complete that fails when you apply it to
the reals (obviously).
Nick Maclaren
As I have repeatedly said, please take your blinkers off and look
around you. Not merely at other approaches to halting problems (and
even THE halting problem) but how it was tackled before the current
"CS theory community" was out of nappies.
I used that example because there are situations in statistics when
the term "undecidable" has been used precisely to mean that a problem
is such that no algorithm can reach a decision (to an arbitrary
probability). That is a halting problem.
There is a related one in deterministic, information-limited game
theory (i.e. two intelligent opponents) where a game is decidable
if there is enough information exposed to be able to decide whether
either side can force a known solution. Don't be confused into
thinking of such games as finite - the mathematical modelling people
are heavily into games that are not so limited.
Now, in that case, we have an almost identical mathematical model to
the one you are thinking of, with a standard halting problem and a
standard term "undecidable". And, in case you don't know, the theory
of automata that you think of as the universe owes a great deal of
its initiation to deterministic game theory.
Which is why I objected when you said that there was a single meaning
of the term, even in the context of automata.
Matthias Blume
> Nick Maclaren wrote:
> > In article <ppQz9.1198$b35.47...@newssvr14.news.prodigy.com>,
> > Bryan Olson <fakea...@nowhere.org> writes:
> > |> Nick Maclaren wrote:
> > |> |> > What might do so (mathematically) is breaking out of
> > countability,
> > |> > because it destroys diagonalisation limits (and proofs).
> > |> |> Why do you that?
> > What a bizarre question!
>
> Yep. It was supposed to read: Why do you think that? Sorry.
I thought the original question to be quite amusing: a
self-referential omission. Heh, heh... ;-)
--
-Matthias
Cagdas Ozgenc
"Nick Maclaren" <nm...@cus.cam.ac.uk> wrote in message
news:aqqjfj$5s$1...@pegasus.csx.cam.ac.uk...
> In article <5oZz9.4646$0N1.20...@newssvr13.news.prodigy.com>,
> Bryan Olson <fakea...@nowhere.org> wrote:
> >Nick Maclaren wrote:
> >> In article <ppQz9.1198$b35.47...@newssvr14.news.prodigy.com>,
> >> Bryan Olson <fakea...@nowhere.org> writes:
> >> |> Nick Maclaren wrote:
> >> |>
> >> |> > What might do so (mathematically) is breaking out of
countability,
> >> |> > because it destroys diagonalisation limits (and proofs).
> >> |>
> >> |> Why do you that?
> >>
> >> What a bizarre question!
> >
> >Yep. It was supposed to read: Why do you think that? Sorry.
>
> Well, a diagonalisation limit and/or proof is dependent on two things:
> firstly, being able to put a total order on the set of programs (or
> whatever) and, secondly, being able to create a new one by taking
> one element from each.
Isn't that related to "Axiom of Choice"? If so, I suppose you can chose
however you wish. Please enlighten me.
Nick Maclaren
In article <aqr7ld$sn1$1...@news01.cit.cornell.edu>,
"Cagdas Ozgenc" <co...@XinvalidX.cornell.edu> writes:
|> "Nick Maclaren" <nm...@cus.cam.ac.uk> wrote in message
|> news:aqqjfj$5s$1...@pegasus.csx.cam.ac.uk...
|> >
|> > firstly, being able to put a total order on the set of programs (or
|> > whatever) and, secondly, being able to create a new one by taking
|> > one element from each.
|>
|> Isn't that related to "Axiom of Choice"? If so, I suppose you can chose
|> however you wish. Please enlighten me.
Yes. I have always chosen to close my eyes to that one, as I have
never worked out whether I don't understand it or don't believe it!
A rather nice quote is attributed to Jerry Bona:
The Axiom of Choice is obviously true; the Well Ordering Principle
is obviously false; and who can tell about Zorn's Lemma?
tc...@lsa.umich.edu
Nick Maclaren <nm...@cus.cam.ac.uk> wrote:
>Well, a diagonalisation limit and/or proof is dependent on two things:
>firstly, being able to put a total order on the set of programs (or
>whatever) and, secondly, being able to create a new one by taking
>one element from each.
>
>In the general case of uncountable sets, both prerequisites fail,
>and this isn't just theoretical. There is a diagonalisation proof
>that the rationals are not complete that fails when you apply it to
>the reals (obviously).
Since we (or at least Cagdas Ozgenc) are trying to push the limits of the
concept of diagonalization, it is worth pointing out that there is a sense
in which diagonalization can apply to uncountable sets.
For example, consider the following proof of Cantor's theorem that for
any set X, there is no bijection between X and its power set 2^X (i.e.,
the set of all subsets of X). Suppose to the contrary that f:X->2^X is
a bijection. Let Y be the subset of all elements x of X such that x is
not an element of f(x). Since f is a bijection, there exists y in X such
that f(y) = Y. We now ask, is y an element of Y? If so, then by definition
of Y, y is not an element of f(y). But f(y) = Y. Therefore y is not an
element of Y, contradicting our assumption. Therefore y is not an element
of Y. But then since Y was the subset of *all* elements x of X such that
x is not an element of f(x), the fact that y is not in Y implies that
y is an element of f(y) = Y, again a contradiction.
This is often referred to as a "diagonalization" argument and it applies
to uncountable X as well as countable X. Note that no well-ordering of
X was needed.
Bryan Olson
> Well, a diagonalisation limit and/or proof is dependent on two things:
> firstly, being able to put a total order on the set of programs (or
> whatever) and, secondly, being able to create a new one by taking
> one element from each.
>
> In the general case of uncountable sets, both prerequisites fail,
> and this isn't just theoretical. There is a diagonalisation proof
> that the rationals are not complete that fails when you apply it to
> the reals (obviously).
The literal "diagonal" is Cantor's proof that the cardinality of
the reals is greater than the cardinality of the integers. One
doesn't need such a diagonal to prove halting is undecidable, and
what are now called "diagonal arguments" often apply to
uncountable sets.
Perhaps the simplest such proof is that for any well-defined set
S, the power set of S (the set of subsets of S) has more elements
than S. As usual, the proof is by contradiction: suppose we can
map the elements of S onto the subsets of S. Then the following
subset is well-defined: the set of elements not in the subsets to
which they are mapped. But no element of S can map to this
subset, giving us the contradiction. The proof holds whether or
not S is countable.
--
--Bryan
Nick Maclaren
In article <aqr5gu$bns$1...@galois.mit.edu>, tc...@lsa.umich.edu writes:
|> In article <aqqjfj$5s$1...@pegasus.csx.cam.ac.uk>,
||>
|> Since we (or at least Cagdas Ozgenc) are trying to push the limits of the
|> concept of diagonalization, it is worth pointing out that there is a sense
|> in which diagonalization can apply to uncountable sets.
I was never meaning to say that there could be no such inconsistency
proof, but merely that the classic diagonalisation proofs fail.
|> For example, consider the following proof of Cantor's theorem that for
|> any set X, there is no bijection between X and its power set 2^X (i.e.,
|> the set of all subsets of X). Suppose to the contrary that f:X->2^X is
|> a bijection. Let Y be the subset of all elements x of X such that x is
|> not an element of f(x). Since f is a bijection, there exists y in X such
|> that f(y) = Y. We now ask, is y an element of Y? If so, then by definition
|> of Y, y is not an element of f(y). But f(y) = Y. Therefore y is not an
|> element of Y, contradicting our assumption. Therefore y is not an element
|> of Y. But then since Y was the subset of *all* elements x of X such that
|> x is not an element of f(x), the fact that y is not in Y implies that
|> y is an element of f(y) = Y, again a contradiction.
Thanks for the reminder. It is a LONG time since I saw that one,
and I had forgotten all about it!
|> This is often referred to as a "diagonalization" argument and it applies
|> to uncountable X as well as countable X. Note that no well-ordering of
|> X was needed.
For some meaning of the word "diagonal" :-)
I shall see if I can start up my rusty brain and think of applying
that to Turing's halting problem. Do you happen to know if it has
been done for machines with (say) cells that can hold any real
number?
tc...@lsa.umich.edu
Nick Maclaren <nm...@cus.cam.ac.uk> wrote:
>I shall see if I can start up my rusty brain and think of applying
>that to Turing's halting problem. Do you happen to know if it has
>been done for machines with (say) cells that can hold any real
>number?
Certainly the book _Complexity_and_Real_Computation_ by Blum et al. (that
I mentioned previously) proves that their model of real computation suffers
from undecidable problems (the Mandelbrot set being an explicit example).
I don't recall offhand if they discuss the halting problem for their
machines, but their book would be the place to look.
Bryan Olson
> I was never meaning to say that there could be no such inconsistency
> proof, but merely that the classic diagonalisation proofs fail.
[...]
> For some meaning of the word "diagonal" :-)
So where is the "diagonal" in Turing or Gödel's proofs?
One might note that in the proof that the power set of S has more
elements than does S, the countable case does have a literal
diagonal interpretation. We might form an |S| by |S| grid with
the rows and columns labeled with the elements of S in the same
order. We put a 1 in square i,j if the subset mapped to element i
contains element j, a 0 otherwise. Now the diagonal tells whether
each element is in the subset to which it is mapped. If invert
every bit on the diagonal, that represents exactly the set
elements that are not in the subset to which they are mapped.
With an uncountable number of elements, there is no longer a
literal diagonal. Nevertheless, the proof is much closer to
Cantor's diagonal than is the proof that halting is undecidable.
Thus I don't think it makes sense to say that "breaking out of
countability [...] destroys diagonalisation limits (and proofs)."
If you mean a literal diagonal, we were not using one anyway. If
you mean proofs along the lines of Cantor's diagonal, then they
certainly do apply to uncountable sets.
--
--Bryan
Bryan Olson
> David Wagner <d...@mozart.cs.berkeley.edu> wrote:
>>Well, this is a theory newsgroup, after all... And when the original
>>poster mentioned the halting problem, shouldn't it be pretty clear we're
>>not talking about, say, statistics?
>
>
> As I have repeatedly said, please take your blinkers off and look
> around you. Not merely at other approaches to halting problems (and
> even THE halting problem) but how it was tackled before the current
> "CS theory community" was out of nappies.
>
> I used that example because there are situations in statistics when
> the term "undecidable" has been used precisely to mean that a problem
> is such that no algorithm can reach a decision (to an arbitrary
> probability). That is a halting problem.
The thread specifically named Turing and the halting problem.
There is no question about what that means.
Furthermore, if it were ambiguous, then the analysis is even
worse. It's better to be wrong that to be so ill-defined as to be
fail to be right or wrong.
--
--Bryan
Nick Maclaren
In article <uWjA9.10$id3.44...@newssvr13.news.prodigy.com>,
Bryan Olson <fakea...@nowhere.org> writes:
|>
|> The thread specifically named Turing and the halting problem.
|> There is no question about what that means.
In the context of Cagdas Ozgenc's posts, there is. He was clearly
trying to ask about the more general concept of undecidability; if
I recall correctly, he used the term "absolutely undecidable" in
a vain attempt to explain what he meant.
In the game theoretic context I referred to, Turing's halting
problem is decidable, because all information is available. And
that terminology is the senior. There is a strong sense in which
that use should be called "absolute undecidability".
There is also the issue of whether there is a finite extension (in
the axiomatic sense) of the Church/Turing model that would enable
the solution of the halting problem in the Church/Turing model.
That is relevant, too.
|> Furthermore, if it were ambiguous, then the analysis is even
|> worse. It's better to be wrong that to be so ill-defined as to be
|> fail to be right or wrong.
That is a matter of opinion.
Nick Maclaren
In article <VCiA9.8$d_2.44...@newssvr13.news.prodigy.com>,
|>
|> So where is the "diagonal" in Turing or Gödel's proofs?
That is a fair comment. I can't think of a concise way to express
what I meant, though.
|> With an uncountable number of elements, there is no longer a
|> literal diagonal. Nevertheless, the proof is much closer to
|> Cantor's diagonal than is the proof that halting is undecidable.
Hmm. I disagree, because the proofs of Goedel's and Turing's
results that I have seen depend rather critically in countability.
There may well be ones that don't, of course.
|> Thus I don't think it makes sense to say that "breaking out of
|> countability [...] destroys diagonalisation limits (and proofs)."
|> If you mean a literal diagonal, we were not using one anyway. If
|> you mean proofs along the lines of Cantor's diagonal, then they
|> certainly do apply to uncountable sets.
Yes, I should have used different terminology.
Bryan Olson
> Bryan Olson writes:
> |> The thread specifically named Turing and the halting problem.
> |> There is no question about what that means.
>
> In the context of Cagdas Ozgenc's posts, there is. He was clearly
> trying to ask about the more general concept of undecidability; if
> I recall correctly, he used the term "absolutely undecidable" in
> a vain attempt to explain what he meant.
You miss the point. Certainly when Cagdas qualified distinguished
what he meant from Turing definition, that's not the same thing.
But Tim Chow immediately pointed out that without a model of
computation it's meaningless. Then post after post, we have these
questions about undefined terms.
> In the game theoretic context I referred to, Turing's halting
> problem is decidable, because all information is available. And
> that terminology is the senior. There is a strong sense in which
> that use should be called "absolute undecidability".
That has absolutely nothing to do with this discussion. If you
want to know whether that one is decidable, ask if that one is
decidable.
> There is also the issue of whether there is a finite extension (in
> the axiomatic sense) of the Church/Turing model that would enable
> the solution of the halting problem in the Church/Turing model.
> That is relevant, too.
Both Tim Chow and myself answered that. One can certainly define
an oracle that answers HALTS and formally include it in the
definition otherwise like Turing machines.
> |> Furthermore, if it were ambiguous, then the analysis is even
> |> worse. It's better to be wrong that to be so ill-defined as to be
> |> fail to be right or wrong.
>
> That is a matter of opinion.
Sure. Here's another: after Tim Chow's careful explanations of
what statements support mathematical reasoning, it's silly to go
on asking for answers to questions one cannot define.
--
--Bryan
Nick Maclaren
In article <XvrA9.179$BZ1.18...@newssvr14.news.prodigy.com>,
Bryan Olson <fakea...@nowhere.org> writes:
|>
|> You miss the point. Certainly when Cagdas qualified distinguished
|> what he meant from Turing definition, that's not the same thing.
|> But Tim Chow immediately pointed out that without a model of
|> computation it's meaningless. Then post after post, we have these
|> questions about undefined terms.
It was absolutely clear that he was trying to ask a question that
he did not know how to phrase. That does not justify flaming him.
|> > There is also the issue of whether there is a finite extension (in
|> > the axiomatic sense) of the Church/Turing model that would enable
|> > the solution of the halting problem in the Church/Turing model.
|> > That is relevant, too.
|>
|> Both Tim Chow and myself answered that. One can certainly define
|> an oracle that answers HALTS and formally include it in the
|> definition otherwise like Turing machines.
I said "a finite extension". Perhaps you missed that?
Bryan Olson
> I disagree, because the proofs of Goedel's and Turing's
> results that I have seen depend rather critically in countability.
> There may well be ones that don't, of course.
If we can decide HALTS we can decide HALTS_ON_OWN_ENCODING, and
then build a machine such that if the input on the tape is a non-
halter on itself says "non-halter" and if it's a halter goes into
an infinite loop. Now feed it its own encoding.
You didn't actually define "breaking out of countability", so I
cannot tell if that proof assumes something illegal. If the
machine and input are allowed to be infinite length, I don't even
know what HALTS would mean. Nevertheless, there's no explicit
requirement of countability in the proof.
--
--Bryan
Bryan Olson
> Bryan Olson writes:
> |>
> |> You miss the point. Certainly when Cagdas qualified distinguished
> |> what he meant from Turing definition, that's not the same thing.
> |> But Tim Chow immediately pointed out that without a model of
> |> computation it's meaningless. Then post after post, we have these
> |> questions about undefined terms.
>
> It was absolutely clear that he was trying to ask a question that
> he did not know how to phrase. That does not justify flaming him.
So Tim Chow both put forth precise versions, and pointed to how
Cagdas's versions went wrong. Cagdas just kept brushing them off.
What's worse, Cagdas acted like Tim was brushing him off.
Cagdas's later "rehash" suggests that it's not just a problem of
phrasing. The question itself seems ill-defined. We cannot be
sure of course.
> |> > There is also the issue of whether there is a finite extension (in
> |> > the axiomatic sense) of the Church/Turing model that would enable
> |> > the solution of the halting problem in the Church/Turing model.
> |> > That is relevant, too.
> |>
> |> Both Tim Chow and myself answered that. One can certainly define
> |> an oracle that answers HALTS and formally include it in the
> |> definition otherwise like Turing machines.
>
> I said "a finite extension". Perhaps you missed that?
Yes, it's a finite extensions; see my finite description. Or
perhaps you can cite a definition of "finite extensions" of Turing
machines to some reasonable reference and show how I broke the
rules.
--
--Bryan
Nick Maclaren
In article <lMsA9.185$ue2.19...@newssvr14.news.prodigy.com>,
Bryan Olson <fakea...@nowhere.org> writes:
|>
|> > |> > There is also the issue of whether there is a finite extension (in
|> > |> > the axiomatic sense) of the Church/Turing model that would enable
|> > |> > the solution of the halting problem in the Church/Turing model.
|> > |> > That is relevant, too.
|> > |>
|> > |> Both Tim Chow and myself answered that. One can certainly define
|> > |> an oracle that answers HALTS and formally include it in the
|> > |> definition otherwise like Turing machines.
|> >
|> > I said "a finite extension". Perhaps you missed that?
|>
|> Yes, it's a finite extensions; see my finite description. Or
|> perhaps you can cite a definition of "finite extensions" of Turing
|> machines to some reasonable reference and show how I broke the
|> rules.
I said "in the axiomatic sense" - you will find better descriptions
than I can give in mathematical textbooks on the fundamentals of
set theory.
In the sense that anything is finite if it can be put into a finite
number of words, may I add "One can define an oracle that can
answer any question put to it"?
tc...@lsa.umich.edu
Bryan Olson <fakea...@nowhere.org> wrote:
>So Tim Chow both put forth precise versions, and pointed to how
>Cagdas's versions went wrong. Cagdas just kept brushing them off.
>What's worse, Cagdas acted like Tim was brushing him off.
I appreciate your support. If possible, though, I would prefer to re-focus
the discussion on the following article of mine, which you may have missed.
http://groups.google.com/groups?selm=aqml12%24t7t%241%40galois.mit.edu&oe=UTF-8&output=gplain
Cagdas Ozgenc and Nick Maclaren have both more-or-less endorsed what I said
in this article. The question at the end is not "precise" in the sense of
being a mathematical statement that can be either proved or disproved, but
I believe it is a clear question, and a reasonable one. In fact, its very
imprecision may help explain why Ozgenc has been making imprecise statements.
Bryan Olson
> Bryan Olson writes:
> |>
> |> > |> > There is also the issue of whether there is a finite
extension (in
> |> > |> > the axiomatic sense) of the Church/Turing model that
would enable
> |> > |> > the solution of the halting problem in the Church/Turing
model.
> |> > |> > That is relevant, too.
> |> > |>
> |> > |> Both Tim Chow and myself answered that. One can certainly
define
> |> > |> an oracle that answers HALTS and formally include it in the
> |> > |> definition otherwise like Turing machines.
> |> >
> |> > I said "a finite extension". Perhaps you missed that?
> |>
> |> Yes, it's a finite extensions; see my finite description. Or
> |> perhaps you can cite a definition of "finite extensions" of Turing
> |> machines to some reasonable reference and show how I broke the
> |> rules.
>
> I said "in the axiomatic sense" - you will find better descriptions
> than I can give in mathematical textbooks on the fundamentals of
> set theory.
So the answer is no, you cannot cite any such definition. Can you
even precisely describe what you mean? If you think this what you
stated is an interesting question, please state it in
mathematically respectable form.
> In the sense that anything is finite if it can be put into a finite
> number of words, may I add "One can define an oracle that can
> answer any question put to it"?
Of course not. To define the oracle in an axiomatic sense, we
have to define a precise mathematical question that will in fact
have an answer. Once again, see my description for an example.
--
--Bryan
Cagdas Ozgenc
> So Tim Chow both put forth precise versions, and pointed to how
> Cagdas's versions went wrong. Cagdas just kept brushing them off.
> What's worse, Cagdas acted like Tim was brushing him off.
>
> Cagdas's later "rehash" suggests that it's not just a problem of
> phrasing. The question itself seems ill-defined. We cannot be
> sure of course.
Are you trying to start a battle between two people who do not even know
each other? Will you be amused if that happens. Are you planning to
contribute to the discussion, or keep measuring who is pissing further
against the wind? Tim and I had a misunderstanding, that is true, but it is
non of your business (and I really mean it).
Nick Maclaren
In article <aqt9jn$150$1...@galois.mit.edu>, tc...@lsa.umich.edu writes:
|> In article <lMsA9.185$ue2.19...@newssvr14.news.prodigy.com>,
|> Bryan Olson <fakea...@nowhere.org> wrote:
|> >So Tim Chow both put forth precise versions, and pointed to how
|> >Cagdas's versions went wrong. Cagdas just kept brushing them off.
|> >What's worse, Cagdas acted like Tim was brushing him off.
|>
|> I appreciate your support. If possible, though, I would prefer to re-focus
|> the discussion on the following article of mine, which you may have missed.
|>
|> http://groups.google.com/groups?selm=aqml12%24t7t%241%40galois.mit.edu&oe=UTF-8&output=gplain
|>
|> Cagdas Ozgenc and Nick Maclaren have both more-or-less endorsed what I said
|> in this article. The question at the end is not "precise" in the sense of
|> being a mathematical statement that can be either proved or disproved, but
|> I believe it is a clear question, and a reasonable one. In fact, its very
|> imprecision may help explain why Ozgenc has been making imprecise statements.
I am prepared to endorse that posting, explicitly, as being a fair
summary of what my guess is that Cagdas Ozgenc was asking. It is
certainly a fair summary of the points that I was trying to make.
And it is a HARD question!
Bryan Olson
> Are you trying to start a battle between two people who do not even know
> each other? Will you be amused if that happens.
Did you miss that in the "rehash" thread? I first asked you if
you could define what you meant. No reply.
> Are you planning to
> contribute to the discussion, or keep measuring who is pissing further
> against the wind?
Did you miss that in the "Church-Turing thesis/halting problem"
thread I offered answers on two of your specific issues? Did you
think they were irrelevant? Incorrect? I cannot tell since you
did not respond. Did read my response when you wrote "I just
would like to interpret Godel from Turing point of view, and
Turing from Godel point of view." I tried to show how to do just
that. No response.
So in answer to your question, yes, I intend to continue to
contribute.
> Tim and I had a misunderstanding, that is true, but it is
> non of your business (and I really mean it).
And when you read what I've written, be aware that I really mean
it too.
--
--Bryan
Nick Maclaren
In article <_etA9.188$To2.19...@newssvr14.news.prodigy.com>,
Bryan Olson <fakea...@nowhere.org> writes:
|> > |> >
|> > |> > I said "a finite extension". Perhaps you missed that?
|> > |>
|> > |> Yes, it's a finite extensions; see my finite description. Or
|> > |> perhaps you can cite a definition of "finite extensions" of Turing
|> > |> machines to some reasonable reference and show how I broke the
|> > |> rules.
|> >
|> > I said "in the axiomatic sense" - you will find better descriptions
|> > than I can give in mathematical textbooks on the fundamentals of
|> > set theory.
|>
|> So the answer is no, you cannot cite any such definition. Can you
|> even precisely describe what you mean? If you think this what you
|> stated is an interesting question, please state it in
|> mathematically respectable form.
Twaddle. See, for example:
http://mathworld.wolfram.com/Zermelo-FraenkelSetTheory.html
I wouldn't put too much trust in that, given the number of errors
in those Web pages, but it is a reference to the issue. As
I am several miles from the nearest real mathematical library, I
shall certainly not be looking up a decent one to save you the
effort.
|> > In the sense that anything is finite if it can be put into a finite
|> > number of words, may I add "One can define an oracle that can
|> > answer any question put to it"?
|>
|> Of course not. To define the oracle in an axiomatic sense, we
|> have to define a precise mathematical question that will in fact
|> have an answer. Once again, see my description for an example.
If you think that your description was precise and finite in the
axiomatic sense, then you need to revise your memory.
Bryan Olson
> Bryan Olson <fakea...@nowhere.org> writes:
> |> > |> >
> |> > |> > I said "a finite extension". Perhaps you missed that?
> |> > |>
> |> > |> Yes, it's a finite extensions; see my finite description. Or
> |> > |> perhaps you can cite a definition of "finite extensions" of
Turing
> |> > |> machines to some reasonable reference and show how I broke the
> |> > |> rules.
> |> >
> |> > I said "in the axiomatic sense" - you will find better descriptions
> |> > than I can give in mathematical textbooks on the fundamentals of
> |> > set theory.
> |>
> |> So the answer is no, you cannot cite any such definition. Can you
> |> even precisely describe what you mean? If you think this what you
> |> stated is an interesting question, please state it in
> |> mathematically respectable form.
>
> Twaddle. See, for example:
>
> http://mathworld.wolfram.com/Zermelo-FraenkelSetTheory.html
Which has nothing to do with the issue here. Turing machines are
not a set theory and no extension is going to turn them into one.
And again, you cannot define what you mean, so it's no surprise
you make no progress on the question.
--
--Bryan
David Wagner
>In the context of Cagdas Ozgenc's posts, there is. He was clearly
>trying to ask about the more general concept of undecidability; if
>I recall correctly, he used the term "absolutely undecidable" in
>a vain attempt to explain what he meant.
Well, not in his original article, he didn't. He never used the term
"absolutely undecidable". He just used the word "undecidable", but he
apparently intended it to mean something non-standard. Not that this
really matters -- the last paragraph of his original post made it clear
that he wasn't using the word "undecidable" in the standard way.
Cagdas Ozgenc
As I read more about computation theory I get more confused about it.
As far as I understand Church-Turing thesis is a hypothesis, and never been
proven. Undecidability of halting problem seems to be based on the validity
of the above hypothesis, which means if the thesis happens to be false, then
halting problem may turn out to be computable.
For example, let's consider the diagonalization proof for Halting Problem.
First we look at the self-halting problem.
BEGIN PROOF=====================
Ls = { <p> | p is a program that halts when its description is given as its
input }
assume machine S decides Ls
S(x) <=> x halts on x
design machine Q the following way
Q(x) {
while(S(x)); // loop when S(x) is true
}
Hence
Q(x) halts <=> not S(x) <=> x does not halt on x
replace x with Q:
Q(Q) halts <=> Q does not halt on Q
Q halts on Q <=> Q does not halt on Q
contradition, hence S does not exist
Lhp = { <p,x> | p is a program that halts on x }
Lhp is undecidable with simple reduction to Ls:
S(x) {
return HP(x,x)
}
in otherwords S(x) would be computable had HP(p,x) been computable,
therefore Lhp is undecidable as well.
END PROOF=====================
Now my confusion is as follows:
The machine Q that we designed has to be in the form of some automaton. S
understands some automaton type as its input and analyze it for a solution.
Now the automaton type for Q and automaton type for inputs of S has to
match. Otherwise this proof is invalid, because it is natural for S not to
be able to compute if the input is not given in the appropriate format. But
we cannot assume that S understands the format of Q.
The only way the above proof may hold is to start with a known automata(and
restrict the programs in Ls to such automata, and Q to the same type as
well), such as a Turing Machine, but then the proof will only hold for
Turing-Machines not for all automata in general.
I agree that Halting Problem is undecidable for Turing Machines, but since
it is not proven that Turing Machines are the most powerful machines then we
cannot conclude that Halting Problem is undecidable.
Please, help me clarify this mess.
Thanks for taking time.
Jim Nastos
> As far as I understand Church-Turing thesis is a hypothesis, and never been
> proven. Undecidability of halting problem seems to be based on the validity
> of the above hypothesis, which means if the thesis happens to be false, then
> halting problem may turn out to be computable.
The undecidability of any problem depends on the model of computation.
The Halting problem is undecidable by these things we have constructed
called Turing machines. For a beginner trying to understand computability
theory, a useful way to think about the Church-Turing thesis is in the
following way: the Turing machine is the most powerful model of
computation (not exactly, but in the sense to follow). This idea is
supported with the fact that if you add more tapes, heads, symbols,
nondeterminism, etc to the functionality of the Turing Machine, this new
machine can still be simulated by the basic Turing Machine.
> I agree that Halting Problem is undecidable for Turing Machines, but since
> it is not proven that Turing Machines are the most powerful machines then we
> cannot conclude that Halting Problem is undecidable.
Sure, if you want to think of it that way. But it IS "undecidable by a
Turing Machine" (which is what is usually referred to as being just
"undecidable.")
It's just the same with simpler models of computation. A Non-regular
language can not be recognized by a deterministic finite automaton. But we
can define a push-down automaton to compute this.
The Halting problem can not be decided by a Turing Machine. If you want
to construct a new model of computation more powerful than the Turing
Machine to solve the Halting problem, you can. But if you want to
construct a useful model, keep in mind that even the world's most powerful
computer can be simulated by a Turing Machine.
Jim
tc...@lsa.umich.edu
Cagdas Ozgenc <co...@XinvalidX.cornell.edu> wrote:
>As far as I understand Church-Turing thesis is a hypothesis, and never been
>proven. Undecidability of halting problem seems to be based on the validity
>of the above hypothesis, which means if the thesis happens to be false, then
>halting problem may turn out to be computable.
Here's one way to think about it. There are two kinds of statements in the
world:
1. Precise, mathematical statements.
2. Vague, philosophical statements.
Mathematical proofs can *only* be given for statements of type 1.
There is no way to give a mathematical proof of a statement of type 2,
any more than one can give a mathematical proof that love makes the
world go around. It's simply not the kind of statement to which the
techniques of mathematics apply.
The Church-Turing thesis is a statement of type 2. It has never been
proven, for the same reason that it has never been mathematically proven
that Marilyn Monroe was the prettiest woman who ever lived. It is simply
not the *kind* of statement that is susceptible to mathematical proof.
Contrast this with the famous "P = NP" problem. This has never been
proven, but for a different reason; "P = NP" is a type 1 statement,
but nobody has yet figured out a proof.
The undecidability of the halting problem is not "based on the validity
of the Church-Turing thesis" in the way that a mathematical theorem is
based on mathematical axioms. Let me ask you this: Is the statement
"The halting problem is undecidable" a type 1 or a type 2 statement?
If your answer is "type 1," then that means you should be able to define
"undecidable" in a precise, mathematical way. The only way I know how
to do that is to define "undecidable" using the Turing machine concept.
Once this is done, then "The halting problem is undecidable" becomes
*synonymous* with "The halting problem cannot be decided by Turing
machines," which can be proved mathematically without appealing to
the Church-Turing thesis or any other type 2 statements.
On the other hand, perhaps you answered "type 2," because you are not
sure about the Church-Turing thesis and resist defining "undecidable"
in terms of Turing machines. In that case, "The halting problem is
undecidable" is indeed not provable using the mathematical reasoning
you cited. But note that this is not because the mathematical reasoning
is inadequate or uses an unproven hypothesis. It is because without a
precise definition of "undecidable," the statement is of type 2 and
therefore not the *kind* of statement that can *possibly* be proven.
The Church-Turing thesis says that the vague word "undecidable" can be
translated (using the Turing machine concept) into a precise term without
losing anything in the translation. While plausible, it is not needed in
any mathematical argument. Insist that people give you a type 1 statement
before asking you to prove it, and you will find that you never need to
invoke the Church-Turing thesis.
Cagdas Ozgenc
"Jim Nastos" <nas...@cs.ualberta.ca> wrote in message
news:Pine.LNX.4.44.02110...@eva117.cs.ualberta.ca...
> On Tue, 5 Nov 2002, Cagdas Ozgenc wrote:
>
> > As far as I understand Church-Turing thesis is a hypothesis, and never
been
> > proven. Undecidability of halting problem seems to be based on the
validity
> > of the above hypothesis, which means if the thesis happens to be false,
then
> > halting problem may turn out to be computable.
>
> The undecidability of any problem depends on the model of computation.
> The Halting problem is undecidable by these things we have constructed
> called Turing machines. For a beginner trying to understand computability
> theory, a useful way to think about the Church-Turing thesis is in the
> following way: the Turing machine is the most powerful model of
> computation (not exactly, but in the sense to follow). This idea is
> supported with the fact that if you add more tapes, heads, symbols,
> nondeterminism, etc to the functionality of the Turing Machine, this new
> machine can still be simulated by the basic Turing Machine.
I am not really looking for a beginner point of view. I am trying to get to
the core of it.
Basically my concern is the following:
Goedel showed that a decent formal system will always be incomplete, in the
sense that there will be unprovable statements, in other words things that
cannot be computed.
But there is always an auxillary system that can prove those statements, but
still the auxillary system in itself will have unsolvable problems.
For example, a TM is an auxillary system to a DFA. Or, correct me if I am
wrong but a second order logic system is an auxillary (or maybe I should say
a meta system)system to a first order logic system.
Having said that the concept of undecidability is shaky. What's undecidable
for a DFA maybe decidable for a TM. And what's undecidable for a TM may be
decidable for some undiscovered machine. Therefore it seems that saying that
something is undecidable does not mean that it will be undecidable forever,
which is a shame.
Also, I think some cross correlation of machines has to be examined. It is
easy to show that a machine cannot decide its own halting problem. But if
there are two machines one deciding other's halting problem that would be
useful.
> > I agree that Halting Problem is undecidable for Turing Machines, but
since
> > it is not proven that Turing Machines are the most powerful machines
then we
> > cannot conclude that Halting Problem is undecidable.
>
> Sure, if you want to think of it that way. But it IS "undecidable by a
> Turing Machine" (which is what is usually referred to as being just
> "undecidable.")
> It's just the same with simpler models of computation. A Non-regular
> language can not be recognized by a deterministic finite automaton. But we
> can define a push-down automaton to compute this.
> The Halting problem can not be decided by a Turing Machine. If you want
> to construct a new model of computation more powerful than the Turing
> Machine to solve the Halting problem, you can. But if you want to
> construct a useful model, keep in mind that even the world's most powerful
> computer can be simulated by a Turing Machine.
No I am not going to attempt building something more powerful, I am sure
smarter people have already tried that. But someone has to show the
convergence of the meta-meta-meta-.... systems to the point where there is
no other level. Otherwise undecidability is based on an assumption that
there is no powerful system than a TM.
tc...@lsa.umich.edu
Cagdas Ozgenc <co19@map's'pam.cornell.edu> wrote:
>Having said that the concept of undecidability is shaky. What's undecidable
>for a DFA maybe decidable for a TM. And what's undecidable for a TM may be
>decidable for some undiscovered machine. Therefore it seems that saying that
>something is undecidable does not mean that it will be undecidable forever,
>which is a shame.
If you allow arbitrarily powerful machines, then nothing is undecidable.
For example, take the halting problem for Turing machines. It is decidable
by a machine that looks at a Turing machine and outputs "yes" if it halts
and "no" if it doesn't.
Can I *build* such a machine? Or can I give you more details about this
machine, explaining step by step exactly *how* such a machine works so that
you can check its correctness?
Can I mathematically *prove* to you that nobody will *ever* be able to
give a step-by-step explicit description of such a machine and build it?
No, because the term "step-by-step explicit description" is a vague term
and hence any claim about it is by its very nature not susceptible to
mathematical proof. See my other article for an explanation of the
distinction between mathematical and non-mathematical statements.
http://groups.google.com/groups?selm=aq9c99%247b9%241%40galois.mit.edu&oe=UTF-8&output=gplain
You seem to think that the Church-Turing thesis is a precise mathematical
statement, and that you are making a mathematical claim when you say that
"some undiscovered machine may prove to be stronger than a Turing machine."
But these are not *mathematical* claims. You also seem to find it a "shame"
that these non-mathematical statements are not susceptible to mathematical
proof. But I don't find this a "shame" any more than it's a "shame" that
nobody has proved mathematically that Dostoevsky was a better writer than
Tolstoy.
David Wagner
>Having said that the concept of undecidability is shaky.
No, this is not so.
>And what's undecidable for a TM may be decidable for some
>undiscovered machine.
This is not true, either[1].
It seems to me the problem is that you're reasoning by analogy, or
by guesswork. Your analogies, or guesses, are misleading you. I can
understand why, not having read the proof, you aren't convinced yet.
However, the answer to this is to read and understand the proof, not to
produce more analogies or guesses. We can invent all the analogies we
like, but they are unlikely to provide much insight.
[1] I'm assuming you define "undecidable" as everyone else does, namely,
not decidable by a Turing machine.
Cagdas Ozgenc
> Cagdas Ozgenc <co19@map's'pam.cornell.edu> wrote:
> >Having said that the concept of undecidability is shaky. What's
undecidable
> >for a DFA maybe decidable for a TM. And what's undecidable for a TM may
be
> >decidable for some undiscovered machine. Therefore it seems that saying
that
> >something is undecidable does not mean that it will be undecidable
forever,
> >which is a shame.
>
> If you allow arbitrarily powerful machines, then nothing is undecidable.
> For example, take the halting problem for Turing machines. It is
decidable
> by a machine that looks at a Turing machine and outputs "yes" if it halts
> and "no" if it doesn't.
You are misinterpreting my comments, and astraying from the original
discussion. All non-trivial properties about a very powerful machine is
undecidable when the machine itself tries to decide them. But there is no
proof that says these properties are undecidable by a yet more powerful
machine.
> Can I *build* such a machine? Or can I give you more details about this
> machine, explaining step by step exactly *how* such a machine works so
that
> you can check its correctness?
> Can I mathematically *prove* to you that nobody will *ever* be able to
> give a step-by-step explicit description of such a machine and build it?
> No, because the term "step-by-step explicit description" is a vague term
> and hence any claim about it is by its very nature not susceptible to
> mathematical proof. See my other article for an explanation of the
> distinction between mathematical and non-mathematical statements.
>
>
http://groups.google.com/groups?selm=aq9c99%247b9%241%40galois.mit.edu&oe=UT
F-8&output=gplain
>
> You seem to think that the Church-Turing thesis is a precise mathematical
> statement, and that you are making a mathematical claim when you say that
> "some undiscovered machine may prove to be stronger than a Turing
machine."
> But these are not *mathematical* claims. You also seem to find it a
"shame"
> that these non-mathematical statements are not susceptible to mathematical
> proof. But I don't find this a "shame" any more than it's a "shame" that
> nobody has proved mathematically that Dostoevsky was a better writer than
> Tolstoy.
Dear sir, I am not questioning the vague-ness of defintions like
"effectively computable" or "step-by-step", because they are indeed vague.
There are some mathematically defined concepts.
For example you think that decidability is a vague concept, but it is well
founded.
Decidability is based on set membership, and it is axiomatic, basically it
is one of the axioms of set theory.
Now my very simple and trivial question is the following: Can we physically
build a machine that can decide the Turing Machine halting problem?
Now you may argue that "machine" is a vague concept, but it is not. Only
limitation to this machine is that it has to have the cabability to interact
with Humans with a HCI interface. Let's limit it to keyboard, shall we? I
don't care whether it is a step-by-step machine, or some state machine, or
whether it is a state machine at all.
So in the end the limitation on this machine is that the input has to be
entered sequentially (I am not aware of my telephathic abilities yet, so I
prefer to use my fingers to type), and the output has to be given in finite
amount of time.
I think such a machine is formal enough to conduct a proof.
Thanks
Michael N. Christoff
"Cagdas Ozgenc" <co...@XinvalidX.cornell.edu> wrote in message
news:aqc5f0$1k2$1...@news01.cit.cornell.edu...
> > In article <aqats7$dcr$1...@news01.cit.cornell.edu>,
> > Cagdas Ozgenc <co19@map's'pam.cornell.edu> wrote:
> > >Having said that the concept of undecidability is shaky. What's
> undecidable
> > >for a DFA maybe decidable for a TM. And what's undecidable for a TM may
> be
> > >decidable for some undiscovered machine. Therefore it seems that saying
> that
> > >something is undecidable does not mean that it will be undecidable
> forever,
> > >which is a shame.
> >
> > If you allow arbitrarily powerful machines, then nothing is undecidable.
> > For example, take the halting problem for Turing machines. It is
> decidable
> > by a machine that looks at a Turing machine and outputs "yes" if it
halts
> > and "no" if it doesn't.
>
> You are misinterpreting my comments, and astraying from the original
> discussion. All non-trivial properties about a very powerful machine is
> undecidable when the machine itself tries to decide them. But there is no
> proof that says these properties are undecidable by a yet more powerful
> machine.
But "undecidable" is _defined_ in terms of Turing Machines. If you wish,
you may qualify "undecidable" as "Turing-undecidable", but I don't see the
use in that until we have created an implementable super Turing machine.
I don't think that's what he was trying to say, but anyways, yes -
decidability is well-defined.
>
> Decidability is based on set membership, and it is axiomatic, basically it
> is one of the axioms of set theory.
>
> Now my very simple and trivial question is the following: Can we
physically
> build a machine that can decide the Turing Machine halting problem?
>
Not at present. But there is at least one theoretical machine (an analog
neural net) that is "super-Turing". It can decide the halting problem for
Turing machines, but it cannot decide its own halting problem. Note this
machine requires the ability to store and recover non-rational real-numbers
in their entirety.
> Now you may argue that "machine" is a vague concept, but it is not. Only
> limitation to this machine is that it has to have the cabability to
interact
> with Humans with a HCI interface. Let's limit it to keyboard, shall we? I
> don't care whether it is a step-by-step machine, or some state machine, or
> whether it is a state machine at all.
>
> So in the end the limitation on this machine is that the input has to be
> entered sequentially (I am not aware of my telephathic abilities yet, so I
> prefer to use my fingers to type), and the output has to be given in
finite
> amount of time.
>
> I think such a machine is formal enough to conduct a proof.
>
All you've given are some minimum requirements for the term "machine", you
haven't come close to defining it in a way that we can use to prove
anything. Its like me defining a super-machine as a machine that can solve
the halting problems for Turing machines. That's a precise, mathematical
property of the machine, but it still gets us nowhere.
PS: Try not to take our statements personally. Think about it for a second
and you may see there is actually something to what we are saying.
l8r, Mike N. Christoff
Bryan Olson
> I agree that Halting Problem is undecidable for Turing Machines, but
since
> it is not proven that Turing Machines are the most powerful machines
then we
> cannot conclude that Halting Problem is undecidable.
>
> Please, help me clarify this mess.
First, the Church-Turing hypothesis is somewhat hard to state, and
there's no single accepted statement. The interesting thing is
that reasonable models of computation all turn out to be equally
powerful. Recursive functions, Turing machines, RAM machines,
Post machines lambda calculus -- all these and many others can
compute all and only the same functions. Give a C implementation
access to arbitrarily large file space, and that's equivalent too.
One *can* define models of computation that are more powerful, but
the examples smack of cheating. For example, the Turing2 machine
is like the Turing machine, but augmented with an oracle that
solves the Turing-machine halting problem: a distinguished state
triggers the oracle, which takes everything before the current
tape position to be a program with no input, and writes '0' on the
current tape position if the program halts and 1 if it doesn't.
Incidentally, no Turing2 machine decides the Turing2 halting
problem.
--
--Bryan
tc...@lsa.umich.edu
Michael N. Christoff <mchri...@MAPSON.sympatico.ca> wrote:
>"Cagdas Ozgenc" <co...@XinvalidX.cornell.edu> wrote in message
>news:aqc5f0$1k2$1...@news01.cit.cornell.edu...
>> is one of the axioms of set theory.
That's not how most people define "decidability," but let me pass over this
because I don't think it's the main point.
>> Now my very simple and trivial question is the following: Can we
>> physically build a machine that can decide the Turing Machine halting
>> problem?
Yours is a physics question, not a mathematics question. Physics is an
empirical science, and hence there is no way to prove the answer to a
physics question using sheer logic. The answer to your question is that
nobody has been able to build such a machine so far. If you are hoping
for a "proof" using pure logic that nobody will ever be able to build
such a machine, then you're out of luck. Physics is simply not susceptible
to pure logic in this way.
As you said, "undecidable" is a purely mathematical concept. The sentence
"the halting problem is undecidable" *by definition* is *synonymous* with
"the halting problem cannot be decided by a Turing machine." It does *not*
mean "the halting problem cannot be decided by any machine that can be
physically built." What can or cannot be physically built is certainly
not dictated by the axioms of set theory.
>> Now you may argue that "machine" is a vague concept, but it is not. Only
>> limitation to this machine is that it has to have the cabability to
>> interact
>> with Humans with a HCI interface. Let's limit it to keyboard, shall we? I
>> don't care whether it is a step-by-step machine, or some state machine, or
>> whether it is a state machine at all.
>>
>> So in the end the limitation on this machine is that the input has to be
>> entered sequentially (I am not aware of my telephathic abilities yet, so I
>> prefer to use my fingers to type), and the output has to be given in
>> finite amount of time.
>>
>> I think such a machine is formal enough to conduct a proof.
>
>All you've given are some minimum requirements for the term "machine", you
>haven't come close to defining it in a way that we can use to prove
>anything. Its like me defining a super-machine as a machine that can solve
>the halting problems for Turing machines. That's a precise, mathematical
>property of the machine, but it still gets us nowhere.
Right. Cagdas Ozgenc's definition is precise enough for physics or
engineering purposes, but not precise enough for a mathematical or
purely logical proof. For example, at minimum Ozgenc needs to describe
formally the laws of physics that he is assuming when he says "physically
buildable." For example, is it possible to physically build a rod of
length exactly x meters, where x is an infinite-precision binary number
whose nth bit is 1 if and only if the nth Turing machine halts? And if
such a rod is not ruled out by the laws of physics, can I build a machine
that will print out the nth bit of x when I type "n" at the keyboard,
by measuring the rod with the desired precision?
Cagdas Ozgenc
mean time I also would like to discuss one catch in the proof of the halting
problem.
Now if we analyze halting problem only in the context of Turing Mahines
everything is just fine. But the ultimate conclusion is the following: "a
machine cannot decide its own halting problem". Now the proof becomes a
little shaky, I repeat the proof from my original post:
BEGIN PROOF=====================
Ls = { <p> | p is a program that halts when its description is given as its
input }
// basically I am just using the term "program"
// and not limit things to a TM
assume machine S decides Ls
S(x) <=> x halts on x
design machine Q the following way
Q(x) {
while(S(x)); // loop when S(x) is true
}
// ******** here is the catch ***********
(1) There is an assumption in the proof that Q(x) is of the same automaton
as S(x)
because we will be feeding Q to Q(x) and to S(x).
OK let's make that assumption.
But now there is another assumption here: "(2)the machine that can decide
the halting problem has the power to go into infinite loop"
The proof neglects the machines that can decide its own halting problem but
that may not have the ability go into an infinite loop.
This is not a problem for TMs because we now that TMs can get into loop
easily, therefore the proof holds for TMs. But it should have hold for all
type of automaton.
Either of the assumptions (1,2) makes the proof a little shaky for automata
other than TMs.
// **********************************
Hence
Q(x) halts <=> not S(x) <=> x does not halt on x
replace x with Q:
Q(Q) halts <=> Q does not halt on Q
Q halts on Q <=> Q does not halt on Q
contradition, hence S does not exist
Lhp = { <p,x> | p is a program that halts on x }
Lhp is undecidable with simple reduction to Ls:
S(x) {
return HP(x,x)
}
in otherwords S(x) would be computable had HP(p,x) been computable,
therefore Lhp is undecidable as well.
END PROOF=====================
> >
> > You are misinterpreting my comments, and astraying from the original
> > discussion. All non-trivial properties about a very powerful machine is
> > undecidable when the machine itself tries to decide them. But there is
no
> > proof that says these properties are undecidable by a yet more powerful
> > machine.
>
> But "undecidable" is _defined_ in terms of Turing Machines. If you wish,
> you may qualify "undecidable" as "Turing-undecidable", but I don't see the
> use in that until we have created an implementable super Turing machine.
Yes. I understand, that was my major concern. "undecidable" is a misnomer.
"TM-undecidable" suits much better.
> >
> > Dear sir, I am not questioning the vague-ness of defintions like
> > "effectively computable" or "step-by-step", because they are indeed
vague.
> >
> > There are some mathematically defined concepts.
> >
> > For example you think that decidability is a vague concept, but it is
well
> > founded.
> >
>
> I don't think that's what he was trying to say, but anyways, yes -
> decidability is well-defined.
>
> >
> > Decidability is based on set membership, and it is axiomatic, basically
it
> > is one of the axioms of set theory.
> >
> > Now my very simple and trivial question is the following: Can we
> physically
> > build a machine that can decide the Turing Machine halting problem?
> >
>
> Not at present. But there is at least one theoretical machine (an analog
> neural net) that is "super-Turing". It can decide the halting problem for
> Turing machines, but it cannot decide its own halting problem. Note this
> machine requires the ability to store and recover non-rational
real-numbers
> in their entirety.
I have read about that as well. But also read that the model is neglecting
the physical limitations of wires, etc that implicitly quantizes the domain,
where one thinks that analog circuitry is a continuous system. Anyways,
people have to try building one rather than dreaming one.
> > Now you may argue that "machine" is a vague concept, but it is not. Only
> > limitation to this machine is that it has to have the cabability to
> interact
> > with Humans with a HCI interface. Let's limit it to keyboard, shall we?
I
> > don't care whether it is a step-by-step machine, or some state machine,
or
> > whether it is a state machine at all.
> >
> > So in the end the limitation on this machine is that the input has to be
> > entered sequentially (I am not aware of my telephathic abilities yet, so
I
> > prefer to use my fingers to type), and the output has to be given in
> finite
> > amount of time.
> >
> > I think such a machine is formal enough to conduct a proof.
> >
>
> All you've given are some minimum requirements for the term "machine", you
> haven't come close to defining it in a way that we can use to prove
> anything. Its like me defining a super-machine as a machine that can
solve
> the halting problems for Turing machines. That's a precise, mathematical
> property of the machine, but it still gets us nowhere.
I understand your point. We first need to axiomize the physical limitations.
> PS: Try not to take our statements personally. Think about it for a
second
> and you may see there is actually something to what we are saying.
The reason I am taking it personal is that some people are simply bulking
without even reading the question and presenting cliche answers that are
dictated in many theory books.
Cagdas Ozgenc
>
> Yours is a physics question, not a mathematics question. Physics is an
> empirical science, and hence there is no way to prove the answer to a
> physics question using sheer logic. The answer to your question is that
> nobody has been able to build such a machine so far. If you are hoping
> for a "proof" using pure logic that nobody will ever be able to build
> such a machine, then you're out of luck. Physics is simply not
susceptible
> to pure logic in this way.
You are right. What I have in mind at the moment is that if we look at
Cook's theorem "for every decision problem L in NP there is a polynomial
time transformation of L into SAT", we see that he managed to make a proof
without knowing what L is. I haven't had time to study the proof completely
yet. What's interesting is that proofs can be conducted without knowing the
exact description of everything. I have this "feeling" that we may at the
end show whether TM is the limit of computation without knowing what
"computation" is.
I will study some more and get back to you, if you are still hanging around
in this NG.
Cagdas Ozgenc
> But now there is another assumption here: "(2)the machine that can decide
> the halting problem has the power to go into infinite loop"
> The proof neglects the machines that can decide its own halting problem
but
> that may not have the ability go into an infinite loop.
> This is not a problem for TMs because we now that TMs can get into loop
> easily, therefore the proof holds for TMs. But it should have hold for all
> type of automaton.
Or it assumes that a machine can do conditional testing or negation. Without
such a power we would not be able to use diagonalization in my opinion.
tc...@lsa.umich.edu
>machine cannot decide its own halting problem".
Whoever is telling you that this is supposed to be the ultimate conclusion
is mistaken. The proof certainly doesn't show that a machine can't decide
its own halting problem. For example, consider the following class C of
machines: The class contains only one element, namely the machine that
always outputs "yes," and then halts. The machine in this class successfully
decides the halting problem for all machines in the class C.
>// ******** here is the catch ***********
>(1) There is an assumption in the proof that Q(x) is of the same automaton
>as S(x)
>because we will be feeding Q to Q(x) and to S(x).
No, the assumption isn't anything nearly as strong as that. All you need
are things like "Q and S take the same forms of input (keystrokes at a
keyboard for example)" and "when building automaton Q it is permissible to
invoke automaton S as a `subroutine.'"
>But now there is another assumption here: "(2)the machine that can decide
>the halting problem has the power to go into infinite loop"
>The proof neglects the machines that can decide its own halting problem but
>that may not have the ability go into an infinite loop.
Again, you're making a mistake by thinking that the proof is supposed to
show that no machine can decide the halting problem for a class of machines
of which it is a member. That's not what it's intended to show (good thing
too, since that claim is false).
>This is not a problem for TMs because we now that TMs can get into loop
>easily, therefore the proof holds for TMs. But it should have hold for all
>type of automaton.
If you look at the proof again, there is no assumption that the machine that
is *doing the deciding* can go into a loop easily. All you really need is
that the alleged halting-problem-solver can be legally incorporated into a
TM as a subroutine ("legally" meaning that the result after incorporation is
still a TM).
Michael J. Fromberger
"Cagdas Ozgenc" <co19@map's'pam.cornell.edu> wrote:
> > The answer to your question is that nobody has been able to build
> > such a machine so far. If you are hoping for a "proof" using pure
> > logic that nobody will ever be able to build such a machine, then
> > you're out of luck. Physics is simply not susceptible to pure
> > logic in this way.
>
> You are right. What I have in mind at the moment is that if we look at
> Cook's theorem "for every decision problem L in NP there is a polynomial
> time transformation of L into SAT", we see that he managed to make a proof
> without knowing what L is. I haven't had time to study the proof completely
> yet. What's interesting is that proofs can be conducted without knowing the
> exact description of everything. I have this "feeling" that we may at the
> end show whether TM is the limit of computation without knowing what
> "computation" is.
The essence of the proof of the Cook-Levin theorem is to show that you
can encode a polynomial-time nondeterministic Turing machine M that
decides L, along with its input (the instance), as an instance of SAT.
The proof basically shows that the SAT instance so generated is
satisfiable exactly if and only if M accepts L. Independence from L is
achieved by using the decider M, instead of the structure of L.
This brief description, of course, glosses over many important details,
so you should still read the actual proof! It's quite fascinating!
But in any case, I don't think this technique extends to the type of
meta-proof you're describing; to "prove" the Church-Turing Hypothesis,
you would have to be able to say something like, "For any effectively
computable model of computation A, there exists a TM M whose output is
equivalent to that of A for any suitably encoded problem instance."
The main problem is, what constitutes an "effectively computable model
of computation?" Most people agree that the operations of a Turing
machine, or of a URM, or the transformations of lambda calculus, and so
forth, are "effectively computable" -- but that consensus is purely one
of intuition and experience, not logic. We look at the actions of
moving a tape head, writing a symbol, changing states, incrementing
registers, comparing two natural numbers, etc., and we can see how these
things could be realized in a simple, concrete way -- and so we're
willing to accept them as "effectively computable".
Of course, if you could find a model of computation A that everyone
agreed was effectively computable, and which you could show to be
strictly more powerful than a Turing machine (e.g., A can compute
anything a TM can, but you show a problem a TM can't decide which A
can), then maybe you could argue that the Church-Turing Hypothesis was
false. But so far, nobody has been able to do that.
Cheers,
-M
--
Michael J. Fromberger | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA
Robert A Duff
> But "undecidable" is _defined_ in terms of Turing Machines. If you wish,
> you may qualify "undecidable" as "Turing-undecidable", but I don't see the
> use in that until we have created an implementable super Turing machine.
Why "implementable"? I mean, Turing machines are not implementable,
so why should super-Turing machines be?
My computer has billions of bytes of memory, but Turning machines have
a lot more! And I doubt if my machine, or any other real machine, will
in fact run *forever*. ;-)
- Bob
tc...@lsa.umich.edu
Cagdas Ozgenc <co19@map's'pam.cornell.edu> wrote:
>I have this "feeling" that we may at the end show whether TM is the
>limit of computation without knowing what "computation" is.
>
>I will study some more and get back to you
You may wish to study the following paper.
http://arxiv.org/abs/math.LO/0209332
In my opinion there are some fundamental flaws in the above paper, but it is
less flawed than most papers of its type, and it is not a bad starting point
for discussion about physically building machines that exceed the power of
Turing machines.
Cagdas Ozgenc
<tc...@lsa.umich.edu> wrote in message news:aqdfqq$hu4$1...@galois.mit.edu...
> In article <aqd4nb$8v0$1...@news01.cit.cornell.edu>,
> Cagdas Ozgenc <co19@map's'pam.cornell.edu> wrote:
> >But the ultimate conclusion is the following: "a
> >machine cannot decide its own halting problem".
>
> Whoever is telling you that this is supposed to be the ultimate conclusion
> is mistaken. The proof certainly doesn't show that a machine can't decide
> its own halting problem. For example, consider the following class C of
> machines: The class contains only one element, namely the machine that
> always outputs "yes," and then halts. The machine in this class
successfully
> decides the halting problem for all machines in the class C.
It's my interpretation of Godel's Incompleteness Theorem in conjunction with
the proof of halting problem. The idea is as follows, please read carefully
before bulking at me:
Godel says a decent enough system will always be incomplete, meaning that
there will be undecidable problems, or proofs that cannot be conducted based
on the axioms of that system.
The proof of the halting problem tells us the following: "A system cannot
decide its own halting problem if the system is decent".
Now how do we know that the system is decent enough? A system is decent
enough to not be able to decide its own halting problem if it has
negation(inverting a boolean value encoded in any format) capability. If the
system does not have a negation capability we cannot conduct
diagonalization.
Some examples:
First order logic system (which clearly has a NOT operator) is incomplete.
An arithmetic system with only addition and neutral numbers cannot negate an
input, meaning that if TRUE is encoded with 1, and FALSE encoded with 2 can
negate TRUE (by incrementing the input by 1) but cannot negate FALSE because
it cannot do subtraction. This system is complete, and always halts.
The example system you are giving is not decent, because it cannot do any
negation.
> >// ******** here is the catch ***********
> >(1) There is an assumption in the proof that Q(x) is of the same
automaton
> >as S(x)
> >because we will be feeding Q to Q(x) and to S(x).
>
> No, the assumption isn't anything nearly as strong as that. All you need
> are things like "Q and S take the same forms of input (keystrokes at a
> keyboard for example)" and "when building automaton Q it is permissible to
> invoke automaton S as a `subroutine.'"
Ls = { <p> | p is a program that halts when its description is given as its
input }
Sorry, I will rephrase the argument as following: "Q is of same automation
type as Ps".
S is a program that decided Ls.
Q(x)
while(S(x));
}
Here is the proof that Q is of same automation type as Ps if halting problem
is undecidable.
Assume that encoding of Q does not overlap with any P in Ls (since if there
is an overlap that Q is of same type as P). We know that S halts on all
input by definition, then Q halts on all input if P does not halt on itself.
Now pick a P that does not halt on P. If encoding of P is equal to Q then
contradiction because Q halts on that case.
What does this mean? We had two assumptions:
(1) Enconding of Q does not overlap with any P in Ls
(2) There exists a program S that decides halting problem
Contradiction indicates that
(1) and (2) is false, which means (1) or (2) is false. To be able to
conclude that (2) is false, we have start off with that (1) is false at all
times, which means Q is in Ls, which also means that Q is of same automation
as P. Otherwise halting problem may or may not be undecidable depending on
Qs encoding.
So far, I think that I have done good enough work to show that to be able to
prove udnecidability of HP we need to assume that Q is of same automation
type as Ps.
Now the relation between automation types of Q and S needs some more work:
Since Q uses S a subroutine, S is encoded within the string of Q (perhaps by
appending S to Q, like R#S, where is R is the part of Q unrelated to S). We
need concat description of S into Q otherwise we cannot give the whole thing
as an input to Q.
Now R#S is a valid encoding for the Q type of automaton.
We will feed R#S into a machine of type Q and it will try to invoke S, and
see that it is not a valid program and Q will halt without a decision (it
will crash let's say).
Either we have to pick S to be same type as Q, or we need to figure out an
encoding such that S is blended within Q (not concatenated) magically. But
then what kind of a subroutine is that? To be able to go further one has to
define precise meaning of "subroutine" and how we encode subroutines...
tc...@lsa.umich.edu
Cagdas Ozgenc <co19@map's'pam.cornell.edu> wrote:
>The proof of the halting problem tells us the following: "A system cannot
>decide its own halting problem if the system is decent".
I think we agree that the proof (call it P) that the halting problem (for
TM's) is undecidable (by TM's) *as it currently stands* does not show that
"a system cannot decide its own halting problem if the system is decent"
(call this claim S).
I gather that your feeling is that P can be *generalized* to prove S.
It's certainly true, as someone else on this thread has pointed out,
that P can be generalized to classes of machines other than the class
of TM's. Whether these generalizations prove S---well, that's a matter
of opinion, because it depends on what "decent" means. I can declare
that anything other than TM's are indecent, and then P *does* prove S.
Conversely, if *everything* is decent, then S is false. It looks like
you're going through the exercise of trying to determine just how weak
a condition one can place on the system without breaking the proof.
That's not a bad exercise to go through, as long as you don't annoy
people along the way by claiming that there are errors or gaps in certain
proofs, when the reality is that they prove just fine what they're
*claiming* to prove. Just because they don't prove what you *want*
them to prove isn't their fault.
If you're hoping that P can be generalized to prove that no machine
that can be *physically built* can ever solve the halting problem for
all machines that can be physically built, then you're out of luck.
As we discussed, physical claims aren't decidable by pure logic. You
will have to introduce some non-mathematical principle like the Church-
Turing thesis.