Introduction

In The Emperor's New Mind [1] Roger Penrose claimed that true artificial intelligence (AI) in computers - machines that execute algorithms - is impossible. He argued that the human brain must exploit a type of physics that he described as 'non-computable' and that a device not built to do this has limitations that a non-computable device may not share.

Penrose, like John Searle, suggests that programs cannot think, but their views differ. While Searle accepts that the behaviour associated with consciousness could be imitated, but argues that such behaviour does not necessarily imply consciousness, Penrose claims that we cannot even obtain the right behaviour from a computer because its reliance on computation will give it limitations not shared by our allegedly non-computational brains.

Penrose has attempted to provide a mathematical proof to support his argument. The proof appears to have been inspired by Godel's incompleteness theorem [2] and is in his 1994 book Shadows of the Mind. The proof attempts to show that algorithms can never show knowledge of a certain fact that can be known by a human brain.

Penrose's proof, known as the Godel-Turing proof or the Godelian proof, considers a limited subset of algorithms that are required to output answers in limited ways. The problem presented to one of these algorithms in Penrose's proof traps the algorithm in a situation in which the rules that state how it is to output its answers prohibit it from answering correctly without contradicting itself. This does not show anything profound about algorithms, but is simply an artefact of the type of question being asked and the way in which the algorithm is required to respond. Penrose may think that he has adequately answered such an objection, but his answer is flawed and does not stand up to examination. His proof is invalid, as this article will demonstrate.

The scope of this article will be restricted to refuting this proof. I shall not be attempting to refute Penrose's entire case or discussing the merits of his suggestion that non-computable physics exists and is needed to explain human abilities. Penrose's proof is an important part of his argument against the feasibility of computational AI, but I leave it to the reader to consider the strength of his case after failure of this proof.

Penrose's Proof

The attempted proof [3] is in Chapter 2 of Shadows of the Mind and can be summarised as follows:

1. For any number n we can consider all possible computations that can act on n and number them C₁(n), C₂(n), C₃(n) and so on.
2. Consider a computation A. The purpose of A is to determine if another computation does not halt. A is given two parameters, q and n and the purpose of A(q,n) is to determine if C_q(n) does not halt. This is done as follows: If A(q,n) determines that C_q(n) does not halt then A(q,n) halts to signify this. A(q,n) does not halt for any other reason: if A(q,n) determines that C_q(n) halts, or if A(q,n) is unable to determine whether or not C_q(n) does not halt then A(q,n) does not halt.
3. Suppose we select n and q such that q=n? This means that we now have:
   If A(n,n) halts then Cn(n) does not halt.
4. Now A(n,n) = C_k(n) - that is to say that when A(q,n) has both parameters the same then there must be an algorithm in the collection C₁(n), C₂(n), etc which is equivalent to A(n,n). Whatever this algorithm is, we call its number k.
5. Consider the case n=k. In such a case:
   A(k,k) = C_k(k).
6. From step 4 it follows that:
   If A(k,k) halts then C_k(k) does not halt.
   By the identity in step 5 we can state:
   If C_k(k) halts then C_k(k) does not halt.
   This proposition implies its own negation. We can therefore state:
   C_k(k) does not halt.
   As A(k,k) = C_k(k) we can also state that:
   A(k,k) does not halt.
7. We know that C_k(k) does not halt. However, the algorithm that is supposed to tell us that C_k(k) does not halt fails to tell us this. The only way that it could tell us would be if A(k,k) stops, but A(k,k) cannot halt to tell us that C_k(k) does not halt because they are the same algorithm; that is to say they are the same Turing machine initial state. This means that we know something that A(k,k) cannot tell us - that C_k(k) does not halt.
8. A(q,n) is an algorithm for determining if computations do not halt, but suppose that A(q,n) comprised every knowable and sound algorithmic method for determining that a computation does not halt. This means that we know something that even the most capable algorithm cannot know - that C_k(k) does not halt.
9. From this it follows that the human mind is not a computer.

One thing needs to be made clear here. Penrose's algorithm A(q,n) is supposed to tell us when it has determined that a program that it is analysing will not stop, but it involves a bit more than this. Each 'run' of Penrose's algorithm considers the program with a specific input. There are two ways of viewing this:

One way is to view the input into the program that is being analysed as being hard-wired into the program so that when we say that Penrose's algorithm is analysing a program C_k(n) we regard C_k(n) as a distinct program for each value of n.

Another way is to regard Penrose's algorithm A(q,n) as not analysing just programs, but actually analysing the initial state of a computer and telling us if it determines that it will not halt. C_k(n) is actually a Turing machine instruction tape, or any similar sort of computer system you care to imagine, set up in a certain way and we could say that A(q,n) is actually determining the consequences of setting up a machine in this way.

None of this discussion of distinguishing between programs and initial states is intended as an attack on Penrose's reasoning: the issue is purely one of semantics and he has explained his proof quite adequately in this respect and makes it clear that we are supposed to be thinking about machine initial states. In this article I shall often talk about Algorithm A(q,n), or some other algorithm, analysing 'programs', and I would ask the reader to accept that my use of words like 'program' will often refer to programs with specific inputs or to the initial state of a machine (whichever you prefer): it should be obvious what is meant, but this makes it easier to avoid cluttering the article up.

A good summary of Penrose's proof is given by Searle in The Mystery of Consciousness [9].

Similarity with Lucas's Argument

Penrose's Godelian approach has some similarities to an earlier argument made by John R. Lucas [10, 11]. Any computer program is a formal system and Lucas argued that there is certain information, relating to its own formal system, that a program cannot determine and output and that humans are not limited in this way.

Lucas's argument was discussed by Douglas R. Hofstadter in his book Godel, Escher, Bach: an Eternal Gold Braid [12], in which Hofstadter mentioned a particularly interesting argument against Lucas by C. H. Whiteley. Whiteley accepted that Lucas could show that there are certain truths which could never be asserted by computers, but he viewed this as analogous with a trivial trick in a word game, rather than indicative of any differences between computers and humans. As an example Whiteley proposed this statement:

Lucas cannot consistently assert this sentence.
(i.e. Lucas cannot say that this sentence is true without contradicting himself.)

A consideration of this sentence shows that if Lucas asserts it then he is saying that he cannot assert it while he is actually asserting it so if he asserts it he is being inconsistent. That is exactly what the statement is claiming so Lucas's inability to consistently assert the statement shows that it is true.

As the statement is true I do not have any concerns about asserting it and I shall now do so:

Lucas cannot consistently assert this sentence.

I can assert it. Lucas cannot. Surely my brain must have capabilities that Lucas's lacks? Could I not argue from this that my brain works in some radically different way to Lucas's brain? Such an argument would be foolish: the problem here is that a word game like this could just as easily be used on me. Lucas could say, 'Almond cannot consistently assert this sentence,' and I would be just as stuck. A word game like this would show nothing about our mental limitations. Whiteley's argument is that Lucas is effectively doing the same thing, except with mathematics instead of words.

Penrose's argument is slightly different to Lucas's, but in this article I shall show that it amounts to nothing more than playing a mathematical version of this sort of trivial word game against a computer and is still vulnerable to this sort of refutation.

A Reason to Be Concerned About Penrose's Proof

A danger sign regarding Penrose's proof is actually in Shadows of the Mind.

If you or I were given some task that we lacked the ability to complete then we could attempt to behave randomly in the hope that we could complete the task. I can certainly not write as well as Shakespeare, but if I typed random sequences of words it is at least mathematically possible, if extremely unlikely, that I may get lucky and produce a sonnet as good as any of Shakespeare's.

Penrose accepts that a computer could duplicate human behaviour and appear to be intelligent/conscious by chance [4], but he makes it clear that is all it is: the intelligence would be fake, just as my production of a Shakespeare sonnet by chance would not indicate any real capability. Penrose states:

We can say that this random faking is possible in almost any reasonable test of capability. Whatever test of your intellectual capability society may inflict on you, unless speed is an issue maybe (for example, if I challenged you to write down the square roots of one million numbers in 1 nanosecond), you could get lucky and produce the correct answers.

This is not the case with the strange game that Penrose has set up for algorithm A(q,n). Penrose's proof attempts to show that it is logically impossible for A(q,n) to give the correct answer. Even if A(q,n) attempted to 'guess' the correct output, without any real attempt to solve the problem, logic prohibits it from outputting the correct answer: it is simply impossible.

This is inconsistent with Penrose's acceptance that a computer could get lucky and produce human behaviour. For situations that are easier to imagine, such as conversing as a human does, recognising objects or writing poetry it is clear that Penrose has to accept the possibility of random behaviour producing the correct output in a trivial way, but if that is the case why should the situation of A(q,n) be any different?

Imagine that you were asked to take a written test of your intellectual capabilities that met these standards. Imagine that you felt that you did not know how to answer the questions in the test and decided to guess the answers and then realised that, due to some aspect of the test, even this would not suffice - that no matter how you moved your pen on the paper and even if you did it randomly, the questions made it mathematically impossible to write the correct answers. Should you not conclude that you were the victim of some sort of game or trick and should you not refuse to accept that anything about your reasoning abilities was really being demonstrated?

This inconsistency between his acceptance that machines could behave like us by chance and his insistence on the impossibility of machines producing certain outputs suggests that, though not by Penrose's intention, some sort of trick is involved in what Penrose is doing to his algorithm A(q,n).

An objection could be made against this on the basis that random numbers generated by computers are regarded as pseudo-random rather than random. Regardless of whether or not such a distinction is ontologically meaningful, this is irrelevant: there is no reason to presume that pseudo-random behaviour should not be adequate and in the worst scenario we could use come conventional random process to construct an algorithm and place random information in it for this purpose. We do not really require the algorithm itself to be random and for any reasonable test that we can imagine there should be a sequence of actions that could be output by some algorithm which may or not be generating pseudo-random results internally. In this respect the random process of creating an algorithm that I just mentioned is, in reality, randomly selecting an algorithm from the list of all possible algorithms in the hope that it happens to behave correctly.

Limited Vocabulary of the Computer

If you or I were asked if a particular program may stop then we may answer in a number of ways. We may answer with 'yes', 'definitely', 'positive', 'no', 'negative', 'I am sure it wouldn't' or with any of a number of phrases that clearly communicate our opinion about whether or not the program would halt. The computer in Penrose's argument has no such freedom. The only way in which it can communicate its results is by stopping to indicate that the program that it is analysing does not stop or by not stopping to indicate, effectively, that the program it is analysing does stop. If the computer never stops it does not necessarily mean that it has determined that the program that it is analysing does stop: it could equally well mean that it has been unable to determine whether it stops or not.

Giving the computer such a limited vocabulary could be viewed as less than ideal. If the computer determines that the program that it is analysing does stop it can never communicate this to us with certainty. Penrose could validly reply that his intention is to disprove the idea that algorithmic AI is possible and not to construct particularly useful algorithms for determining whether other algorithms halt.

The issue of vocabulary is, however, still important with regard to Penrose's proof and it will be a big feature of this article. I will use the term 'vocabulary' often and it will simply mean the way in which the computer signals various results of its processing. The particular vocabulary chosen by Penrose is simple and involves:

1. halting to show that the program being analysed (that is to say a Turing machine with the initial state under consideration) does not halt.
2. not halting for any other reason other than that just stated.

Analogous Word Games Against Humans

I wanted a word game which mirrors aspects of Penrose's argument, but one that is easily understandable in English. I came up with a game that has these rules:

1. We have a list of every yes/no question that can be asked. Every such question has a number.
2. You will be given the number of the question that needs answering. We do not expect any great feats of memory here so you will be given a lookup table that will tell you, for any given question number, what the question is.
3. If you are asked a question from this list you are required to answer with 'yes' or 'no'. You are required to be as consistent as possible in your answers.
4. It is permissible for a question to refer to another question.
5. Self-reference is allowed: it is permissible for a question to refer to itself.

Let us make up some questions. If the shorter questions had smaller numbers and the longer questions had larger numbers then the numbers of most interesting questions would be very large indeed. I shall ignore this and just make up the numbers for some example questions. The English language makes it hard to construct questions without any ambiguity so I shall ask the reader to pretend that these questions were stated more precisely: the meaning will be obvious in any case.

Question 1: Is it true that 2+2 is equal to 4?

Question 2: If you were asked Question 1 while playing this game, would you answer 'yes'?

Question 3: If you were asked Question 2 while playing this game, would you answer 'no'?

and now, the important question:

Question 4: If you were asked Question 4 while playing this game, would you answer 'no'?

Let us look at the answers that you should give to these questions.

Question 1 is simple enough: 'Is it true that 2+2 is equal to 4?' Yes, it is, so you should answer 'yes' to this question.

Question 2 simply asks if you would answer 'yes' to Question 1. You should answer 'yes' as you know that the answer to Question 1 is 'yes'.

Question 3 asks if you would answer 'no' to Question 2. You should answer 'no' as you know that the answer to Question 2 is 'yes'.

Question 4 is more interesting: it is self-referential in that it asks what you would say if asked Question 4. Now, if you would answer 'yes' to Question 4 then you are being inconsistent, as your answer actually claims that you would reply 'no' to this question. If, however, you reply 'no' to question 4 then you are also being inconsistent. Your answer indicates that you would not answer 'no' to Question 4, yet this is exactly what you have just done!

It may seem that Question 4 has no answer, but this is not true. If you are asked Question 4 then you cannot consistently answer it; however, the fact that you cannot consistently answer it means that you would not say, 'No,' to this question - your failure to give an answer prevents you from doing it. As Question 4 is asking if you would say, 'No,' then the answer to Question 4 is 'no'. The problem is not that there is no answer. When the question is directed at you I can state what the answer is. You, however, cannot articulate this answer without being inconsistent.

What if I asked you Question 4, waited for you to fail to answer, announced that the correct answer was 'no' and then pronounced the clear superiority of my mind over yours - maybe even going so far as to suggest that this superiority is so profound that my brain must rely on some type of physics to which yours does not have access? Such a claim would be a fallacy because I have done nothing beyond playing a word game, the rules of which effectively ban you from answering, yet this is what Penrose has done in his proof.

In Penrose's proof the algorithm A(k,k) is analysing another algorithm to determine if it will not stop and that other algorithm is identical to A(k,k) itself. The algorithm is effectively being asked a very similar question to the one being played in this word game and the question being asked in Penrose's proof is something like this:

If halting means 'no' and not halting means 'yes' or 'don't know', if you were asked this question would you halt?

or to put it in a slightly more detailed way:

If halting means 'no' and not halting means 'yes' or 'don't know', would a Turing machine that had the same initial state as you halt?

Penrose's proof, therefore, is nothing more than a mathematical form of this sort of pointless word game and tells us nothing about the relative capabilities of computer programs and human brains.

Objections can be made to the sort of word game described here. While I do not intend this word game, or my version of the question being asked of the computer in Penrose's proof, as described above, to be an absolute refutation of Penrose - that will come later - I shall deal with some obvious objections:

Objection 1: Your word game involves self-reference, which is invalid.

A question which asks how you would answer it is clearly self-referential. Questions such as 'Does 2+2 equal 4?' require you to find the correct answer to the question, but with a self-referential question like the one above you really need to arrange your behaviour to be self-consistent rather than actually try to find the answer. Some readers will find this self-reference unacceptable. I do not have a problem with it, but for any readers who do then we need not even proceed further. I have only used self-reference because Penrose's proof involves the same sort of self-reference when an algorithm is effectively asked if it would stop when analysing itself. Penrose acknowledges the issue of self-reference in Shadows of the Mind, stating:

The use of self-reference in my example, and in my word game version of his question, only mirrors that of Penrose. If my use of self-reference invalidated my case it would also invalidate Penrose's, making my argument redundant anyway.

Objection 2: Your word game assumes that the user has to play consistently all the time. A computer programmed to play word games like this may need to follow such a program slavishly, but a human could choose not to answer the same way each time.

Does this provide any loophole for a human in Question 4? An attempt to exploit such a loophole could involve answering 'yes' when the question is asked a first time and 'no' when it is asked a second time. The excuse for this behaviour would be to say that the question did not state which instance of itself it related to and that when it was asked the first time the answer should be taken to mean 'Yes, I would reply "No" to the second instance of this question' and the second time the question was answered the answer should be taken to mean, 'No, I would not (and did not actually) reply "No" to the first instance of this question'. The idea here is that humans can vary their actions and, by answering the question differently each time, maintain overall consistency. Conversely, the algorithm A(q,n) in Penrose's proof is not able to play such a trick to maintain consistency.

The logic involved in such an approach is not really useful. All that is being exploited here is some vagueness in the question and a difference between the mechanics of the human brain and Penrose's algorithm A(q,n).

The vagueness being exploited is that the question does not explicitly deal with the issue that humans could give different responses for each instance of the question and fails to specify which instance of the question it relates to. A simple way of fixing this is to make the question refer to all instances of itself by wording it in a way like this:

Question 4: If you were asked Question 4 while playing this game, would you ever answer 'no'?

This sort of question now demands that all answers are the same. It is not possible for it to be both true that you answer 'no' sometimes and false that you answer 'no' sometimes so if anyone gives two different answers while playing the game then he/she is being inconsistent. If you are asked this question you are set up for a slightly better trap now. Saying, 'Yes,' requires that you always say, 'Yes,' to be consistent, yet your very act of giving 'yes,' as an answer is a claim that you sometimes answer 'no'. Saying, 'No,' on the other hand also gets you into trouble because by doing so you are claiming never to do it while you are actually doing it.

Someone could argue against this by saying that it allows consistent play without any problem, provided that you have played or will play other games that are inconsistent. In other words, I can still play the game consistently by saying, 'Yes,' and satisfy any Penrose vs. AI enthusiast judges who happen to be present, and simply give the required 'no' answer, the one that is inconsistent and the occurrence of which is required by my 'yes' answer, on another day. This is hardly satisfactory. The word game still achieves its purpose of forcing you into inconsistency at some time, even if you can evade the inconsistency in isolated games.

A further loophole could be sought by adopting a 'prevaricative' strategy. In this approach you would answer 'yes' every time. The fact that you have answered 'yes' is an admission that you would say, 'No,' on one or more occasions. When are these occasions? Simple: in the future - and you make sure that they stay in the future. You are admitting to an inconsistent answer that you must give, yet you simply postpone the giving of that answer indefinitely. Some readers may notice a slight resemblance between this idea and Anthony Duff's 'mixed wager' approach to Pascal's wager [13].

I could alter the question to preclude a prevaricative approach and here is one example of how it could be done:

Question 4: If you were asked Question 4 while playing this game, and it was the first time that this question had been asked of you while playing this game, would you answer 'no'?

This example attempts to remove any ambiguity about the instance of the question to which it refers. Some readers may be disturbed by what looks like even more self-reference here: the question refers not only to itself, but goes further to refer to this particular instance of itself - at least it does the first time that it is asked - but we should not worry about this unduly: it is self-referential to start with anyway, just like the problems being presented to Algorithm A(q,n) by Penrose. The question will cause inconsistency the first time that it is used only, so it is a 'one-shot' question.

Objection 3: Self-reference may be valid but there are problems with your analogy. The questions that Penrose asks of his algorithms do not explicitly say 'you'. They do not say 'Will you not stop?', but rather 'Will such-and-such an algorithm not stop'. This means that the questions are exactly the same whether being considered by A(q,n) or by a human, so that all that is needed is for a human to show his/her natural superiority. Your question (Question 4: If you were asked Question 4 while playing this game, would you answer 'no'?) explicitly refers to the you who is the target of the question. Suppose that you ask me that question. Naturally I shall fail to answer, but you can hardly gleefully show that you can answer and show your cleverness. The question is not aimed at you: it is aimed at me. I am the you in the question. You may know what the answer is that I should have asserted, yet it does you no good: nobody asked you. This is not just an issue of socially niceties! Because the question refers explicitly to me it is incoherent for you to answer it and you can never demonstrate your greater abilities by answering it. This does not apply to Penrose's arguments. Yes, what you just showed us was a pointless word game - and an irrelevant one.

The mere fact that I know the answer that you should give, while watching you struggling to assert it should be enough. If it is not enough we can easily rectify this by making the self-reference les explicit. We can alter the question so that it becomes one which is just as meaningful to both of us. As an example, if your name is 'John Smith' we can make the question:

Question 4: If John Smith were asked Question 4 while playing this game, would he answer 'no'?

A question like this would be meaningful to anyone, yet John Smith would have trouble with it.

Objection 4: But surely that could be any John Smith. Could John Smith seek refuge in claiming that the question considers a different John Smith?

We could make the question refer to any John Smith:

Question 4: If anyone who is commonly known as John Smith were asked Question 4 while playing this game, would this person answer 'no'?

There! Now we mess the brain of any John Smith up.

If this is not desirable, possibly because it seems a bit general or vague, we could always make the description more specific; for example:

Question 4: If John Smith, who lives at 21 Arkady Road, Bridgeport, Nottingham, United Kingdom, Earth were asked Question 4 while playing this game, would he answer 'no'?

If we keep going there will be little doubt that the question applies to you and only you. Even worrying about this is a fallacy, however. Penrose's question identifies an algorithm that satisfies certain criteria (obeying the rules about what the algorithm C_q(n) is for given values of q and n). Any algorithm that satisfies these criteria can be considered to be the subject of the question. As it happens there is only one unique algorithm that does satisfy it, but this is not particularly important and has no relevance to the attempted proof. When I describe a person who is the subject of a question I also specify certain criteria and anyone who satisfies these is in the set of subjects to which the question refers. Whether there is just one or many is not relevant.

Objection 5: It is relevant. You seem to be saying that the question takes the form: Would any member of Set X (where we can presume that Set X is specified in the question) answer 'no' in response to this question? That is assuming that all members of Set X behave in the same way, but what if different members of the set could behave differently? The question would become incoherent.

We could always use techniques like the ones we used earlier, for example:

Question 4: Would anyone called John Smith answer 'no' in response to Question 4?

This difficulty only appears to arise because the description of an algorithm is abstract and refers to one algorithm, whereas descriptions of physical objects in the real world refer to sets of objects that meet the criteria of the description. It is not really too important, however: when we expect to discuss real objects - and that is what this whole debate is about: whether or not intelligent machines can be constructed - then that algorithm would, in fact, describe a set of real machines that behave according to that algorithm. There is no obvious reason why we could not do the same with a human: if we could get an accurate enough description of the brain we could then ask:

If your brain were in this state just after hearing this question (and details of the state of a brain would be given here) in an environment which takes this form (and details of the environmental influences would be given here) would you answer 'no' in response to this question?

We would then make sure that the brain state described in the question is the state that the person's brain will actually be in at the end of the question. We would need to control the environment and we do have the problem of how the person knows he is being asked about his own brain state, but the principle itself is sound.

Some readers may think that issues such as chaos or non-determinism are important here and argue that some sort of description of a human brain would never demand a specific future behaviour of it. I do not think this is relevant, but if it were machines could easily be provided with this and if that is our refuge against the prospect of machine intelligence we are rather desperate.

Objection 6: If I am asked the question then maybe I cannot answer while maintaining my consistency: I can accept that you could put a question in some form that would force this on me. That is only part of your case, however. To accurately mirror Penrose's argument, you need to show that a proof can be constructed that you can answer the question while I cannot. Let us suppose, though, that I resolved not to try to play the game and not to answer consistently. I would lose the game, but so could you: you could never know what I would do in such circumstances and you could not know that I would or would not say, 'No,' with certainty. In a sense we would both lose and you would not have the easy win that we have against Penrose's algorithm A(q,n). This makes your analogy flawed.

Trying to use human characteristics of uncooperative behaviour and inconsistency does not help against the point that I am making. If it is these that make my argument fail then it must be these that separate us from computer programs: Penrose is not attempting to make such a case. It is unreasonable to expect A(q,n) to be inconsistent or uncooperative because it is required not to be by Penrose's proof, so it would hardly be a fair comparison.

If we liked we could imagine all kinds of extreme ways in which a human could be altered to force him/her to be cooperative, and to try his best to be consistent, without sacrificing his/her abilities with regard to questions like this. We should also be able to imagine a version of A(q,n) that has been allowed the same inconsistency. Such an algorithm, would, of course, lose Penrose's game, so there would be little point in this, but if we are going to permit human inconsistency to be used to evade questions then we should permit this of algorithms. Doing so would make the debate rather pointless, however. I can fully accept that Penrose is using the idea of a machine that is required to behave consistently in an attempt to show that there are limitations on the abilities of such a machine. Given this requirement of consistency by Penrose it would be unreasonable to suggest that inconsistency tells us anything the capabilities of a system.

We can also deal with this objection by considering Penrose's case somewhat differently. Instead of regarding Penrose's case as telling us about the capabilities of some hypothetical algorithm A(q,n) we can consider it as attempting to show that some statement is true of the form 'There exists no algorithm A(q,n), such that it can always answer questions of such-and-such a type consistently and can deal with such-and-such a question.'' There is no real difference here: I merely stated it differently. It is still as reliant on Penrose's assumptions and yet we could now also interpret my word game against other humans as attempting to show that a statement is true of the form 'There exists no human, who is the subject of this question (for example, you if you were asked this question, or John Smith in earlier examples) such that he/she can always answer this question consistently.' The whole issue of whether a human decides to play consistently or not is now irrelevant: we are not talking about an individual person but merely demonstrating that consistent and successful playing of the game is impossible. Any argument about whether or not I can win the game is now considered irrelevant. It merely becomes obvious that both my word game and Penrose's proof make rather pointless attempts at proving statements about the capabilities of different sorts of entity.

We could always demand that consistency was assumed in the question, for example:

If John Smith were asked this question and was always going to respond consistently, would he ever answer 'No'?

Some readers may not like this assumption of consistency for which the question asks. We could also avoid the issues of consistency and cooperation by making consistency the subject of the question:

If John Smith were asked this question would it be consistent for him ever to answer 'No'?

and in this case, any inconsistency shown by John Smith is irrelevant: while John Smith should have problems I can safely answer 'no' and supposedly show my mental superiority without any regard for what he will or what will not do.

I am sure that further objections could be made and I will not attempt to anticipate them further. This word game is not intended to be an exhaustive disproof of Penrose's proof, but was simply given to show the sort of thing that I think is going on in Penrose's proof and it is merely an analogy. It is not even critical to me that it survives against all such objections. I have dealt with some of the more obvious objections to try to give the case some strength, but now we should move on.

It may seem that I have to struggle to phrase a question to force inconsistency or failure to give an answer onto a human victim, while Penrose's apparently elegant problem does the same to Algorithm A(q,n) with ease. Some readers may even feel that they can exploit some vagueness in my word game, even with the above loopholes closed, and still play consistently. While I could try to anticipate more loopholes and phrase the question so as to close them, it would make no sense for me to play this game indefinitely. We only have to face such issues because of an unimportant difference (for the purposes of the Godelian proof) between a human brain and the algorithm A(q,n) in Penrose's proof, which is that Algorithm A(q,n) is compelled by its own nature to perform the same processing and give the same answer every time it is asked the same 'question', that is to say, every time that it is given the number of another algorithm and its input to analyse. Someone could think that this is because human brains have 'free will' and have a choice about how to respond each time, whereas a computer is constrained by its program to behave in the same way each time. This reasoning would be wrong - in fact I would find it incoherent and I am not aware of Penrose himself making any argument like this. The reason for the human brain having such apparent freedom in contrast to the computer is that the computer starts in the same state every time it is asked the question. If such a machine were actually built then it would need to be reset and loaded with its program each time it were used and starting in the same state, with the same input, forces an algorithm to give the same output every time. This is not due to any limitations in computers, but is simply one of the rules of the game in Penrose's proof. A human brain, conversely, is under no such limitation. While you are being asked the question, and while you are answering it, your brain changes and, the next time you are asked it is actually a slightly different brain that is answering, allowing it to give different answers for different instances of the question.

To make the situations of the human brain and Penrose's algorithm A(q,n) the same, without regard to the ability to give different answers for different instances of the same input, we would either have to put constraints on the human brain or modify Algorithm A(q,n). Putting adequate restrictions on the human brain appears to be impractical as we would not only have to return the brain to the same state before we asked each question - meaning that the individual would lack any memory of answering it before - but we would also have to control environmental effects with total precision and deal with issues such as chaos and the apparently random numbers (though there is some controversy about this) generated by quantum mechanics. An advocate of Penrose could seize this as evidence that computers are limited in an important way, but this counts for nothing: digital computers are not as vulnerable to minor changes in their environments or their initial states as human brains, but it has little direct relationship to the point that Penrose is making. It would be easy to give the algorithm A(q,n) the freedom to respond differently each time, simply by giving it an internal counter that is incremented (that is to say, one is added to it) each time it is asked a question and is not reset each time. Different program runs would read different values of the counter and could respond differently as a result. Another way would be to give the system an input from some chaotic system, or one governed by quantum mechanical randomness in the outside world. This is only of interest when we are considering why we appear to need more carefully worded questions to trap a human and we should have no interest in doing this: we want A(q,n) to work consistently.

An objection could be made to what I have just said by stating that allowing computers to preserve their states in between analysing different examples will, in itself, not save them from the problems which are claimed to be posed by Penrose's proof. I want to make it clear that I have never said it would and my mention of this has been only with regard to constructing equivalent 'word games' that catch humans out. Such an objection would merely be a distraction.

Could a Different Vocabulary Help?

The algorithm A(q,n) in Penrose's proof is limited in the answers that it can provide because the act of giving some answers actually contradicts them. This is caused by a limitation in the vocabulary of the computer. Penrose's algorithm can only interact with the world in two ways: it can halt to indicate that the program it is analysing does not halt or it can avoid indicating this by not halting.

The contradictions in Algorithm A(q,n) being able to answer the problematic question could be avoided if Algorithm A(q,n) were allowed to make other outputs. How this would be done need not concern us too much: we are already used to computer programs which output information in a large number of ways; however we can give some consideration to how it would work. In Penrose's proof he is clearly thinking of computing devices that are controlled by Turing machine instruction tapes and such a machine could easily output information by stopping with one or more symbols on the tape at some point set to communicate the machine's output. A suitable way of communicating could use one tape symbol as follows:

0 - the algorithm being analysed does not halt if the machine halts in this state.
1 - the algorithm being analysed does halt if the machine halts in this state.
Until the machine halts the answer has not been determined. If the machine does not halt then the answer is indeterminate.

We could actually improve this slightly, in the sense of providing more information, by differentiating between situations which have been determined by Algorithm A(q,n) to be indeterminate (that is to say, situations on which Algorithm A(q,n) has decided to give up) and situations which Algorithm A(q,n) has simply failed to resolve. This could work as follows:

0 - the algorithm being analysed does not halt if the machine halts in this state.
1 - the algorithm being analysed does halt if the machine halts in this state.
2 - if the machine halts in this state then it has been determined that it is not possible for this algorithm to determine whether or not the algorithm being analysed halts.
Until the machine halts the answer has not been determined and it has not yet been determined if the answer ever can be determined. If the machine never halts then the answer is indeterminate and has never been determined to be indeterminate (That is not a typographical error, by the way!).

For the purpose of avoiding the contradiction in answering Penrose's question, either type of output will be adequate. The important point is that this allows Algorithm A(q,n) to halt and give an output of '1' when analysing itself, indicating that the program being analysed (itself) halts. This extended vocabulary allows the program to avoid the limitation of the simpler program that can only communicate by halting or not halting, specified by Penrose.

The vocabulary does not have to be extended like this. The vocabularies that I just gave are providing more information than we need to beat Penrose's contradiction and a vocabulary which simply involved outputting some symbol for algorithms that do not stop and otherwise outputting no symbol, without the act of halting being required for communication or even relevant to communication at all, will work just as well. For such a vocabulary to be used the algorithm would need to be able to make outputs without being in its halt state, but this presents no problem: algorithms output information without halting all the time. Such a vocabulary could be as follows:

To indicate that it will not stop the algorithm will output '1'.Whether the algorithm stops or does not stop after doing this has nothing to do with the vocabulary. The algorithm must not output '1' for any reason other than that just stated. If the algorithm determines that it does stop, or if the algorithm determines that it cannot determine whether or not it does stop then it must not output '1' and, provided that it does not do this, what it does after making the output is irrelevant to the vocabulary.

It would be possible to alter the question in an attempt to catch A(q,n) out, but nothing profound would be shown by this: the same could be done to human brains.

Penrose's Defence

The main idea behind this objection is not new. As I stated previously, Whiteley made a similar sort of argument against Lucas and other arguments like this will have been made against Penrose's proof. The closest that Penrose gets to acknowledging such arguments in Shadows of the Mind is when he states [6]:

Penrose goes on to ask us to imagine such an algorithm that does halt for both cases, but is then forced, after determining that an algorithm halts, to enter a loop that it never exits. His argument is, essentially, that we are only interested in an algorithm that tells us when other algorithms will not stop, that such an algorithm can easily be produced by altering an algorithm with a more extensive vocabulary, and that an algorithm with a vocabulary that is limited in this way is quite adequate for his thought experiment, as it will demonstrate limitations that all algorithms have. This is what he says:

The similarity between the idea that Penrose is refuting here and the one being discussed in this article is that both ideas are based on changing the vocabulary - the way of communicating its answer - that the algorithm is required to use. Penrose is focusing on the idea of allowing A(q,n) to halt if it determines that C_q(n) does halt. While I am going to make some use of this I am also going to use also the idea of not forcing A(q,n) to halt if C_q(n) does not halt. The two are related: it could be argued that the real problem involved in not letting A(q,n) halt if C_q(n) does halt is actually that, if we are determined that A(q,n) should use halting or not halting to communicate, then it only leaves the option of having A(q,n) not halt to show that C_q(n) halts, causing the contradiction for A(k,k), whereas a vocabulary that was not as dependent on halting may not get us into the same mess.

In this article I am using two ideas for vocabularies. One of these exploits the idea of allowing A(q,n) to halt naturally when it has not determined that C_q(n) does not stop. The other vocabulary will be closer to Penrose's vocabulary in that it will not make no provision for providing information about cases when C_q(n) halts and will simply use the idea of a different vocabulary that is not based on halting or not halting at all.

Penrose could reply that it is not true that A(q,n) does not halt to signify that C_q(n) does halt: he may say that the only time that A(q,n) communicates is when it determines that A(q,n) does not halt and that other cases do not involve any result from A(q,n). This would not help as it does not address the real problem with what he is saying: the main problem with Penrose's answer is that it appears to defend his right to have whatever vocabulary will suffice, in his proof, to allow A(q,n) to give its answer.

Because these ideas appear to be the closest that Penrose gets to a defence against the sort of refutation being attempted here, I will refer to them from now on as Penrose's defence or I will use some equivalent terminology; for example, 'the defence used by Penrose'. This article will show that this defence of a specific vocabulary does not work.

Initial Comments on Penrose's Response

Penrose clearly thinks that he has already refuted this sort of argument. His defence, described above, is important because it is on this that the validity of his entire case rests. I find his answer unsatisfactory and here are reasons for this:

For a start, Penrose discusses the idea of purpose behind Algorithm A(q,n). He finds that Algorithm A(q,n), as he specifies it, is satisfactory for his proof because it meets some purpose of telling us when an algorithm will not stop. This introduction of intentionality is something that I find strange. We are simply discussing what types of outputs algorithms are capable of and presuming that a given category of algorithm (his), limited in a particular way, is demonstrative of the capabilities of all categories of algorithms purely because it satisfies some human intentionality does not make much sense to me. If this point seems strange I would ask you to consider a rather implausible situation in which no humans were actually present and some matter had happened to come together randomly to make a computer that was executing Penrose's algorithm A(q,n), while other matter had come together randomly to make a computer that was executing another version of this algorithm without the vocabulary restrictions that are justified by Penrose's intentionality argument. It should be clear that any argument that is claiming that the computer running Algorithm A(q,n) is somehow indicative of the capabilities of the other computer, and all other computers that can exist, should not rest on ideas of purpose or intentionality.

The main problem that I have with Penrose's defence is that it seems to ignore the entire issue. When the suggestion is made that an algorithm with a different vocabulary would not be vulnerable to his argument, Penrose appears to dismiss such an algorithm by simply saying that we do not need it! Well, we do need it actually - not because we are particularly interested in having an algorithm that gives us firm answers when it finds that other algorithms halt: as I admitted earlier we do not have any particular interest in the situation when C_q(n) halts. No, we simply need an algorithm with a different vocabulary to refute Penrose's argument! I can understand if Penrose does not consider this a particularly useful purpose for an algorithm.

The Assumptions in Penrose's Defence

Penrose's defence appears to rely on these ideas:

1. If we are considering algorithms that are required to answer a question then it is reasonable to consider only a class of algorithms that have a specific vocabulary, provided that, ignoring any contradictions caused by self-reference, this vocabulary does not compromise their capability to answer the question.
2. If it is demonstrated that the class of algorithms with the specific vocabulary mentioned in (1) lacks some capability then either: (a) any class of algorithms, irrespective of its vocabulary, lacks that same capability with regard to the problem or (b) any class of algorithms lacks that capability or some other capability as a direct result of the class of algorithms with the specific vocabulary having the deficiency demonstrated by Penrose.

What I mean here is that, in his dismissal of any attempt to change the vocabulary of the computer, Penrose must be implying that vocabulary changes do not work. The most obvious conclusion would be that Penrose believes that his argument demonstrates that any class of algorithm will have the limitations demonstrated in his proof, even though the proof appears to fail for such an algorithm! It seems likely that Penrose justifies this by thinking that his proof for a specific class of algorithm somehow works for all algorithms and this is what I suggest in (a).

I want to be sure, however, to be fair to Penrose. It could be that he is not claiming this. In this case the only sensible possibility would seem to be that the failure of Penrose's algorithm A(q,n) to answer his question is proof that, even if we constructed some machine that did not have this limitation, some other limitation would manifest itself. This is what I suggest in (b). Presumably, the existence of some such limitations for all algorithms should be clear as a consequence of Penrose's demonstration of a limitation for Algorithm A(q,n), but unfortunately it is not at all obvious to me. I will not even attempt to argue against this position here, because Penrose's book does not even advance an argument to support it: the defence that he makes where he states:

is too vague for us to read anything like this into it.

A third possibility seems to exist - that Penrose is not even arguing that all algorithms have limitations in comparison with humans, but is simply suggesting that A(q,n) is limited and that other algorithms are simply irrelevant. I doubt if he is making this case. It would not help to refute ideas of computational AI, but would simply amount to an assertion that computers made in certain ways cannot output results that we can.

Because the second idea would actually need an argument by Penrose to refute - we do not seem to have one, at least in Shadows of the Mind - and the third idea would not help Penrose at all anyway, this article will attempt to refute the most obvious argument that could be used as a defence - the idea that a demonstration of some limitation for A(q,n) implies that all other algorithms have that same limitation. This claim appears to be based on the assumptions given above, so my argument will refute these assumptions.

The Basic Idea of the Refutation

Penrose's argument is based on an algorithm A(q,n) that consists of every knowably sound method for determining that an algorithm does not stop. The question being asked of A(q,n) is hardly easy: A(q,n) is expected to be able to answer this question for any algorithm for which a knowably sound method exists.

We cannot actually get Algorithm A(q,n) and examine it, nor we can get hold of computer code which runs another version of A(q,n) designed to circumvent Penrose's implied limitations. We simply cannot make this algorithm. In the absence of any easy demonstrations of Penrose's logic being wrong, the vague ideas used in his defence may seem somewhat plausible.

There is one way in which we can approach this: if the ideas in Penrose's argument are valid then it should be possible to use those same ideas to demonstrate that all computers have limitations with regard to answering some other questions. Rather than choosing the problem faced by Algorithm A(q,n) in Penrose's argument, which is rather unwieldy to think about, we can choose a question which is easier to consider and for which the answers about the capabilities of various classes of algorithms will be obvious. Once we have constructed such an argument then we can imagine it coming under the same sorts of attacks that I have already made in this article, and which others have also made. If the assumptions behind Penrose's defence are valid then Penrose's defence should be valid in an argument intended to demonstrate limitations in algorithms that are being asked much easier questions.

This will be my strategy. I shall use Penrose's ideas to construct arguments about the capabilities of computers that are dealing with much simpler questions than the question being dealt with by Algorithm A(q,n). I shall then subject these arguments to the sort of attack that I have made on Penrose's argument and show how Penrose's defence against issues relating to vocabulary, or any other defence that he could make, does not work in these situations. Once this has been established it will strongly suggest that the use of these ideas and Penrose's defence in particular are also invalid in Penrose's argument.

An Algorithm that Indicates if it Would Not Stop

We will begin our consideration by exploring a very simple question. Penrose's algorithm A(q,n) had to deal with questions about halting of all algorithms. Our question will be much simpler. Here it is:

Is it true that you do not stop? Specifically, if you do not stop, give some indication of this.

The way that this question is worded may be a little vague, so here is what is actually required of an algorithm that answers it:

The specific purpose of the algorithm is to inform us if it happens that it will not stop, but that is all. If the algorithm does not determine that it does not stop then we have no interest in what it does, provided that it does not wrongly inform us that it does not stop. This limitation in our requirements is similar to that used by Penrose in his defence.

I shall use the same sort of idea that Penrose used to construct an argument showing that no algorithm can answer this question. I want to be sure that the reader understands that I will be using reasoning that I find wrong here to make a point about Penrose's proof.

What sort of inputs does our computer need? We should not expect it to answer questions in English or any other natural language: Penrose's algorithm A(q,n), after all, is not expected to accomplish any such feats of general purpose AI. In fact, as the algorithm is only made to answer one question, then we can consider that question to be hard-wired into it so that the question does not need to be input at all. This means that the algorithm will not need any inputs.

We need an appropriate vocabulary for our algorithm to communicate its findings. The vocabulary used will be as follows:

If the algorithm determines that it will not stop then it stops to indicate this. Unless the algorithm determines that it will not stop, then it continues to run. This means that if the algorithm determines that it does not stop it will signify this by stopping and if the algorithm determines that it will stop, or if it cannot determine the answer, it will not stop.

A quick consideration of all this shows that if the algorithm does not stop then the only way that it can signify this is by stopping. This is a contradiction as it would be announcing that it does not stop by stopping. On the other hand, if the algorithm does not stop, which is the only consistent behaviour available to it, then it has not announced that it does not stop, so by Penrose's standards it does not know that it does not halt, whereas we do.

We did not consider any particular algorithm here so we must confront an obvious truth for all algorithms:

No algorithm can answer this question: 'Is it true that you do not stop? Specifically, if you do not stop, give some indication of this.'

It may seem, therefore, that I have proven a limitation to exist in algorithms!

What objections could be made to this? We will examine some of the more obvious ones.

Objection 1: The question is self-referential and it is therefore invalid to ask it.

As I have stated previously, I do not see any problem with the self-reference here, though I can imagine that some people would. This sort of self-referential situation is accepted in Penrose's proof. If it is acceptable in Penrose's proof it should be acceptable here.

Objection 2: The program is being asked about its own behaviour. If it could answer the question - which it cannot, of course, without contradicting itself - it would actually be being asked not a question, but to actually direct its own behaviour so as to be consistent. This is invalid.

This objection may appear a little deeper and it suggests that, whereas a question such as 'What is 2+2?' is asking someone or something to determine the answer, a question such as the one we are asking here is asking a program about its own behaviour and the program is required to arrange its own responses to be consistent, rather than to actually obtain any real knowledge, for example about the consequences of adopting various formal systems or physical reality.

In human terms, this is rather like asking these two questions:

Question 1: What would Attila the Hun do if he were resurrected in the 21^st Century?

Question 2: Would you say, 'Yes,' if you were in a situation exactly like this one with a brain in a state exactly like the state in which your brain is now?

The first question is extreme. Many people would say it refers to an implausible situation and it is certainly a little vague (How does Attila the Hun get here? From what period in his life is he plucked? etc) but that is not relevant to the point, which is that this is a question about psychology and it is asking you to think about how brains work and provide some useful information about this. The question is asking you to find something out.

The second question is also asking you what a certain human brain would do in a situation, but would it make much sense to say that this is a question about psychology? The question invites you to predict your own actions in a situation like the one in which you are now. The very action that you choose to perform when answering the question determines what the answer should be. This particular question is, of course, quite answerable, but it shares this characteristic with the sorts of questions that we are examining here: it does not really require you to find something out, but instead demands that you act so as to ensure that the answer is consistent.

Some people would suggest that only the first sort of question is valid, but I have no problem with both sorts of questions. Regardless of what an algorithm is doing internally (attempting to find things out or attempting to be consistent) from the point of view of someone outside, providing that the algorithm is giving correct answers, it is still providing information. If the reader disagrees with this then I would make this simple comment: Penrose's argument places his algorithm A(q,n) in just such a situation. If it makes my reasoning invalid, then it does the same to his and there is no case for this article to answer: it certainly was not my idea to start playing the 'direct your own behaviour to be consistent' game.

Now, let us make what could be a stronger attack on my 'proof'. We will use just the sort of objection that I have been making to Penrose's proof.

Objection 3: This is nothing more than a mathematical equivalent of a word game. Insisting on a specific vocabulary that demands that the algorithm stop to indicate that it does not stop and using this to suggest that no algorithm can actually 'know' that it does not stop is flawed. The algorithm is being required by the game to use a vocabulary that makes it contradict itself to communicate its finding. All that is being demonstrated here is that you can use a question, together with a required vocabulary for the answer, to ban an algorithm, or a person for that matter, from answering without paradox. Nothing is being shown about the capabilities of algorithms in general.

This should be familiar as the sort of objection that I have to Penrose's proof. I am now using it on my own special case 'proof'. Does it work? If it does work in this situation we should be concerned about Penrose's proof: mine merely involves a special case of what Penrose imagines. Fortunately, however, we already have Penrose's defence against just this sort of objection! Let us state it here again:

Like Penrose, I could then go on to ask you to imagine such an algorithm that does halt for both cases, but is then forced, after determining that an algorithm halts, to enter a loop that it never exits.

How powerful is this defence? It turns out to be feeble. We can see that the defence is weak by performing one obvious act: constructing an algorithm that correctly answers the question. The existence of such an algorithm would make this defence, or any other, worthless. How would such an algorithm work?

Our first act should be to change the vocabulary that the algorithm uses to communicate. We will use this vocabulary:

To indicate that it will stop the algorithm will output '1' and halt.
To indicate that it will not stop the algorithm will output '0' and halt - clearly this is contradictory and, although I have included it in the vocabulary, it will never be used!
To indicate that it has determined that it cannot determine whether or not it will stop the algorithm will output '2' and halt - an act of dubious value to us, but a quite consistent one for the algorithm to perform.

How do we construct the algorithm that can provide the correct answer? As before, there is no need to input the question. The algorithm is only intended to answer one question and can be presumed to be 'hard-wired' to respond to that question. If we wish to make an algorithm that can answer correctly and consistently we simply need to ensure that it outputs '1, indicating that it will halt, and then halts - which makes it totally consistent with its own prediction of its behaviour.

By doing this we are relying on the idea of allowing A(q,n) to come to a halt when C_q(n) does not halt, but we are not obliged to do this. Instead of having the information output by A(q,n) in its halt state we could make the idea of halting irrelevant and simply have A(q,n) make its output in another way - for example, by writing a symbol to a specific memory location. This vocabulary could be as follows:

To indicate that it will stop the algorithm will output '1'. Whether the algorithm stops or does not stop after this output is made has nothing to do with the vocabulary. To indicate that it will not stop the algorithm will output '0'. Whether the algorithm stops or does not stop after doing this has nothing to do with the vocabulary.

Halting or not halting plays no part in the output of results in the above vocabulary. Once the algorithm has made an output then it can continue running or it can halt. The output still stands once it has been made. We could consider the issue of the algorithm making an output twice, but this should not really concern us: we can say that the vocabulary defines the first output made by the algorithm as relevant and that any further behaviour by the algorithm after this serves no purpose in communication, though of course, any behaviour of the algorithm after the output was made may be examined to check the algorithm's prediction of its own behaviour.

This would now allow us to make A(q,n) behave in one of two ways to answer the question:

1. output '1', indicating that it will stop, and then actually halt for consistency with its prediction of its own behaviour.
or
2. output '0', indicating that it will not stop, and then enter a loop which it never exits, meaning that it does not halt, for consistency with its prediction of its own behaviour.

This approach does not rely directly on the idea of allowing the algorithm to halt in cases where it has a 'no halting' answer against which Penrose's defence is aimed, but it does make use of the idea of vocabulary change, against which Penrose's defence can also be considered to speak.

Either of these algorithms will answer the question consistently.

The vocabularies that I have been using provide more information than Penrose's does. Some readers may think that it is this extra information which is supposed to allow Penrose's contradiction to be beaten. This is not the case. A vocabulary which provides minimal information about not halting only, just as Penrose's does, will work fine. Here is an example of such a vocabulary:

To indicate that it will not stop the algorithm will output '1'.Whether the algorithm stops or does not stop after doing this has nothing to do with the vocabulary. The algorithm must not output '1' for any reason other than that just stated. If the algorithm determines that it does stop, or if the algorithm determines that it cannot determine whether or not it does stop, then it must not output '1' and, provided that it does not do this, what it does in such situations is irrelevant to the vocabulary.

Halting or not halting plays no part in the output of the result in the above vocabulary. Once the algorithm has made an output then it can continue running or it can halt. The output still stands once it has been made. We could consider the issue of the algorithm making an output twice, but this should not really concern us: as before we can say that the vocabulary defines the first output made by the algorithm as relevant and that any further behaviour by the algorithm after this serves no purpose in communication.

This would now allow us to make A(q,n) behave in the following way to answer the question:

Output '1' (indicating that it will not stop) and then enter an infinite loop for consistency with its prediction of its own behaviour.

It would be entirely consistent, actually, for the algorithm to not output '1', meaning that no indication has been given that it does not halt, and then halt, or to enter an infinite loop and never output '1', meaning that the algorithm has simply failed to tell us that it does not halt. Each of these actions, however, would be undesirable to us, as we want an algorithm that successfully deals with the question by Penrose's standards, so having the algorithm output '1' and enter an infinite loop is preferable.

Where does all this leave my use of Penrose's defence to meet Objection 2? It should be clear that it leaves it in a bad situation! In each of the above cases we are being confronted with the very thing that my proof says should not exist: an algorithm that can tell us if it does not halt. I hope it is clear that my use of Penrose's defence to answer Objection 2 is irrelevant.

What should I do now if I wish to persist with my 'proof'? Maybe I could say, 'You do not understand!' and repeat Penrose's defence again. Maybe I could say, 'You just do not get it. The purpose of the algorithm is not to tell us which algorithms do stop: that is not its job…' All of this is irrelevant when we are confronted with an algorithm that defies the proof.

The conclusion that follows from this is inescapable. When we consider Penrose's proof, but applied only to algorithms that give us answers about a special case, it fails. Such a proof uses reasoning that is, basically, no different to the type of reasoning used by Penrose. In particular, when we make the type of objection that we have been discussing in this article and attempt to use Penrose's defence against it, this defence fails. The reasoning in Penrose's defence against this sort of 'limited vocabulary word game' objection is flawed. If it is flawed in our special case situation then there is no reason why we should not regard it as flawed in Penrose's proof. Without this defence to protect Penrose's proof it fails and, unless he can provide another defence (and it would have to be one that is good enough to defeat the actual existence of algorithms that are proved not to exist by proofs which are like his own, but less general) his argument collapses.

Possible Objections

It would be unfair to expect this to be accepted without considering possible objections that can be made. Here are some:

Objection 1: So what? Even if you have refuted Penrose's Godelian argument, and let's face it, you can find plenty of refutations already on the Internet, does it mean that Penrose's case for non-computability is wrong? Where is your refutation of his entire case? Penrose offers an explanation of the human mind, or at least an idea that may let us get a grasp of how such an amazing thing as the human mind can exist. Do you know how the human brain works? No? Well, what do you know? Leave this great man alone.

Apart from noting the obvious 'appeal to authority' of such an objection, I would restate an important point. The purpose of this article is not to demolish all of Penrose's claims regarding non-computable physics or even to consider his case in its entirety, but only to refute the mathematical proof which is being discussed here.

Objection 2: You may have shown that an algorithm can be made to answer a question about itself. By doing this you may have shown that if we have some algorithm A(q,n) that cannot answer a question about itself then we can extend the algorithm A(q,n) by incorporating your algorithmic method, but this is already acknowledged by Penrose in Shadows of the Mind and he points out that if this is workable then it should be possible for Algorithm A(q,n) to have the capability to derive such a method. He shows that this does not help as it will simply imply a new A(q,n) that cannot assert the truth that C_k(n) does not halt [7].

The objection is a straw man argument - an argument that is made by inventing a position that cannot be validly defended, falsely representing it as an opponent's position, and then refuting it and it misses the point of my argument. I am not trying to show that we can circumvent Penrose's contradiction by extending Algorithm A(q,n). The point is that we can use Penrose's assumptions to construct a proof for a less general case which can then be refuted by producing the very algorithm that is not supposed to exist according to the proof.

Objection 3: It is irrelevant that you show that a program that can consistently answer the question can exist, in defiance of your rather disrespectful spoof version of Penrose's proof. No matter what you show to exist, it still remains that the purpose of the algorithm was not to give an indication that it will stop. That is not its purpose…

After everything that I have said I am not entirely sure whether I have included such a 'head in the sand' objection for facetious reasons or because of a worrying suspicion that someone would actually try to use it. As I stated earlier, this defence relates more directly to the case for A(q,n) being allowed to halt when C_q(n) does not stop, which is not the only vocabulary changed used in this article. It does have some relevance to the whole refutation, however, as it proposes a defence for the choice of a particular vocabulary.

It is clear what we would be expected to infer from such an objection: the idea would be that the demonstrated existence of an algorithm which appears to defy my proof is an irrelevancy, as it is constructed by assuming a way of communicating that is not needed and that because the original class of algorithms, which failed to consistently answer the question, communicated in a different way, they would presumably have some sort of mathematical 'purity' and would tell us more about the capabilities of algorithms than the class of algorithms with the different vocabulary that can answer the question.

If this were accepted then presumably it would also apply to Penrose's position. The suggestion would be that even if an algorithm can be shown to exist that is not trapped by the contradiction that limits Penrose's algorithm A(q,n) this is also of no significance. Penrose's algorithm A(q,n) would be a much 'purer' algorithm for the purposes of the proof and would be much better placed to demonstrate the capabilities of algorithms,

Such an idea is a fallacy. The whole argument is based on showing that algorithms that can answer certain questions cannot exist. Once the existence of an algorithm that can answer is demonstrated, if it is regarded as irrelevant, we have to wonder exactly what the proof was attempting to show. Let us take this to an extreme. Penrose's attempted proof, and my special case 'proof', appear to allow the existence of algorithms that are 'outside their scope' and are expected to be deemed irrelevant, but this suggests that any reasoning intended to follow on from this and preclude intelligent behaviour in a machine should have similar provisions. Given that Penrose's argument is clearly intended to show that truly 'intelligent' algorithms cannot exist, what if the existence of such an intelligent algorithm were demonstrated? The absurd situation is now suggested in which a devotee of Penrose actually tells the machine, in a plain language conversation about maths, that he/she has some 'extended Penrose argument' that proves that machines cannot be truly intelligent and that any apparent intelligent behaviour that the machine produces does not count, as the machine is not a member of a class of algorithms that communicate in ways deemed adequate for this sort of philosophy. As an argument against the existence of true AI this is questionable!

Further objections could be made against my use of this special case proof to demonstrate weaknesses in Penrose's proof by trying to demonstrate differences between my proof and Penrose's proof. The idea here would be that because of some difference between the two proofs, my demonstration of the weakness in my proof to the sort of refutation I have been using does not imply that a similar weakness exists in Penrose's proof. Here are some of these objections:

Objection 4: Penrose's algorithm A(q,n) is expected to contain every knowably sound method that determines that a program does not halt. It performs some computation that is not trivial. Your algorithm is trivial. It performs no computation at all, but simply outputs a 'result' that was hard-wired into it. You can hardly claim that your algorithm contains every knowably sound method for determining that 'it does not stop' (surely a pointless exercise). It does not do anything really. It certainly is not equivalent to Penrose's algorithm. As your algorithm does not actually determine anything in any non-trivial way it would be futile to suggest that your 'proof' would show anything about what algorithms can determine. We should expect your 'proof' to be meaningless for this reason - there is not really any algorithm there for the proof to be about. Although you intended your proof to fail, it fails on account of triviality and not due to any validity of the objection that you made to your own proof. To suggest that any reasoning that applies to your trivial algorithm should apply to Penrose's algorithm A(q,n) is a fallacy.

The algorithm that I imagine does make some output and does this by means of an act of computation. The computation may appear trivial and not particularly useful, but that is merely a human value judgement. All we have is what we would have if we took a machine that performed some computation to make an output and progressively reduced the size of the program in it by a line of code at a time, or maybe an instruction symbol at a time, in the case of a Turing tape machine, until all that was left was the instruction that makes the output. If this is supposed to mean that we are not doing a computation any more then at what point did we stop doing computations? Was it when we went from ten lines of code to nine? Was it when we removed the very last instruction that did something other than just make the output? If so, why? It may be appealing to think that the transition from a machine that does something before it makes an output to a machine that just outputs is profound. We could say that the operations performed by the machine before reaching the output command are 'processing' and that when these are lost the machine crosses some sort of boundary and becomes trivial. This would be a fallacy. The whole concept of processing, lines of code, output and the distinction between processing and output is a human construction anyway. In reality, computers are merely machines that undergo state changes, each state change being controlled by a set of rules, and my computer undergoes a state change: it goes from the state that it is in just before running the output command to the state that is in after it has executed this command and then halts or loops forever. How many state changes occur (that is to say, how 'long' the computation is) has nothing to do with Penrose's proof or my failed 'proof'.

If you do not accept a single state change as a computation then I would ask what you do accept. Any computation occurs by means of a sequence of state changes and if each of these single changes achieves no computation at all then it is hard to see how a sequence of computationally empty single state changes could combine to perform a computation. We can also view this in terms of outputs. If you think that the making of a single output cannot constitute an act of computation then you have the problem that a computer can be viewed as a system of interacting components, each of which makes outputs that become inputs for other components. How are all these computationally null outputs expected to somehow embody a computation?

If any readers still have issues with this I would point out that we could simply add some redundant computation to my algorithm to make it more substantial. Penrose uses a similar idea in his defence so if it works for Penrose, which it does not, it may as well work for me too.

Some readers may still have issues with this so I would like to point something else out: although an algorithm with a trivial amount of processing was considered in my argument against Penrose it was not a part of my failed 'proof' itself. The 'proof' that I demonstrated used reasoning similar to Penrose's to show that algorithms of a certain type cannot exist. That 'proof' did not just attempt to show this for trivial algorithms. It gave no consideration at all to the significance, size, complexity or triviality of algorithms: it appeared to demonstrate a lack of capability for all algorithms. We could go further than this and even say that Penrose's proof and my 'proof' are not specific to algorithms, but apply to any entities that can be numbered according to their behaviour in the same way. My trivial algorithm was only produced by me to refute my own 'proof' by showing that an algorithm could make the sort of output that I had just 'claimed' to prove was not possible. The fact that this algorithm is trivial should hardly be of much comfort to me, if I really think such a proof works! I am supposed to have constructed this proof that all algorithms lack a certain capability, yet a trivial algorithm is capable of punching through the 'contradiction' of which I am so proud, which should hardly give us confidence about the survival of the contradiction in the face of non-trivial algorithms.

If anyone still has problems with this triviality issue we will shortly be looking at a discussion of another proof that involves an algorithm that has more processing.

Objection 5: In Penrose's proof, Algorithm A(q,n) is given input data. It is given the number of an algorithm (q) and the input of that algorithm (n) for an algorithm that it is expected to analyse. This input is effectively a question: the inputs q and n into A(q,n) can be regarded as meaning 'Would algorithm q with input n not halt?' In your proof you talk of asking your algorithm a question ('Would you not stop?') yet your algorithm has no inputs. This means that, unlike Penrose's algorithm, your 'answer' is not answering a question at all: no question is being provided as an input. You are just pretending that it is answering a question.

When we consider the questions being asked of the algorithm in my 'proof' or in Penrose's we can imagine the question being in English. In neither proof, however, is the question actually input into the algorithm in this way: in each case the algorithm is only supplied with the data that it needs to answer the question. Penrose's algorithm may appear to be doing something more profound because it accepts input data. Mine does not and it would be easy to claim that Penrose's algorithm is answering a question, whereas mine is not.

For a start, the whole idea of considering this as a question is a rather artificial way of looking at things anyway. In reality, we are considering the feasibility of setting algorithm up in various initial states and extracting information from them to answer questions that we may have in mind. It is perhaps a bit anthromorphic to talk about the algorithm really being 'asked' anything.

This answer may appear vague to some readers who remain unconvinced, so here is a better answer to this objection:

When we build a machine to answer a question, what is input? When we make a calculator to perform arithmetic, are we expected to enter on a text keyboard something like 'What do we get when we add 2 and 2 together?' Of course not! When every question that a machine can answer has a certain part that is the same for all questions then the machine can be built in such a way as to effectively assume that part of the question. In this case of a calculator that only does arithmetic this means that the 'What do we get…' part is assumed and the calculator only awaits the specific numbers and the specific arithmetical operation for the particular question that is going to be asked. The calculator does not really assume this in the way that you or I may assume something: rather, the assumption is built into the calculator when it is designed only to perform arithmetical operations. As another example, a computer that is hard-wired to expect programs in a language like BASIC, as some machines were in the 1980s, does not expect every BASIC program to begin with some introduction that means 'This is a BASIC program. Process these instructions according to the syntax of the BASIC language': the assumption is implicit in the machine's construction.

If certain information is not needed in questions that are posed to machines then we can ask what information is needed. The answer to this should deal with this objection. Any machine that can answer questions can answer a certain number of questions. While it may seem trivial to state this, a number of questions can be posed to the device and for each valid question it is expected to produce an answer. For a calculator, for example, possible questions would be 'What do we get when add 0 and 1 together?' and 'What do we get when we add 1 and 1 together?', but there are lots of others, of course. Because the machine can answer a large number of questions, while it does not need data that is common to every question, what it does need to be told is which, of all the possible questions that can be asked of it, it is expected to answer now. For a calculator this could be done by entering the question in a way that makes sense to us, but it could be done in another way: we could simply have some system of assigning every possible question (that can be validly asked of the machine) a number and we could input this number into the machine which could use this same system to work out which question was being asked and then answer it. For example, we could design a calculator in such a way that we may just enter a question such as '2,651,729' that would direct the machine to display the answer for question number 2,651,729, using whatever scheme we had worked out for numbering arithmetical questions.

Any question answering machine is going to have a certain number of questions in its repertoire. Although this number may be infinite for some machines that need not concern us here - and it is certainly not relevant for us to worry about whether or not infinity is a number! The only input the machine needs is a number or some other data that makes it clear which question is to be answered. For Penrose's algorithm this data comes in the form of two numbers: q, the number of the algorithm to be analysed, and n, the input to that algorithm. We could, in fact, put q and n together to form a single number and the purpose of that number serves only to specify which of all the possible questions, out of all the ones that Penrose's algorithm A(q,n), can answer, is the one that actually has to be answered. For Penrose's algorithm the number of algorithms that can be analysed is probably infinite and q and n serve to specify a single question from this infinite list of questions.

Let us now suppose that we constructed a machine that could answer only 100 questions. It does not matter what these 100 questions are - they could be questions about Shakespeare, geometry or logic - in principle the only input needed by the machine is that which is sufficient to identify which of the 100 possible questions is being asked. An input of a single whole number between 1 and 100 would be adequate, provided that the machine's internal logic is able to use this data to answer the question appropriately. We could take this further; for example, if the machine could only deal with ten questions and answers the only input needed would be a whole number between one and ten and if the machine only had a repertoire of two questions and answers then an input of one or two would suffice or, if we wished, an input of '0' or '1' so that the machine would require only a single binary digit as input. This is the main point I am making here: when a machine is built to answer a question the only data that is needed as an input is that which is sufficient to identify which of the possible questions is being asked. Any other information relating to the question can be considered to be intrinsic to the machine's design.

Let us now consider the algorithm in my proof. It is only designed to answer one question. The only input that it needs has to be sufficient to identify which of the possible questions is being asked, but as there is only one question we do not even need a single binary digit. We do not need any input at all as every time that a question is being asked it can be presumed to be the only question that the machine can be legitimately asked.

The design of my algorithm is entirely consistent with what we have said about questions and it also shares the same feature with Penrose's algorithm: that of having only the minimum amount of information needed to distinguish between possible questions as input. The lack of input into my algorithm is entirely consistent with the design of a machine that must answer one question only.

Some readers may object to this by saying that this simply means that a machine that answers only one question is somehow invalid and cannot be said to be answering a question at all. This would simply be a value judgement based on a prejudice about the usefulness of the algorithm. If someone made this case what would satisfy them that a machine were being asked a question? Would it be input adequate to distinguish between two questions, or ten maybe? If input adequate to distinguish between two questions were accepted what would be the reasoning behind this? Why should an algorithm become more useful for a proof of this type merely by having a binary digit input into it? Having any dividing line between systems that are answering questions and systems that are not merely on the basis of a dividing line of this type is contrived, but, surely, if it is required that an input for a 'question' has more than one binary digit in it, the argument that the standards being applied are arbitrary should become more persuasive.

Some readers may still have problems with this. The further 'proof' which is to be given will involve algorithms that have to accept sufficient input data to distinguish between multiple questions, thereby resolving this issue. It will also be apparent that the number of questions could easily be extended without any contradiction.

Objection 6: Penrose's algorithm A(q,n) is an extremely powerful and complex algorithm comprising every knowably sound algorithmic method for determining that an algorithm halts. Your algorithm, in contrast to this, is much less powerful. It can only answer questions about itself. It is not surprising that the proof for your algorithm should have some limitations. Penrose's proof involves the much more sophisticated algorithm A(q,n) and we should not presume that, just because your proof fails for your simple algorithm, it should fail for Penrose's more sophisticated algorithm.

Anyone making this objection is falling into a cognitive trap. The idea would seem to be that my proof fails - I intend it to fail, of course - due to some lack of 'scope' in the algorithms that I am considering. When we consider Penrose's proof we are imagining an algorithm of much greater scope and this would be expected to make the proof stronger.

This is a strange idea. The failure that I demonstrated in my proof had nothing at all to do with lack of 'scope' in the algorithm. It was simply that the proof attempted to demonstrate that an algorithm of a certain type caused a contradiction, yet such an algorithm could actually be produced, refuting the proof.

It may be that there is a kind of intuitive feeling that the greater powers of the algorithm in Penrose's proof will somehow be 'inherited' by the proof involving that algorithm. I do not really know how to refer to such a bizarre idea - 'proof Lamarckism' is about the best term that comes to my mind. The idea is wrong because there is no clear reason why a proof that happens to feature an algorithm should somehow gain any strength from the algorithm itself. To think this really is a cognitive fallacy. It is the same type of reasoning that has caused people to accept Anselm's ontological argument [14, 15] which attempts to prove the existence of God by trying to establish that the greatness of God, a hypothetical idea in the argument, is somehow passed onto the reality of the definition of God and actually makes the object of that definition more real. The reasoning is not exactly the same, but it is the same sort of fallacy. Penrose's algorithm is not presented for our inspection. It is a hypothetical object in his argument, as Penrose admits without any problems, and it should not cause a proof to become stronger merely by mentioning it.

Those who would say, 'Your argument is invalid because you do not realise that Penrose's algorithm is so much more powerful than yours,' really should prove this case. They should show why Penrose's proof escapes the problems of my proof without simply referring vaguely to Algorithm A(q,n)'s power. In the absence of such a demonstration we can be sceptical, but even if we did take such a case seriously we should hardly view it as helping Penrose. Such an idea would be using the 'power' of Algorithm A(q,n) to argue that the proof is less vulnerable to refutation, and hence stronger, than proofs involving less powerful algorithms. Penrose's argument, however, is trying to demonstrate the weakness of A(q,n), relative to the human mind. Even if we did accept some sort of link between the strength of the proof and the power of Algorithm A(q,n), we would be accepting that the power of Penrose's algorithm strengthens a proof of its weakness! Not only is this idea flawed: if we did adopt such bizarre reasoning why should we not argue that such a link exists for other arguments? Why should we not argue that the large scope of Penrose's algorithm A(q,n) strengthens my refutation argument and all the other refutations of Penrose's proof? All of these arguments should surely be better placed to benefit from the strength of A(q,n) if this sort of idea has any validity! They are on Algorithm A(q,n)'s side!

Such reasoning is more likely to be the product of emotion - which lets people see what they want - than consistent reasoning.

Objection 7: There seems to be a sort of disconcerting vagueness in the requirements of the algorithm in your proof. With Penrose's proof the algorithm is given the specific number of an algorithm which is to be analysed. With your proof the 'question' simply refers to whichever algorithm happens to be answering it. Penrose's question refers to a specific algorithm, but yours does not. There is a difference between a question that asks whether algorithm 2,184 will not stop and simply asking 'will you not stop' and directing it any algorithm that happens to be listening. When the algorithm is caught in the contradiction of effectively analysing itself it is analysing a specified algorithm and there is only algorithm A(q,n) that is under consideration. With your proof a large number of different algorithms could all be considered. The question does not require any particular algorithm to be involved. Your question, because of its greater vagueness, seems to be less 'real' than Penrose's. This may cause enough of a difference between Penrose's proof and yours to mean that intended failure of your proof does not imply a failure of Penrose's.

This objection does not seem to deal with the main problem here - that a set of assumptions broadly similar to those that appear to be used in Penrose's attempted proof can be used to construct a 'proof' that fails.

Some readers may not accept this. The objection is also related more to how we view the situation than what is actually going on. Let us suppose we consider the question in my proof as being 'Will you not stop?' and imagine that we produce an algorithm - let us make up a number for it and call it algorithm 4,213,625 - which is attempting to determine if it will not stop, in accordance with my question. It may seem that algorithm 4,213 is not specifically referred to in the question, but, both in my proof and Penrose's, from the point of view of the algorithms, the question never exists in such an English language form anyway. Once we have a 'candidate' algorithm which is to attempt to answer the question we can simply revisit the question and alter it to specifically refer to the algorithm that we have in mind. In this example we could consider the question just as validly as being 'Will algorithm 4,213,625 not stop?' provided that we are restricting our consideration to just this algorithm.

If we are to view things like this we can simply restate the goal of our proof. It was previously to show that no algorithm can be made to answer this question:

Is it true that you do not stop? Specifically, if you do not stop, give some indication of this.

If apparent vagueness here is a problem we can simply reword the question and the goals of our proof. The question now would be:

Is it true that algorithm n does not stop? Specifically, if algorithm n does not stop, give some indication of this.

The aim of the proof would now be to show that it is impossible for this question to be answered by an algorithm q when q=n. Although we are not too concerned with the specific values of q and n when we consider the algorithm's behaviour as a whole, the situation that we are attempting to prove to be impossible will involve a specific value of n for any algorithm q which is being considered. This is little different to what is going on in Penrose's proof.

It should be obvious that constructing a proof with Penrose's assumptions is not much different in this situation and that what is going on here is equivalent to what was already considered in my proof, but with slightly different wording. The proof will still fail, showing the assumptions to be unsound.

I am not saying that this resolves this objection: I do not think that there is any real objection here to resolve. When the question is stated in this way, however, I hope it makes this clear.

If any readers are still unconvinced, the proof that we will consider soon will address this issue more directly by using a situation in which a specific algorithm number is required.

Objection 8: Given that your algorithm is trivial, how can it contain any methods that are knowably sound? The specification for Penrose's algorithm requires that the methods that it uses to determine its output are knowably sound. As your algorithm does not seem to do any processing to determine its output, it is hard to see how it could be knowably sound: you do not have a method there to be knowably sound! Even if we accepted your view that the trivial giving of an output amounts to computation, have you demonstrated that this computation is knowably sound? I do not see any such demonstration in your argument.

I could point out that we certainly know the processing of the algorithm used to refute the 'proof' to be sound: while some readers may raise issues of triviality I doubt that many would actually try to maintain that my algorithm produces an incorrect answer. This objection, however, is not relevant to what Penrose's proof and my failed 'proof' sought to demonstrate. These proofs simply attempt to show that algorithms cannot be constructed to answer certain questions consistently. Any knowable soundness of the methods used in the proof is a separate issue. Once it has been shown that Penrose's proof fails to show that algorithms capable of answering certain questions cannot exist then it raises these isues:

• Is the idea of knowable soundness coherent?
• Is the algorithm that I used to refute my 'proof' knowably sound?
• If it is not knowably sound, can a knowably sound algorithm be produced to achieve the same result?
• Does it matter that we know that the algorithm that I used to defeat my 'proof' is known to be valid to us while the machine implementing this algorithm has not performed any logic aimed at establishing its validity but has simply been programmed to use it?

Critics could argue that the last two of these issues are relevant, but they do not avoid a simple fact: we have constructed an algorithm that the proof is not supposed to allow. Once we have done that, we have an algorithm that answers a question and we can debate about its knowable soundness, lack of knowable soundness, our ability to produce knowably sound algorithms to achieve the same ends, the issue of how the algorithms are supposed to get into the computer and what an algorithm can know about the soundness or otherwise of itself. The problem is that none of these directly relate to the issue of the contradiction in Penrose's proof. We do not need to have Penrose's proof or an algorithm that refutes it to discuss these issues. We could take any algorithm that does any mathematics and have this sort of discussion about it. Once we know that algorithms can be made that are not supposed to be allowed in my 'proof' or Penrose's proof then the algorithms that 'beat' the proofs simply join the vast number of other algorithms about which we can have this sort of debate. While Penrose's case could still have merits, and while these merits could conceivably be established in this sort of debate, by this time Penrose's Godel-Turing argument has already become irrelevant.

Objection 9: You interpret the output of your algorithms in an arbitrary way. If we say that your algorithm halts to indicate it would not halt and otherwise does not halt then it may appear to cause a contradiction, but who are you to say how the output should be interpreted? You produced an algorithm that seemed to demonstrate failure of your proof but it required a contrived interpretation of its output to establish that it has done this. If we took your apparently successful algorithm and interpreted its output differently then it would not beat your contradiction at all: it would simply be wrong. The 'successful' algorithm that appears to overthrow your proof does nothing of the sort. It merely provides an output which you can interpret as you wish. It is hardly a surprise that you interpret the output of your 'succesful' algorithm as being a correct answer of the question. In reality anyone could interpret its answer as anything. This means that there is not really any answer there.

Anyone who makes this objection is trying to have it both ways. In my 'proof' I defined a vocabulary, which is simply a way of interpreting the algorithm's output, and showed that this vocabulary would make it impossible for an algorithm to answer the question. I then introduced another vocabulary - admittedly just another arbitrary way of interpreting the output - and showed that this allows the question to be answered and causes the proof to fail. This apparent arbitrariness is at the root of this objection.

Does this arbitrary nature of the interpretation make this output invalid? It should not do so. I have done nothing here that Penrose has not done. Penrose assumed a particular vocabulary for his algorithm A(q,n) and used this to show that A(q,n) will fail in one situation. If we are to be consistent, while making this objection, we should hold Penrose's vocabulary assumption to be equally problematic. If arbitrariness of the vocabulary makes the existence of any algorithm that answers the question irrelevant, then it should make the non-existence of any algorithm that uses Penrose's arbitrary vocabulary also irrelevant. By denying us the right to interpret the results of algorithms as we choose, this objection actually prevents Penrose's proof from working at all, as it precludes us from inferring anything from the output of A(q,n), and if the output of A(q,n) is irrelevant like this we would have to ask exactly what we are even debating here.

Objection 10: I am not finished with my previous objection yet! You have defended your right to interpret the output of algorithms as you see fit, but the interpretations in your 'proof' are more arbitrary than Penrose's. Let us suppose that we have a machine that can answer a long series of questions, each of which could be answered correctly or incorrectly. If we interpret the answers in a certain way and they are all correct, or even a large number are correct, then it is clear that this should be the preferred interpretation of the answers. To suggest otherwise would be to claim that the answers just happen to be correct by chance when the wrong interpretation is used. Penrose's algorithm A(q,n) can answer a large number of questions. If we examined the output for all these 'runs' it would be difficult to persuasively suggest that this was just arbitrary: our so-called 'arbitrary' interpretation could give the correct results for billions of questions. In the case of your algorithm, however, there is only one question and answer. The answer only becomes correct (as you see it) when you interpret that answer in a certain way. Unlike Penrose's proof you do not have a long series of other answers against which you can check this interpretation: your interpretation is simply arbitrary.

We can consider the question to be answered by both the algorithm and the interpretation of its output, so this objection would really be implying that both are arbitrary. How does this stand up?

No real case is being made here. As with earlier objections about triviality of questions, the arbitrariness of interpretation here is a value judgement about how 'significant' an interpretation is. Neither my proof nor Penrose's concern themselves with arbitrariness of algorithms or interpretations: each merely seeks to show that certain types of algorithm cannot exist such that when their output is interpreted in any way they produce certain results. Even if we do accept that my interpretation is trivial why we should expect a proof involving a non-trivial interpretation to do better? There is nothing in the proofs here that gives any special recognition to a non-trivial interpretation.

Some readers will not be satisfied with this. Anyone making the case that my proof is less valid than Penrose's (and therefore that the deliberate failure of my proof tells us nothing about Penrose's proof) with this objection must be insisting that my interpretation is trivial because interpretations of output are trivial when the number of possible answers is below a certain amount. I would ask such readers what would satisfy them. An algorithm with an interpretation that allows it to give correct answers to two different questions? three? 100? A million? Why should there be a 'magic number of answers' at which the interpretation abruptly becomes non-trivial and can be used in a proof? The arbitrariness of this sort of position should be a sign that it is wrong.

The issue of triviality of the interpretation should not concern us. The proof does not concern itself with arbitrariness of algorithms or interpretations. It merely seeks to show that certain types of algorithm cannot exist such that when interpreted in any way they answer certain questions. Even if we accept that my interpretation is trivial there is no reason why we should expect a non-trivial interpretation to do better. There is nothing in the proof that gives it any advantage. Anyone who wants to challenge this should be able to show why a non-trivial interpretation gives a stronger proof and, furthermore, how many different outputs must be possible for the interpretation to be non-trivial.

Most people who attempt to show this would probably pick '2' as the number of different possible answers needed for non-triviality: it may satisfy some concern about having 'different answers' and may appear to lack some of the arbitrariness of selecting '5', '17' or '103'. If any readers are still not persuaded, however, the 'proof' which is about to be shown will address this issue by considering an algorithm and its vocabulary being applied to multiple questions and answers. It will also become apparent that this could be easily extended.

A Second Algorithm that Answers Questions About Halting

I think that I have shown Penrose's attempted proof to be invalid by now; however, when I was dealing with the above objections I mentioned that another 'proof' was about to be provided which may deal with questions and algorithms that are less trivial. This is to satisfy readers who regard triviality as an issue with what is being demanded of algorithms in my 'proof'. As before, the 'proof' is intended to fail. It is built on Penrose's own assumptions and, by failing, is intended to show that Penrose's assumptions do not lead to profound conclusions about the capabilities of algorithm'.

This is the proof:

We will consider an algorithm A(q,n) that behaves in a similar manner to algorithm A(q,n) in Penrose's proof. A(q,n) accepts two inputs: q and n. As with Penrose's algorithm, our algorithm is intended to tell us about other algorithms that are in the list of algorithms C₁(n), C₂(n), etc.

The purpose of A(q,n) is to determine for inputs q and n if C_q(n) will not halt. We are only interested in being told when algorithms will not halt. Should A(q,n) determine that an algorithm will halt, or should A(q,n) be unable to determine whether or not an algorithm halts, we have no interest in this. As long as we are informed when A(q,n) encounters an algorithm that will not halt and A(q,n) never wrongly informs us that an algorithm will not halt we are satisfied.

So far, the requirements for A(q,n) may appear to be the same as those in Penrose's original proof. We will introduce a slight change, however. It is this: A(q,n) will not be required to answer for all algorithms C₁(n), C₂(n), etc. Instead, it will only be required to answer for two different algorithms, unlike Penrose's A(q,n) which is expected to answer for all algorithms for which there are knowably sound methods for telling us if they halt.

We will say that the first algorithm's number is r, so that it is C_r(n), and the second algorithm's number is k so it is C_k(n).

Unlike Penrose's algorithm, however, A(q,n) is only required to deal with two algorithms: C_r(n) and C_k(n). Each of these algorithms can validly accept two input numbers. For C_r(n) the possible values of n are r and '1'. For C_k(n) the possible values of n are r and k. this means that the possible computer initial states that A(q,n) may be required to analyse are:

C_r(r)
C_r(1)
C_k(r)
C_k(k)

What is the value of r? We do not need to worry about what it is, but C_r(n) corresponds to an algorithm that we will make up. C_r(n) will be valid for two values, r and 1, and will perform quite simple processing for each input. When C_r(n) is given r as an input value it will enter an infinite loop, which is to say that it will never stop This means that C_r(r) does not stop. When C_r(n) is given '1' as an input value it will perform a trivial calculation - we will have it divide 10 by 1 - and it will then stop. This means that C_r(1) does stop. We are not interested in what C_r(n) does for other values of n. We have only designed it to deal with the values '1' and r.

The algorithm C_k(n) also has to be processed by A(q,n) and C_k(n) accepts two possible values: k and r. While C_r(n) was a fairly simple algorithm, C_k(n) is a little more complicated. If we consider our algorithm A(q,n) with two identical inputs, that is to say A(n,n), then C_k(n), as in Penrose's attempted proof, is simply an algorithm that accepts one input and behaves in the same way as A(q,n) when two identical inputs are passed into it. Depending on how the algorithms are numbered it is possible that there may be more than one algorithm that meets this standard: if that is the case we only need one of them to give us our value of k. That is to say, the value of k is such that C_k(n) = A(n,n).

Algorithm A(q,n) is expected to accept details about other algorithms and their inputs and tell us if these algorithms do not halt. The possible 'runs' that can be made for Algorithm A(q,n), and their associated questions, are as follows:

A(r,r) - does C_r(r) not halt?
A(r,1) - does C_r(1) not halt?
A(k,r) - does C_k(r) not halt?
A(k,k) - does C_k(k) not halt?

Algorithm A(q,n) is therefore expected to be capable of answering four distinct questions.

As Penrose did in his proof we will assert the right to specify a vocabulary for A(q,n). We will use this vocabulary, which should look familiar by now:

A(q,n) will halt if, and only if, it determines that C_q(n) will not halt. We have no interest in the cases when A(q,n) determines that C_q(n) will halt, or when A(q,n) cannot determine whether or not C_q(n) does not halt: all that we demand is that A(q,n) only halts when it determines that C_q(n) does not halt.

Now, we will look at whether or not A(k,k) can actually give us the answer. You probably will not be surprised to learn that I am about to 'prove' that it cannot do this, using assumptions similar to those of Penrose, before refuting my own proof by means of a vocabulary change.

Let us first consider A(q,n) when it is being asked about algorithm C_r(n). C_r(n) was included simply to ensure that A(q,n) is answering questions about an algorithm, other than itself and is less trivial than it might otherwise be. A(q,n) is expected to answer two questions about C_r(n) and these correspond to A(r,r) and A(r,1).

A(r,r) corresponds to the question 'Does C_r(r) not halt?' From the definition of C_r(r) given previously we know that C_r(r) will enter an infinite loop. C_r(r) does not halt so this means that A(r,r) should halt. This logic could easily be built into A(q,n) so that when A(q,n) detects that it has input values that make it A(r,r) it can simply be made to halt. A(r,r) does not seem to pose any problems.

Let us now consider A(r,1). A(r,1) corresponds to the question 'Does C_r(1) not halt?' From the definition of C_r(r) given previously we know that C_r(1) divides 10 by 1 and then halts. This means that A(r,1) should not halt as it is only valid for A(q,n) to do this when it determines that the algorithm it is analysing does not halt. This logic could easily be built into A(q,n) so that when A(q,n) detects that it has input values that make it A(r,1) it can simply be made to enter an infinite loop. A(r,1) does not seem to cause any trouble.

Let us now consider A(k,r). A(q,n) is being asked the question 'Does C_k(r) not halt?' From the definition of C_k(n) given previously C_k(n) is equivalent to A(n,n),so the question can be rephrased as 'Does A(r,r) not halt?' A(r,r) should only halt to signify that C_r(r) does not halt. It is true that C_r(r) does not halt so A(r,r) should halt (we looked at this case above), implying that C_k(r) should halt and, therefore, that A(k,r) should not halt. As with the previous cases, there is no reason why the logic to make A(q,n) behave in this way could not be built into it.

We will now consider the final case: A(k,k). A(q,n) is being asked the question 'Does C_k(k) not halt?' From the definition of C_k(n), C_k(n) is equivalent to A(n,n), so the question can be rephrased as 'Does A(k,k) not halt?' The contradiction occurs now: A(q,n) is now faced by the same kind of problem that algorithm A(q,n) had in Penrose's attempted proof. A(k,k) is being asked if A(k,k) (that is to say, itself) does not halt and is being asked to halt to indicate if this is the case. If A(k,k) does halt then A(k,k) is actually claiming that A(k,k), which is C_k(k), does not halt and it is being inconsistent. We require A(k,k) to be consistent so we can say that in this situation A(k,k) does not halt. This is despite the fact that C_k(k) does not halt.

This last example shows a limitation in Algorithm A(q,n). We know that C_k(k) will not halt, yet A(k,k) is incapable of halting to tell us this fact.

The Proof Refuted

Have I really just proved anything about the capabilities of algorithms? Does my demonstration of what A(q,n) cannot do give us any deep insight into computing science or thought? You will probably not be surprised when I say that the answer is 'no'. The proof that I have just constructed is useless for these purposes. We will refute it now by doing nothing more than a simple vocabulary change. To refute the last proof I used a number of different vocabularies, but for this example we will just use one simple vocabulary that provides minimal information as follows:

To indicate that C_q(n) will not halt, A(q,n) will output '1'. A(q,n) must never output '1' unless it has determined that C_q(n) will not halt.
A(q,n) is not required to halt to make an output.

This vocabulary makes no mention of halting to communicate results, nor does it allow A(q,n) to give any indication if it determines that C_q(n) will halt or if it determines that it cannot determine whether or not C_q(n) will not halt. The vocabulary allows A(q,n) only to be used for the sort of purpose originally envisaged for Penrose's algorithm A(q,n), except that that this algorithm solves problems within a smaller domain.

It should be clear now that with this new vocabulary A(q,n) can actually be constructed to solve all the problems which it is supposed to solve, including the one that is supposed to force it into a contradiction. Now, A(k,k) can simply output '1' to indicate that C_k(k) and hence A(k,k) will not stop. Following this input A(k,k) need only continue running forever to maintain consistency. It does not even have to do this. A(k,k) could actually stop without outputting '1', which would also be consistent: A(k,k) would simply have stopped without making the output required to tell us that C_k(k), and hence A(k,k), will not stop - this is quite reasonable given that A(k,k) does stop in this situation. I prefer the first approach - A(k,k) not stopping, because it stays closer to the behaviour of A(q,n) in the original proof and involves producing a version of A(q,n) which can solve the problem while the second approach merely produces a version of A(q,n) which does not need to solve the problem as its behaviour now is not of the type about which A(q,n) needs to answer.

A change in vocabulary allows the A(k,k) case to be answered easily. It would also be easy to arrange for the other cases that A(q,n) is supposed to deal with to be incorporated into A(q,n). These were:

A(r,r) - does C_r(r) not halt?
A(r,1) - does C_r(1) not halt?
A(k,r) - does C_k(r) not halt?

These cases are easily dealt with as follows:

C_r(r) enters an infinite loop so A(r,r) would output '1' to indicate that C_r(r) does not halt. Whether it then halts or not is immaterial to us: we could have it halt if we liked.

C_r(1) halts so A(r,1) would not output '1'. Whatever A(r,1) does, as long as it does not output '1', is of no concern to us: we could have it halt if we liked.

The behaviour of C_k(r) needs slightly more consideration. Previously, C_k(r) did halt, but now we need to look at this again. C_k(r) is equivalent to A(r,r) and whether or not A(r,r) halts depends on the preference we just adopted for it. If we decided that A(r,r) should output '1' and then halt then C_k(r) will halt and A(k,r) should not output '1'. If we decide that A(r,r) should output '1' and not halt then A(k,r) should output '1'. What A(k,r) does after this (whether or not it halts) is immaterial.

None of this involves any paradoxes yet we had a 'proof' that an algorithm that could achieve all of this is impossible as it should get stuck with the A(k,k) case. That 'proof' was based on the same assumptions used in Penrose's proof, the only difference being that our version of A(q,n) was designed to deal with a smaller set of algorithms and possible inputs.

If a proof that uses Penrose's assumptions in a special case collapses in this way then we should expect Penrose's proof itself to be invalid.

This 'proof' and its failure should address the concerns about triviality, although I think them invalid anyway, that I raised previously. Although the algorithm A(q,n) is still considering a special case it is now able to answer four different questions, comprising questions about two algorithms, each with two possible inputs.

Possible Objections

Some readers may still have objections. Previous objections may still be raised and new ones may be made. I shall examine some of the more obvious ones now:

Objection 1: You have tried to show that no paradox is implied by an algorithm that can solve your special case problem, but we cannot be sure that this can actually be built. How do you know that some problem would not arise if we actually tried to make an algorithm that did this? In particular, for the case A(k,k) the algorithm would have to recognise when it has been provided input values that refer to itself. It is easy for you to say that we can include code to do this, but how would it work? As an example of one problem, let us suppose that we write the code for the algorithm and put some arbitrary number in place of k in the part of code that is supposed to recognise when it is dealing with the A(k,k) situation. Let us now suppose that we somehow compute what the value of k should be that we need to put into the algorithm and replace this arbitrary value of k with the true value of k. The mere act of doing this will change the algorithm A(q,n) and this will change the value of k! This could make it impossible to construct an algorithm to recognise the A(k,k) case and 'know' that it has to perform the actions that you envisage for it.

The issue of how we would build such an algorithm is getting away from the main subject. The issue is not about how easy it would be for humans to make such an algorithm, but it is about whether such an algorithm implies any contradictions. If you have trouble imagining humans easily making the code to recognise the A(k,k) case then imagine the code being made as a result of a monkey randomly typing or any one of a number of other unlikely scenarios. We do not need to worry about how the code can be made by us as long as we can show that the argument that its existence involves a paradox has failed.

Objection 2: That answer was evasive! How do you know that the difficulties involved in producing an algorithm that can recognise the A(k,k) case are not caused by some underlying paradox in the very existence of such an algorithm?

If anyone is making this objection it is clear that I will have to go further and give a convincing description of how the algorithm A(q,n) could be constructed by humans for this special case. The method that I describe may not be the best - it is not intended to be efficient - but it should address any concerns about the algorithm's construction involving paradox.

To make matters easy to deal with, let us imagine that our algorithm is being written in some common type of machine language - a language containing the sort of commands that are executed directly by the CPU (central processing unit) microchip in a conventional computer. Some readers may object that I should be using a Turing machine, but such a language would be a Turing machine: one of the major ideas of Turing machines is that a universal Turing machine can simulate any other computer so any solution that I can produce for a machine code algorithm could certainly be implemented on the sort of instruction tape machine that is closer to Turing's original ideas and that is used in Penrose's proof. I am simply using more conventional machine code as some readers will have a good understanding of the sorts of operations that can be performed in it, making a demonstration easier.

The chosen vocabulary demands that A(q,n) outputs '1' when it has determined that C_q(n) will not halt. This could be done in a variety of ways; for example, the algorithm could write data into the display memory of a computer, causing the digit '1' to be displayed onscreen or it could send the output to a printer, causing '1' to appear on a printout. We need not be too concerned with the specifics of how the output is produced.

We also need a way of getting the input values q and n into A(q,n). Ideally this should be done in a way that makes it easy to determine which algorithm corresponds to a particular value of q and in a way that does not make the argument vulnerable to any charges of triviality. The way in which we will do this is simple. Any computer program can be encoded as a sequence of numbers and any sequence of numbers can be expressed as a single number. All we need to do do is take each symbol in the program and replace it by a number and then write each such number down, left to right, going from the start of the program to the end. The resulting number can then be input into A(q,n). We do not, in fact, even have to think of things at such a level of abstraction, though I do because Penrose discussed programs having numbers corresponding to them: we can simply take the symbols in the program for C_q(n) and say that they are parameter q. The parameter n can be dealt with in the same way. A(q,n) can therefore be passed the machine initial state represented by q and n directly.

We will now examine how we would we construct a program A(q,n) to perform the required processing that I have described.

To start with we will not work on A(q,n) directly. We will look at the issue of C_r(n) to determine what an appropriate value of r would be - to put this another way, I described what a program r would do in the proof, but I did not give any value of r. We need to find what r is so we can get A(q,n) to recognise it when it is provided as a parameter. We begin, therefore, by constructing a program, C_r(n), that has the appropriate behaviour. If it is provided with r as an input value it will enter an infinite loop. If it is provided with '1' as an input value it will compute 10 divided by 1 and then halt. What it does in any other situation need not concern us.

We could have a minor complication in the construction of C_r(n) and that is that it may seem that we need to look at the code for C_r(n) to determine the value of r needed to allow it to recognise itself in the case C_r(r), yet when this value of r is determined and incorporated into the code for C_r(n) the act of such inclusion will change the value of r, making the value that has just been included wrong! This is the sort of idea that was raised in the objection as a possible cause of a contradiction that I have missed, though here it relates to C_r(n) rather than to A(q,n) itself.

A simple resolution is available. We can arrange for C_r(r) to determine its own value of r after it starts running. This would involve it executing a command to read the contents of each memory location in its program and store this in another part of the computer's memory where it will not altered in any way. This processing would be performed immediately after C_r(n) started to run. There is no paradox involved in a program accessing its own code in this way. When C_r(n) receives a sequence of symbols as the inputs n it can simply check this against the copy of its own code stored in its memory to find out if it is dealing with the case C_r(r).

The C_r(1) case is simpler. When C_r(n) detects that it has been provided with '1' as an input it will simply divide 10 by 1 - we do not really care what happens to the result - and then halt.

In this way C_r(n) can be easily constructed.

We will now deal with the construction of A(q,n) itself.

To start we will write some subroutine that makes the output of '1' required when it had been determined that C_q(n) will not halt. What it does need not concern us: we can just call it to output '1'.

We now need to deal with these cases so that A(q,n) answers the corresponding questions:

A(r,r) - does C_r(r) not halt?
A(r,1) - does C_r(1) not halt?

When inputs are provided to A(q,n) it will check these inputs against a list. The cases involving C_r(n) are easily dealt with.

If q=r and n=r this corresponds to A(r,r) - does C_r(r) not halt? C_r(r) does not halt. A(r,r) will therefore output '1'. After it has done this it will halt, which is an arbitrary choice that I made.

If q=r and n=1 this corresponds to A(r,1) - does C_r(1) not halt? C_r(1) does halt. A(q,n) will therefore not output '1': it will simply halt, which is an another arbitrary choice as I could have had it loop forever.

We also have to deal with these cases:

A(k,r) - does C_k(r) not halt?
A(k,k) - does C_k(k) not halt?

These cases require A(q,n) to be able to recognise when it has been provided with k as an input value. This could cause a problem similar to the one we had with C_r(n): the value of k is dependent on A(q,n) itself so determining it and then incorporating it into A(q,n)'s code will invalidate it. Just as we did with C_r(n) we will solve this problem by having A(q,n) determine the value of k itself.

To obtain the value of k we should first consider what k actually is. C_k(n) is an algorithm that is equivalent to A(n,n), just as it is in Penrose's proof. For any algorithm A(q,n) we should be able to find such an algorithm C_k(n) using a fairly mechanical method, which is important as we are going to get A(q,n) to do this.

The value of k will be obtained by code which is inserted at the start of A(q,n) so that it runs before the checks on the input values that have just been discussed. Whatever method is used to determine k, it will involve A(q,n) having to make reference to itself. For this reason the first act of A(q,n) will be to read all of the memory locations used to store its program instructions and to store this data in another area of memory. We will call this copy of the program A₂(q,n).

We now need to use A₂(q,n) to obtain k. There are a number of ways in which we could do this:

One way in which we could obtain C_k(n) is simple. We would simply take A(q,n) and say that C_k(n) is exactly A(n,n). This would seem to suggest that we require the input value n to be placed in C_k(n) twice and it would also seem to require this for every program C₁(n), C₂(n), etc. While this may not be desirable it would be easy to use such an approach. It would simply involve using A₂(q,n) as C_k(n) and as the value of k.

Another approach would be to say that C_k(n) must be an algorithm that does only accept one input rather than two identical inputs. With this approach the obvious action would be to derive C_k(n) from A₂(q,n) in some way by presuming that both input parameters in A₂(q,n) are the same. If the input values are embedded in the program (for example by being placed at certain memory locations, maybe as a header or footer in the program just before it starts to run), then the location in memory where the second input value is stored could be cleared. Code is placed at the start of A₂(q,n) which, were it to be executed, would copy A₂(q,n) to make A₃(q,n), but to introduce one difference into A₃(q,n): this difference would be that the same input parameter, q, would been placed in A₃(q,n) for both q and n. Once this 'corrected' version of A(q,n) had been produced control would then be passed to it, which could be done by a machine code 'unconditional jump' command. A₃(q,n), however, will never actually be produced. The code which will produce it is built into A₂(q,n) to allow A₂(q,n) to be used as C_k(n). The sole purpose of doing this is so that A(q,n) can read all the memory locations in A₂(q,n), once it contains the appropriate code, and use these to obtain the value of k.

It should be noted that there may be more than one algorithm C_k(n) which is equivalent to A(n,n). Various ways can be imagined of taking A(q,n) and finding an equivalent algorithm C_k(n) though this could depend on how the algorithm numbering system works. All that is necessary is for us to choose one method, such as that which has just been discussed, or if we think we can be sure from Penrose's proof that C_k(n) is produced from A(n,n) using a very specific method, to use that method here. We should be aware that two of the questions that A(q,n) is required to answer refer to k, so selection of a particular method for determining k is actually selecting which of a number of possible questions to ask. Whether we choose one in an arbitrary way or select one that may be implied by Penrose's proof has no effect on the outcome.

When A(q,n) has the value of k it can use this to deal with these two cases:

A(k,r) - does C_k(r) not halt?
A(k,k) - does C_k(k) not halt?

The code to check for these cases can be inserted into A(q,n) in the same place as the code to check for the other two cases. The processing which is performed is now simple.

If q=k and n=r this corresponds to A(k,r) - does C_k(r) not halt? Comparison of its input parameters with the stored values of k and r should allow A(q,n) to recognise that it is dealing with this case. The question is asking if C_k(r) does not halt, equivalent to asking if A(r,r) does not halt. A(r,r) does halt, so the answer is 'no'. When A(q,n) recognises that it is dealing with the A(q,r) case therefore it will not output '1' and will halt, though the halting is not mandatory.

If q=k and n=k this corresponds to A(k,k) - does C_k(k) not halt? Comparison of its input parameters with the stored value of k should similarly allow A(q,n) to recognise that it is dealing with this case. This is equivalent to 'does A(k,k) not halt?' To deal with this the algorithm will not output '1' and it will then enter an infinite loop. As this is A(k,k) then it has acted entirely consistently for dealing with the case of an algorithm (itself) that does not halt.

Objection 3: You have demonstrated that an algorithm can exist that serves as a refutation of your 'proof', but this algorithm is still too trivial: what is being demanded by the questions is too trivial. All that is being examined here is a special case with four possibilities. It is hard to see how any computation is going on here. Penrose's proof involves an algorithm that performs a substantial amount of computing, whereas your algorithm does not and achieves nothing.

This is not an 'amount of processing' contest between algorithms. I can understand the objection. My algorithm merely seems like the throwing of a few switches, whereas Penrose's algorithm A(q,n) may seem to be doing something more profound, but Penrose's algorithm, if examined closely, must itself reduce to a sequence of almost trivial decisions: any algorithm must. To say that the assumptions in Penrose's proof are only for reasonably 'profound' algorithms, and should not be expected to work for trivial algorithms, may seem attractive, but it is merely a value judgement. If we did adopt such an idea how would we say at what level of sophistication Penrose's assumptions would start to be valid and how would we justify this? The arbitrariness of this should be reason enough to view it as wrong.

This second 'proof' and its refutation were given to deal with objections based on triviality and the algorithm here is being required to do more than the algorithm in my previous 'proof'. A strong defence against the charge of triviality is that the list of questions that need answering in this proof can be extended. I chose to have the algorithm deal with two algorithms, each with two valid inputs, yet it could be easily amended to deal with more algorithms, with more valid inputs for each, and the proof would still collapse each time. It would seem strange to persist with a triviality argument all the way through this.

Objection 4: Yes, but each time you added the capability to deal with a new special case you would just be adding a crude switching mechanism to your program. Nothing of any significance is happening.

I want to make it clear that I am not attempting to use this as an argument that A(q,n) could be created in such a way: my argument is that Penrose's whole proof collapses in special cases that are substantially the same as his situation.

The triviality, or lack of it, when the capability to recognise a new algorithm is added to A(q,n) is irrelevant. The attempted proof was not about triviality: it was about whether or not the giving of certain answers by algorithms implies contradictions. The fact that the change in vocabulary removed this issue entirely shows that this was merely an artefact of the vocabulary used. It may be possible to extend A(q,n) by using a relatively small set of generalised rules, or a relatively small number of lines of code, that can deal with a large number of cases. We could also debate, if we liked, the merits of using such an approach and whether or not the method by which A(q,n) answers its questions really matters, what the various methods are that A(q,n) could be made to use and how this may relate to artificial intelligence and its feasibility. None of this would be relevant to this proof or Penrose's: all that we are concerned about is whether the answering of certain questions by algorithms causes any contradictions that are not faced by humans.

Objection 5: The fact that your 'proof' relates to a special case means that it is no surprise that it fails. Your proof involves your algorithm A(q,n) being asked a list of questions. One of these, the one relating to the A(k,k) case, is self-referential and this is what causes the difficulties for A(q,n) in answering your question. Your algorithm A(q,n) is only prevented from answering as the question refers to A(q,n), but there could be lots of other algorithms that are not A(q,n) that could answer your question. This is because your A(q,n) is a special case that does not encompass all algorithms at which your question could be directed and it makes your proof unsound. Penrose's algorithm A(q,n), conversely, comprises all knowably sound methods of determining if an algorithm will not halt, so the same trick cannot be played with it as it actually comprises any other candidate algorithm at which the question could be directed. Any alternative algorithm proposed as a candidate for answering Penrose's question could only do so by not being A(q,n) and this would imply that it cannot have all the capabilities of A(q,n).

Self-reference is in the very nature of my question and I would point out that should an alternative algorithm be proposed to answer my question in this way, without any vocabulary change, it would also lack the ability to answer the self-referential form of the question. It would lack some capability in the same way that an alternative algorithm proposed to answer Penrose's question would lack that same capability.

None of this need concern us as the objection is another straw man argument and can be shown to be invalid well before we have to worry about such matters. I have not used this idea of finding an alternative algorithm that can avoid self-reference to destroy my own proof. I have shown, instead, that regardless of the merits of such an argument, my proof fails for an entirely different reason. That reason is that a vocabulary change allows algorithms to be constructed that can consistently answer all the questions that A(q,n) is supposed to answer. This has nothing to do with how general A(q,n) is and simply exposes flaws in the assumptions behind my failed proof.

Objection 6: Your proof involves self-reference in a way that Penrose's does not. Your question directly refers to your algorithm A(q,n) as the value k, referred to in your question, is dependent on the particular algorithm A(q,n) used. If a different algorithm A(q,n) were used then the value of k would change, meaning that the question would change. With Penrose's proof this does not happen. The problem that Penrose's algorithm is supposed to solve is that of finding out if any algorithm does not halt for which a knowably sound method of determining this. This problem remains the same, whatever form A(q,n) takes. Maybe this causes some problem with your argument?

Penrose's argument involves a similar degree of self-reference yet this is a little less obvious because the questions are described in more general terms that involve stating what A(q,n) is supposed to do about all algorithms C_q(n) for which knowably sound methods exist. It may seem that this lacks the same self-reference, but if we actually listed all the questions that Penrose's algorithm A(q,n) is supposed to answer the A(k,k) case would have the same degree of self-reference. If another algorithm B(q,n) were used to examine the A(k,k) case then this self-reference would disappear, but if we tried to use this other algorithm to answer all the other questions asked of A(q,n), using the same vocabulary, then there would be another case for which B(q,n) could not answer as it would involve values of q and n that relate to algorithm B(q,n) in the same way that the A(k,k) case related to A(q,n) itself.

The main problem with this objection, however, is that it does not show how it is supposed to apply. If there is some difference between the type or amount of self-reference in my 'proof' and Penrose's exactly how is it supposed to leave my 'proof' as a failure but Penrose's intact? The refutation I used on my proof had nothing to do with this.

Objection 7: You claimed that you have not cheated by simply creating another algorithm to refute your proof. You did however make a vocabulary change. To all intents and purposes this means that your 'successful' algorithm is not even answering the same questions anymore.

It is debatable whether or not this objection is coherent: what standards should we apply to say that the question is the 'same' or 'different' after a vocabulary change? It is certainly irrelevant. Even if the question were determined to be different, it would suggest that Penrose's question could be answered by using a similar vocabulary change. Let us suppose that we were attempting to construct an intelligent machine and came across this sort of problem with one of its components, so that it seemed to us that some subroutine in its code could not be constructed to give an answer that was needed. We could simply make a vocabulary change and then develop the subroutine to provide the answer in the new vocabulary! Whatever parts of the code needed to use that answer could do so without there being any external evidence of it having been obtained with a different vocabulary. Whether or not it is answering the same question is purely semantics: all that matters is whether or not an algorithm could be used for the same purpose.

Objection 8: Your first demonstration involved an algorithm that could do nothing but tell us if it would not stop. Your later demonstration involved an algorithm that could answer three more questions. You have also pointed out that this algorithm could be extended further by incorporating more code into it. This does not prove anything. In Shadows of the Mind Penrose already recognises the argument that A(q,n) could be extended with extra code, just like the simple code to deal with one of the cases in your example, to allow it to answer for the case with which it cannot deal. He shows that this is a fallacy as, if this would really help, it should be entirely possible to include the capability to derive this code into A(q,n). Arguing that we can simply construct A(q,n) from a number of simple blocks of code, each of which recognises a special case, or that we could extend Penrose's algorithm A(q,n) in this way, is a waste of time: Penrose has been there before you.

This objection is another straw man argument. While one method of arguing against Penrose is to point out that A(q,n) could be extended to deal with the A(k,k) case I have not used this argument in this document. The intention has been to show that Penrose's assumptions lead to other 'proofs' that fail. The idea of adding code to extend A(q,n) has simply been used to allow construction of versions of A(q,n) that can act as a clear refutation of my own special case 'proofs'.

Objection 9: You may have demonstrated that there is no reason why an algorithm could not answer the question posed by Penrose, but what if we made the question harder so that your vocabulary change 'trick' would not work? This would be done by making the sort of behaviour for which A(q,n) is looking more general in nature. Your vocabulary change only works because there is more than one way of saying the same thing, effectively. As an extreme example, and there could be other ways that we could strengthen Penrose's argument, we could try to construct a form of A(q,n) which is supposed to examine every algorithm that can provide a positive or negative answer, and for each of these algorithms, to tell us if it does not provide any form of negative answer. When such an algorithm analysed its own initial state it could never tell us that it did not provide a negative answer without contradiction. This means that we know that A(q,n) would not answer in the negative for this case yet A(q,n) is not capable of telling us. The argument would now resist your vocabulary change as any vocabulary you could use which involved positive or negative meanings would be swallowed whole by it.

If it is necessary to extend the question in this sort of way then we are not really dealing with Penrose's proof, the subject of this article, anymore. Nevertheless, I think I should at least make some attempt to deal with this sort of objection.

I mentioned earlier, with my word game, that it would be possible to go on changing the question in an attempt to make it more difficult to answer. This is an example of this and it will achieve nothing. There is no reason to presume that a human brain could not be prevented from consistently answering by questions which have been generalised to the point of absurdity like this.

This objection seems to me to actually weaken Penrose's position rather than strengthen it. When we think about a general question like this we should ask how we interpret the output of any individual algorithm C_k(n) as, in this case, positive or negative. We would have to use some sort of interpretative process or algorithm and it should be apparent that quite a lot is now going on from the time the information about the result first exists in A(q,n) to the time that it exists in a human brain as the knowledge that A(q,n) gave a negative answer. This makes it apparent that, for an extreme case like this, we are not considering A(q,n) in isolation, but also with an interpreting process that actually produces our knowledge of what its output is. The interpreting process does matter and is clearly capable of losing information that has been obtained from A(q,n) or failing to acquire it from A(q,n) in the first place. It is conceivable that this could happen even if the interpreting process is almost trivial and this gives a useful way of thinking about what is wrong with Penrose's proof.

Oracle Algorithms

If you are still not convinced I should point out that in Shadows of the Mind Penrose himself exposes a problem in the Godel-Turing proof [8]. He mentions oracles and explains that an oracle is a hypothetical device considered by Turing. An oracle could solve any halting problem of the type that we have been considering. An oracle can, of course, not exist in a universe which lacks some unorthodox physics of the sort, for example, proposed by Penrose, but that does not prevent us from using it as a conceptual device.

We can imagine the services of an oracle being provided to A(q,n), making A(q,n) an oracle algorithm. An oracle algorithm is simply an algorithm that has access to the services of such an oracle: it can call the oracle at any time and ask it if a particular algorithm halts. When A(q,n) has been given the value of q and n and needs to know whether or not C_q(n) will halt, it can simply send a request for the answer to an oracle, wait for the oracle to return an answer and then continue processing, ultimately outputting the answer. Penrose himself considered such a case by imagining A(q,n) being an oracle algorithm (an algorithm that has access to the services of such an oracle) being applied to the oracle algorithm C_q(n). This simply means that, as well as letting A(q,n) have access to the services of an oracle then all of the algorithms C₁(n), C₂(n), etc also have this capability.

Strangely enough, it does not help: even if A(q,n) is allowed to consult an oracle and obtain the answer, it is still not possible for A(q,n) to assert this answer by halting without contradiction!

It should be clear now that all of this is trivial and is being caused by vocabulary restrictions. After discussing his consideration of an oracle machine A(q,n) considering other oracle algorithms C_q(n), Penrose seems to clutch at straws. After considering various levels of oracle machines he states:

Yes, this is alarming indeed! It seems like the problem has no solution, so we clearly need something that is beyond what we can easily imagine - something that goes beyond the capabilities of even an oracle-Turing hybrid machine and acts as a deus ex machina to restore the argument to plausibility.

I have a different idea: the proof is wrong.

Penrose is aware of how people like me are going to take this when he admits:

Penrose has made other arguments that are not considered here, but with regard to the Godel-Turing proof this article has come to terms with the arguments that he has given. There is no need to hypothesise some vague mathematical idea of 'machines beyond all levels of oracle machines' as a way out.

Conclusion

Penrose's Godel-Turing argument does not show anything really profound about the capabilities of algorithms. It attempts to show that an algorithm cannot answer a certain question, but this is merely an artefact of the rules that the question imposes on the way that the algorithm communicates its results. The problem being presented to the algorithm is merely a trick question that the rules of the game prohibit it from answering. Humans can be put into the same situation by various questions and we do not see anything profound in this.

It is possible to refute Penrose's proof by showing that his assumptions regarding the validity of selecting a particular method of communication, or vocabulary, for his algorithm can be used to construct other 'proofs' regarding special cases which can then easily be demonstrated to fail by producing algorithms that are not supposed to exist according to the 'proofs'. This suggests that Penrose's use of a particular vocabulary for this purpose is flawed and that his attempted proof is incorrect.

This does not imply that Penrose's entire case is necessarily wrong: he makes other arguments that the human brain must use non-computable physics that have not been addressed in this article.

References

[1] Penrose, R. (1989). The Emperor's New Mind: Concerning Computers, Minds and the Laws of Physics. Oxford: Oxford University Press.

[3] Penrose, R. (New Edition, 1995). Shadows of the Mind: A Search for the Missing Science of Consciousness. London: Vintage. Chapter 2, pp64-76.
(Originally published:1994. Oxford: Oxford University Press)

[4] Ibid. Chapter 2.6, p83.

[5] Ibid. Chapter 3.24, pp190-193.

[6] Ibid. Chapter 2.6, pp79-80.

[7] Ibid. Chapter 2.6, pp81-82.

[8] Ibid. Chapter 7.9, pp379-381.

[9] Searle, J. R. (New Edition, 1998). The Mystery of Consciousness. London: Granta Publications. Chapter 4, pp 89-93.
(Originally published:1997. New York: The New York Review of Books)

[10] Lucas, J. R. (1961). Minds, Machines and Godel. Philosophy, 36, p112-127.

[11] Lucas, J. R. (?). Minds Machines and Godel. Home page of J.R. Lucas, Fellow of Merton College, Oxford. Retrieved on 10 September 2004 from http://users.ox.ac.uk/~jrlucas/Godel/mmg.html.
(An online version of Lucas's paper from reference [10]).

[12] Hofstadter, D. R. (New Edition, 2000). Godel, Escher, Bach: an Eternal Golden Braid. London: Penguin Books. p477.
(Originally published:1980. New York: Vintage)

[13] Duff, A. (1986). Pascal's Wager And Infinite Utilities. Analysis, 46, pp107-109.

[14] Holt, T. (2003-2004?). Anselm's Ontological Argument. Philosophy of Religion. Retrieved on 6 October 2004 from http://www.philosophyofreligion.info/anselmontological.html .

[15] Banach D. (?). Anselm's Ontological Argument. David Banach, Department of Philosophy, St. Anselm's College. Retrieved on 12 September 2004 from http://www.anselm.edu/homepage/dbanach/anselm.html.