Archive 1Archive 2

Computer vs Computable

It also implies that a computer can never be programmed to answer all mathematical questions.

I'm not sure this is the case. It implies that you cannot choose a formal system and then simply work out all its consequences, and as a result get the answer to all mathematical questions -- thus it proves that one potential way of a computer answering all mathematical questions doesn't work. But in the general case it's an open question whether computers are in principle capable of more or less intelligence than humans, and so this can only be said conclusively if either the AI question is resolved, or it is shown that it is in principle impossible to answer all mathematical questions (whether the answering is done by a human, computer, or something else). Delirium 04:07 1 Jul 2003 (UTC)

It's misleading. 'Answering all mathematical questions' is like running through a recursively enumerable set - can be done if you have an infinite supply of CPU cycles and don't mind waiting infinitely long.

Charles Matthews 04:37 1 Jul 2003 (UTC)

I have removed the sentence Charles Matthews objects to but not because it is wrong. The far more general point is true. The theorem does not only imply that computers cannot answer all mathematical questions; it implies people cannot either and, more than that, it implies that some mathematical questions are unanswerable. The sentence I have removed was written by someone who does not fully understand this theorem. Godel is often trotted out to support an anti-AI point of view, I suspect that that is what has happened here.

Psb777 09:44, 10 Feb 2004 (UTC)

I respectfully disagree. The remark is IMO correct and relevant and therefore should stay. What the motives were of the one who wrote it is simply irrelevant. In fact, it could very well have been me that put it there, and I hold no such view. Removing correct information from an article in Wikipedia requires more justification than that. -- Jan Hidders 17:30, 12 Feb 2004 (UTC)

You would be right if the "correct" thing I removed was not just a small part of the truth. But I said it was not wrong which is not quite the same thing as saying correct. There are a lot of consequences of Godel's theorems, the interpretation I removed was not wrong but it was misleading. Why are not all the consequences of the theorem listed? [Because there are pages for the theorems!] Why this one (sub-)consequence? If the comment goes back then the general point must be what is replaced, not one that is needlessly computer specific. Paul Beardsell 07:16, 13 Feb 2004 (UTC)

I don't agree that it is needlessly computer specific, and I would argue that it is the most important consequence from which almost all other consequences follow. In fact, it is essentially equivalent with the first theorem, so calling it "a small part of the truth" is, well, a bit misleading :-). Moreover, it illustrates why this is such an interesting theorem, so it certainly has its place there. If you don't like how it is worded, then by all means reword it, if you think it is too specific then make it more general, but removing statements from Wikipedia should always be done with the greatest care. So, since we have to stick to NPOV I will put it back and reword it a little so it reflects a bit more your point of view, even though I in fact disagree. Let me know if you find this unacceptable. -- Jan Hidders 10:28, 13 Feb 2004 (UTC)

I like your new wording. What part of it do you disagree with? And I'm being needlessly argumentative, now that you have crafted wording with which I agree, but in what way is the statement "It also implies that a computer can never be programmed to answer all mathematical questions" not computer specific? And, this quesion from interest only, do you think that the brain is capable of evaluating a super set of the algorithms which a computer can evaluate? Paul Beardsell 14:23, 13 Feb 2004 (UTC)

Good, I'm happy you like the new wording. What I myself don't like about it, is that it now is a bit academic and abstract. The answer to your last question is "extremely unlikely and without any evidence whatsoever". However, I don't think there is a definitive proof that shows that a human brain or all humanity as a collective cannot do noncomputable things. -- Jan Hidders 13:05, 14 Feb 2004 (UTC)

There isn't a definitive proof that there isn't reincarnation either. Paul Beardsell 01:04, 16 Feb 2004 (UTC)

There is however definitive proof that this discussion is over, if ever it started. ;-) Remember that Wikipedia is not a discussion forum and contributions should be made in the spirit of cooperation. Trying to lure people into little debates is usually not very productive. Good luck with your other contributions to Wikipedia. -- Jan Hidders 23:45, 16 Feb 2004 (UTC)

This page is the discussion forum for the article. Paul Beardsell 23:11, 17 Feb 2004 (UTC)


I am disappointed that the discussion has not continued. Upon reflection I agree with Jan Hidders that his new wording is academic and abstract. We have gone from something which was partially correct and perfectly understandable albeit misleading to something which is correct but jargon. I intend to replace the current text as follows. This removes the perceived anti-AI slant whilst maintaining readability. I propose we define computable and to do so elsewhere - and I hope the link I have used is considered adequate.

Comment to Aleph4 march 21 Thanks for your prompt reaction. I was prepared to wait four weeks for the first reader. The word ‘specific’ in my text seems to be misleading. So please omit it. The n in Gödels Z(n), itself not a symbol of System P, stands there for any positiv whole number out of the infinite sequence 0, f0, ff0, fff0, ...... etc. Another error that I just see in my text lies in my description of the number representations: evidently, the symbols f have to be put in front of the symbol 0 (zero) and not x ! Sorry, I must have slept! The symbol y in Gödels Z(y) however is a symbol of the System P, it stands there quite for itself, not for anything else, and, again I have to correct myself, its Gödel-number in Gödels paper is 19, my 13 comes from the Nagel-Newman booklet, from where I anyway assumed the way of writing the formulae to get them on a single line of typing. Yours Ginomadeira

Then: It also implies that a computer can never be programmed to answer all mathematical questions
Currently: It also implies that the set of truths about natural numbers is not recursively enumerable, which means that there is no algorithm that can enumerate all these mathematical truths.
New: It also implies that not all mathematical questions are computable.

Paul Beardsell 03:34, 22 Feb 2004 (UTC)

I do not see any meaning in It also implies that not all mathematical questions are computable. How can a question be computable?

There are two ways (well ... infinitely many really) of phrasing the incompleteness theorem:

  1. There is no axiom system that generates all mathematical truths.
  2. There is no computer program that lists all mathematical truths.

Of course the two are equivalent, but the equivalence is itself an interesting fact. The first of these is already in the article: These theorems ended a hundred years of attempts to establish a definitive set of axioms to put the whole of mathematics on an axiomatic basis... Why not use the sentence It also implies that a computer can never be programmed to answer all mathematical questions for the second? Aleph4 00:30, 11 Feb 2005 (UTC)

Brno or Brünn? Or both?

Where was Gödel born?

  1. Brno
  2. Brünn, now Brno
  3. In a city which is now (2005) known as Brno in the English-speaking world, but which in his time (at least by him and his family) was called "Brünn".

I think that (1) is misleading, and (3) is too verbose, so I prefer (2), which really is an abbreviation for (3). Please do not remove "Brünn" without explaining it here. -- Aleph4 23:40, 9 Apr 2005 (UTC)

In fact the only misleading proposal is (2) suggesting nonexistent renaming from Brünn to Brno. He was born in the city called Brno in Czech and Brünn in German. Since his family was German-speaking he most likely called his hometown "Brünn", but it doesn't make the Czech name (from which the German version was once derived) less valid or less English. My proposal (4) is therefore "Brno (Brünn)" with the Czech and present-day English name in the first place and the German name with which he is also associated in parentheses. Qertis 10:09, 18 Apr 2005 (UTC)
I think it should remain in the current form (X in A, now Y in B). This is standard all over the English Wikipedia. We have to include A (here Austro-Hungary) to give information on his nationality at birth. If X (Brünn) was the then-official name of the place, we should give that too, as a matter of record. Charles Matthews 18:37, 18 Apr 2005 (UTC)

I am sure that it was an official name, but perhaps not the (i.e., the only) official one. According to Meyer's 1886 encyclopedia, the city had in 1880 "82660 inhabitants, among them 60% Germans, 40% Czechs, and 5498 Jews". (I see, so Gödel was really German after all, just like Mozart... :-)

But I am sure (again without being able to prove it) that Gödel's certificate said Brünn, not Brno. -- Aleph4 23:41, 18 Apr 2005 (UTC)