Penrose Turing Argument

[69dodge]

Originally posted by Robin
But the argument only shows that A doesn't know, it says nothing at all about what B knows. After all if Penrose's reasoning is valid then it could also be used by B, but it would simply be prevented from reporting this by the artifice of A.

A computer program doesn't "know" things in the same way that a person does. A person might know something, yet refuse to tell anyone about it. What a computer program "knows", on the other hand, is, by definition, just what it reports. What other meaning could be given to the expression, "such-and-such a program knows such-and-such a fact"?

But do we even know that A does not stop?

If it never gives the wrong answer, then it doesn't stop. This is straightforward: if it did stop, then, by that very act of stopping, it would be giving the wrong answer.

Penrose's reasoning is that A does not stop because if it did stop it would not. That seems rather weak to me,

"If it did stop it would not" sounds slightly odd, I agree---it's not something that a nonmathematician would ordinarily say---but, strictly speaking, there's nothing wrong with it. If p implies not-p, we can logically conclude that p is false: it can't be true, because that would lead to a contradiction. On the other hand, there's no problem if it's false. So it's false.

the more correct conclusion would simply be that there is some algorithm that B cannot tell if it halts

Not just "some algorithm". We know which one. It's A. The only way we know that one exists in the first place is by explicitly constructing it. We construct an A, based on B, in such a way that B can't correctly say it doesn't halt. We know that B can't correctly say it doesn't halt, because if B did say so, it would halt and B's answer would turn out to be incorrect after all.

There are two possibilities: (1) B says that A doesn't halt; A halts; B gave the wrong answer. (2) B doesn't say that A doesn't halt; A doesn't halt; B failed to give the right answer.

This is what I am trying to show with my 'Dunbar Conference' example - that a human mathematician working to the same constraints will also not be able to signal the correct answer.

Yes, I agree. That example is perfect.

 

[69dodge]

Originally posted by sorgoth
Well, I read the posts pertaining to the main argument a couple of times, and one thing I don't understand is: Even if it's impossible for one machine to determine if it will ever halt (Because of the paradox...it halts if it never halts), what's to stop you from simply using another TM to halt when it determines the other will never halt?

It's possible to have a TM that correctly determines whether some other TMs halt. But no TM can correctly determine whether all other TMs halt. The reason is that, given any proposed determiner, we can always make another TM that asks it, "Ok, wise guy, am I going to halt or not?", and then goes and does the opposite.

 

[LW]

Reading my own posts in this thread again, I note that I have managed to be more confusing that I should have. This is because I've written too quickly and with the assumption that the reader knows technical definitions of the terms.

Since I don't really have time to explain the things better (our basic theory of computation course has 12 2-hour lectures), I can only strongly recommend the interested readers to pick up some textbook on the subject. The Sipser's book that I mentioned above is good. Another old favorite is Lewis and Papadimitriou's Elements of the Theory of Computation (second ed, that is, the first edition is very heavy reading).

However, there is still one matter that I need to clarify because I haven't said it explicitly, yet:

The standard way to define computations is using Turing machines, though some old books use recursive functions, string rewriting systems, lambda calculus, or some other essentially equivalent formalism to do so. All these formalisms have the inherent limitation that they can be seen as operating only in the domain of natural numbers. But they have the advantage that they can be physically realized (within the confines imposed by the finite nature of our computational resources).

So, you could say that the list C₀, C₁, ... contains all computations, since that is the list of computations that are in some sense physically realizeable.

But this would not be accurate for two reasons: (1) The mathematicians have designed computation models that are not realizeable in real life, such as systems that work on arbitrary real numbers or systems using oracles. These systems have also well-defined computations and their properties can be examined even though they exist only as theoretical abstractions. (2) The vast majority of entries C_i in the list are not realizeable in practice because the programs are so large that they cannot be stored in any physical media.

And what comes to representing irrational numbers using natural numbers, Georg Cantor proved that impossible already in 1874.

 

[Thomas]

Assuming, of course, that any computation can give only YES/NO answers. If we allow "I don't know" as a result, then the above doesn't hold anymore.

 

[Robin]

So, you could say that the list C0, C1, ... contains all computations, since that is the list of computations that are in some sense physically realizeable.

But this would not be accurate for two reasons: (1) The mathematicians have designed computation models that are not realizeable in real life, such as systems that work on arbitrary real numbers or systems using oracles. These systems have also well-defined computations and their properties can be examined even though they exist only as theoretical abstractions.

Does C include abstract, theoretical or black box computations? Absolutely!

If a mathematician has a way of representing it then it can be represented by natural numbers. If a mathematician can draw conclusions about it then those conclusions can be represented as natural numbers. Is there an algorithm that can represent the process by which mathematicians can draw conclusions? We don't know but potentially there is.

If you think about it C will, by Penrose's definition, contain abstract computations (since A is supposed to encapsulate methods used by human mathematicians and human mathematicians generally draw conclusions from abstract computations).

For example look at the very simple abstract computation x * y, where x and y are any irrational numbers. There is certainly enough information here to know that the computation halts. All represented with natural numbers. And let's face it there is always enough information for a Yes/No/I don't know answer.

The list is not restricted to physically realizeable computations, the sum of a divergent series for example is not physically realisable but we have enough information to know that it does not halt.

 

[LW]

Does C include abstract, theoretical or black box computations? Absolutely!

Three words:

You. Are. Wrong.

Quoting the quote posted by 69dodge:

(To be explicit, we could, if desired, take this ordering as being provided by the Turing‑machine numbering given in ENM, so that then the computation Cq is the action of the qth Turing machine Tq acting on n.)

Note the reference to Turing machines. Turing machines have a precise formal definition [*]. That definition doesn't involve real numbers or oracles or any other similar constructs. It is very clear that Penrose intends the C_i list to be based on some formal computation system. If you fail to accept that, well it's your problem.

[*] I intended to include a link to a definition here but since I noticed that the Wikipedia definition is subtly incorrect, and the few other links that I clicked through were either word-to-word copies of Wikipedia or used non-standard notations, I decided against it. Read some textbook if you are interested, those tend to get the definitions right.

If a mathematician has a way of representing it then it can be represented by natural numbers.

There are quite a lot mathematical constructs where the mathematician doesn't have a way of representing the individual elements of the construction.

The list is not restricted to physically realizeable computations, the sum of a divergent series for example is not physically realisable but we have enough information to know that it does not halt.

Why limit that to divergent series? Computing the sum of any infinite series term-by-term never stops.

 

[LW]

I intended to include a link to a definition here but since I noticed that the Wikipedia definition is subtly incorrect.

Better change that to "misleadingly incomplete".

 

[Donks]

Better change that to "misleadingly incomplete".

Here's a wild idea. How about you correct it? That's the point of Wikipedia, you know?

 

[Robin]

Originally posted by LW
Note the reference to Turing machines. Turing machines have a precise formal definition [*]. That definition doesn't involve real numbers or oracles or any other similar constructs. It is very clear that Penrose intends the Ci list to be based on some formal computation system. If you fail to accept that, well it's your problem.

Of course Penrose intends the C list to be based on some formal computation system, that is the whole point of the exercise.

However formal mathematics can be expressed by some Turing machine (in fact it was the original intention that they should), although there is an incompleteness problem here too, as discussed in Turing's original paper on the halting problem.

What you appear to be saying that Penrose has put up A as a candidate for the encapsulation of the methods human mathematicians use, and then has carefully ensured that it works in a way that human mathematicians don't.

There are quite a lot mathematical constructs where the mathematician doesn't have a way of representing the individual elements of the construction.

So what do they do? Leave a blank space in their published documents? I already addressed this point about black boxes. You are going way our of your way to avoid my point - if it can be expressed mathematically then it can be expressed as natural numbers.

Why limit that to divergent series? Computing the sum of any infinite series term-by-term never stops.

And this is my very point. Take the algorithm { s=0;i=1; while (true) {s=s+1/i; i++; } }. It would be true to say that this algorithm never stops. But we know that there is a finite answer to this sum but it is still inaccurate to say that the algorithm stops since clearly it doesn't. So if you were to examine this algorithm as a dumb as dirt algorithm you would get one answer. If you were to examine the purpose and resolve it mathematically you would get another.

Take one of Penrose's own example: Find an odd number that is the sum of n even numbers. Does this computation halt? It depends - if a human mathematician were to attempt the computation it would halt straight away. If you designed an algorithm to do a straight line seach it would never halt. Both would return the same answer. So is it improbable that some algorithm could resolve it the same way that a mathematician would?

So clearly if A is to represent the methods mathematicians have of finding if a computation halts then C must contain some encoding of the types of problems a mathematician would look at.

 

[Robin]

Originally posted by LW
Turing machines have a precise formal definition [*]. That definition doesn't involve real numbers or oracles or any other similar constructs.

That definition doesn't include integers either. So a TM cannot operate on integers?

 

[Robin]

Just for context here is an HTML rendition of Turing's paper that defines computability and the extent of computable numbers, computing machines (ie Turing machines), the (edit out)halting(/edit out) decision problem and the use of Turing machines to represent formal mathematics:

http://www.abelard.org/turpap2/tp2-ie.asp#section-11

In particular note that Turing definitely intends that TM's can represent formal mathematics and abstract computations.

(Note I had misremembered the exact paper I was referring to in an earlier post).

 

[Robin]

Originally posted by 69dodge
A computer program doesn't "know" things in the same way that a person does. A person might know something, yet refuse to tell anyone about it. What a computer program "knows", on the other hand, is, by definition, just what it reports. What other meaning could be given to the expression, "such-and-such a program knows such-and-such a fact"?

I was being imprecise. What I meant was that if A is based on some other "yes/no/I don't know" function then that function could conceivably produce a trace of the reasoning it follows which might be similar to the reasoning Penrose follows.

If it never gives the wrong answer, then it doesn't stop. This is straightforward: if it did stop, then, by that very act of stopping, it would be giving the wrong answer.

Yes, I was wrong there, I realised it as soon as I posted the Dunbar thing. I had realised that (M) was the reductio ad absurdum tautology, but I had made the most basic logical error possible in (H) by assuming that a->~b then ~a->b. Of course the alternative is not only that C does halt, but that A is unable to determine if C halts.

 

[LW]

That definition doesn't include integers either. So a TM cannot operate on integers?

It includes a finite alphabet and an unbounded computation tape => it can represent integers.

Suppose that we want to express the integer '5'. The simplest thing to do is to include '0' in the alphabet of the machine and then use the string:

|0|0|0|0|0|

to do so. (where | | denotes each tape cell.)

If you went wild and decided to use a binary encoding, then you would include both '1' and '0' in the alphabet and use:

|1|0|1|

Using the above unary encoding you could define a TM to add two numbers by simply concatenating the strings representing them. In the binary number case you have the exercise 10.2 of our basic course on computation theory. [Hint: put the least significant bit first and use a 3-tape machine]. You can do multiplication by transforming it into series of repeated addings, but be warned that depending on your approach and the exact formalization of Turing machines, it may take a full A4 paper to draw that machine [BTDT].

No such representation is possible for reals or oracle machines.

[An aside: by far the most ingenious way of representing integers using some other formalism that I've seen is in Badendregt's Lambda Calculus. If you an access to that book (it is old and horribly expensive), I recommend reading it, it is truly mindblowing.]

 

[LW]

Of course Penrose intends the C list to be based on some formal computation system, that is the whole point of the exercise.

So, why do you keep insisting that it must contain something that is not possible within that formal system?

What you appear to be saying that Penrose has put up A as a candidate for the encapsulation of the methods human mathematicians use, and then has carefully ensured that it works in a way that human mathematicians don't.

In the part of the text you quoted, A was "a sound set of computational rules ascertaining that some computations do not halt" with the idea that it may halt only if the examined program does not. No human mathematician would ever work that way. Human beings just don't enter infinite loops.

In my opinion, trying to formalize the way how mathematicians think is pointless. Not because I believed that there is some theoretical barrier. I have more practical reasons: we just cannot construct the model. A mathematician doesn't live in isolation, just churning out computation steps of some well-defined program. The model would have to include the interactions between mathematicians and also between mathematicians and Real World (tm). We won't have tools to do such modeling in my lifetime, and probably never.

So what do they do? Leave a blank space in their published documents?

[M.A. Numminen's voice]
Wovon man nich sprechen kann, darueber muss man schweigen!
[/M.A. Numminen's voice]

They don't write papers where they would need to address all real numbers individually.

You are going way our of your way to avoid my point - if it can be expressed mathematically then it can be expressed as natural numbers.

We are seriously talking beside each other.

Mathematics as a science is pure abstract symbol manipulation. Nothing else.

But mathematicians like to pretend that there exists some sort of mathematical universe where the mathematical objects exist. For example, they like to say things like "{ 1, 2, 3 }" is a set of three objects 1, 2, and 3, instead of saying "{ 1,2,3 }" is a string consisting of the symbols '{' ,' ', '1', '2', '3', ' ', '}', which it strictly speaking is. Or, more strictly speaking, in this case it really is a bunch of electricity levels in the computer memory.

Now, mathematicians have defined this mathematical universe so that it is not possible to talk about all its elements individually, even if we pretend that natural numbers really exist in our world. Which they don't.

So, you are speaking about mathematics as symbol manipulation. I am mostly speaking about the make-believe mathematical universe.

 

[Robin]

We are seriously talking beside each other.

I agree so let's recap. I said:

Robin Another thing about this is that it is easy to convert any value to a natural number and vice-versa - any integer, real number, imaginary number etc.. OK then so what is the difference between the set of all possible computations that can be performed on natural numbers and the set of all computations full stop?

You corrected:

LW Not any. Especially no irrational real number or imaginary number can be converted into an integer.

I amended my original statement:

Robin I should have said that any computable value can be converted into a natural number.

and then pointed out that your statement was not true either, that computable irrationals and imaginary numbers could be represented by natural numbers and that non-trivial calculations could be done on these with infinite accuracy.

I can't imagine why it should have gone on from there. But since it did I pointed out that all formal mathematics could be represented using natural numbers - you appeared to have some objection to this, why I don't know because as you said yourself:

Mathematics as a science is pure abstract symbol manipulation. Nothing else

Exactly - and every symbol can be represented by a natural number. If there is nothing else then all formal mathematics can be expressed by natural numbers.

And since you are clearly trying to imply that I know nothing about Turing machines I cited Turing's 1935 article "ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM" in which he was saying many of the same things about computable numbers and representing formal mathematics with Turing machines. I think that we might suppose that Turing knows a little about Turing machines.

Since Penrose's definition "a computation on natural numbers" could be said to include examinations of algorithms to see if they halt, then it is hardly a stretch to say that it might include a Turing formalisation of a theorem or a proof. In which case it would clearly include black boxes, abstract and theoretical functions. In fact might reasonably be said to encompass all of mathematics.

In the part of the text you quoted, A was "a sound set of computational rules ascertaining that some computations do not halt" with the idea that it may halt only if the examined program does not. No human mathematician would ever work that way. Human beings just don't enter infinite loops.

So let's not enter an infinite loop then. You have simply restated my original objection - a human mathematician under the same constraints would be as stumped as the algorithm. I tried to illustrate this with the Dunbar thing.

I personally don't think that there is a knowable algorithm to describe the way mathematicians reach conclusions - I just don't think that Penrose's argument has proved this.