This guy asserts:

I’ll say it — the computer was invented in order to help to clarify … a philosophical question about the foundations of mathematics. (This problem being Entscheidungsproblem - The Decision Problem)

The reference here states that the Church-Turing thesis was attempting to answer this question.

My question is - is it true that modern computers are a byproduct of trying to solve 'The Decision Problem'?

(My intuition told me that modern computers were more a byproduct of trying to break Nazi encryption codes). (perhaps with some pre-war German influence).

  • 2
    $\begingroup$ there is the theoretical version and the physical version. the physical version is millenia old in the form of an abacus and also the middle ages [leibnitz calculating machine etc]. the electronic version does indeed date much to WWII mainly breaking codes & calculating projectile trajectory tables. the theoretical version ie Turing machine/lambda calculus were indeed invented by mathematicians and logicians to model/solve theoretical problems... $\endgroup$ – vzn Nov 1 '12 at 14:54

I can see his point, but I think he's really (deliberately?) confusing computation (and the mathematics thereof) and computers.

A computer is certainly a device for performing computation, but what Church and Turing created was a (well, two, but they're "the same") theoretical (read mathematical) model of the process of computation. That is, they define a mathematical system which (if you believe the Church-Turing thesis) captures what it is possible to compute on any machine that can perform mechanical computation (mechanical in the sense that it can be automated, and yes, that's a little hand wavy, but that's another story).

Computers don't work like Turing Machines (or the Lambda calculus, which doesn't even pretend to be a machine). Bits of them look kind of similar, and indeed Turing does play an important role in the development of modern computers, but they're not a byproduct of the maths, any more than aeroplanes are a byproduct of the dynamics that describe airflow across their wings.

  • 1
    $\begingroup$ One small comment. Church and Turing's models are not at all the same. They yield the same class of computable functions, though. $\endgroup$ – Peter Shor Nov 4 '12 at 22:43
  • $\begingroup$ Hence the scare quotes, it didn't seem worth going into Turing completeness for this. $\endgroup$ – Luke Mathieson Nov 4 '12 at 23:12

Just an extended comment, for those who didn't notice that "This guy" in the question is not the author of the linked blog, but refers to Gregory Chaitin.

The sentence is from the lecture: A Century of Controversy over the Foundations of Mathematics; the transcription can be found here.

It seems interesting (I'm going to read it now)!

Okay, I'd like to talk about some crazy stuff. The general idea is that sometimes ideas are very powerful. I'd like to talk about theory, about the computer as a concept, a philosophical concept.

We all know that the computer is a very practical thing out there in the real world! It pays for a lot of our salaries, right? But what people don't remember as much is that really---I'm going to exaggerate, but I'll say it---the computer was invented in order to help to clarify a question about the foundations of mathematics, a philosophical question about the foundations of mathematics.

Now that sounds absurd, but there's some truth in it. There are actually lots of threads that led to the computer, to computer technology, which come from mathematical logic and from philosophical questions about the limits and the power of mathematics.
  • $\begingroup$ GC aka "Omegaman" is an authority & also a bit biased on the subj. but his pt is well taken & it would be interesting to study/survey the symbiotic relationship how theoretical developments influence physical design & vice versa. $\endgroup$ – vzn Nov 1 '12 at 20:45
  • $\begingroup$ @vzn: I agree with you, and I would underline that in this case - like in most of the questions involving men and their actions/histories - there is not a "black or white" answer :-) $\endgroup$ – Marzio De Biasi Nov 1 '12 at 21:41

In 1936, Konrad Zuse developed what was for all intents and purposes the Z1 the first computer in the modern sense. This fact is little known but has since been acknowledged even by his international competitors, e.g. IBM. While the Z1 was not very reliable, later models (still developed during WWII) actually worked. Shortly after the war, Zuse's company began building (universal) computers for multiple major universities in Europe.

Zuse's motivation was not to gain mathematical insight, although he did develop a formal, universal programming language called Plankalkül. He primarily wanted to do away with repeated, mechanical calculations often seen in engineering -- surely a machine could perform such mindless manipulations of symbols!

Note how Zuse's early work happened concurrently and, due to different background and the political situation, mostly independently of the better known work in the US.


That is a defensible position to take. "Computational devices" existed before Turing. The idea that Turing had that was so powerful in the development of real computers was the idea of a "universal computer": i.e. a single piece of hardware that could perform any calculation by taking as input data that described a different machine -- software. This kind of universal computer was useful for Turing's investigations into decidability: this is the kind of object that is used when discussing the halting problem.

But it is also the thing that defines the modern computer, first physically realized by Von Neumann's machine. (The Eniac came first, but was not universal -- i.e. you could not just feed in a program using punch-cards, you had to physically re-wire it to get it to perform a different computation).

The idea of universal computation was arguably developed to reason about decidability, and forms the core idea of physical computer realizations.

  • $\begingroup$ George Dyson's book, "Turings Cathedral" (which despite the title is a history of Von Neumann and his development of the computer) suggests that Von Neumann was fond of Turing, and very aware of his work, and that the similarity is no accident. $\endgroup$ – Aaron Roth Nov 1 '12 at 21:00
  • $\begingroup$ [deleted this comment to edit it; now out of order] the similarity between the TM and the Von Neumann architecture is interesting and almost striking. havent seen it pointed out in historical accts. Von Neumann does not seem to have credited Turing in writing afaik. the connection between Von Neumann & Turing seems murky/unknown. $\endgroup$ – vzn Nov 1 '12 at 21:02
  • $\begingroup$ @ Aaron Roth, the first computer was K. Zuse's Z3 in the sense that it was Turing universal, although Zuse wasn't aware of that concept at the time. $\endgroup$ – Martin Berger Nov 1 '12 at 22:50

It is a common opinion among experts that Turing's work on foundation of mathematics is part of the foundation of computer science and computers. There are many ideas essential to working of modern computers that came from Turing's work. Part of the motivation for Turing's research were the question about the foundations of mathematics like formalizing and clarifying the meaning of mechanical/algorithmic computation going back to at lease Hilbert's problems.

However this doesn't mean that Turing's work was aimed at creating a computing device.

AFAIK, the code-breaking work of Turing are part of a much later period of his life.

In any case, if you want to learn more about Turing there are considerable amount of resources that you can refer to. In particular check Alan Turing's page by Andrew Hodges.

Turing work is very important but there are also many other ideas that were essential to the creation of computers. If you want to learn more about history of computing check the Wikipedia articles on history of computing, history of computing hardware and timeline of computing.


here is a very detailed history & table of modern computers by By Ulf Schünemann that can help resolve some questions of this type. however its a linear record of facts and in general its very difficult to determine the exact "multidimensional" interconnections between inventors (both theoretical & physical oriented/focused), inventions and ideas; its a big historical project that requires even more deep analysis than just looking at known/written history, and can only inherently partially succeed in definitiveness. see also The Relation between Babbage and von Neumann which emphasizes the similarity between Von Neumann architecture and Babbage differential engine.

conceptually there is clearly a tight cluster between the following work but apparently the exact historical interconnection has never been fully deconstructed (nor may it be possible because recorded history is inherently incomplete and some degree of educated guesswork and opinion is inevitable).

strangely while their ideas are all highly interpenetrating mainly on the theme of what is now identified as Von Neumann architecture, there does not seem to be any strong/known historical evidence (such as citations in papers, notes, letters, etc) they were fully or largely aware of each other. one definitely has to resist the assumption/bias that just because one event happened sooner than another, later researchers were aware of it.

(esp it is known that Zuse worked very independently.) and to be fair, Leibnitz' calculating machine should be mentioned in this list based on his quotations of imagining more general computations possible than those strictly built into his machine.

one could create a historical graph and try to determine if there are any connections between historical points/events and draw edges if there are. such a resource might be as least as illuminating and valuable as the highly regarded Complexity Zoo. Ulf Schünemann's ref seems to be the closest to this in existence but with the caveat its not directly intended for this purpose. again a history of facts is not the same as a map or graph of interconnections.

theoreticians sometimes say certain ideas are "in the air" and there are many famous cases of the nearly-same [sometimes complex] idea appearing in different, largely independent works at nearly the same time. the invention of computers clearly/strongly exhibits this "synchronicity" even stretching over a century if Babbage is fully/fairly considered.

it seems that the "dream" of a computer is old and perhaps very fundamental to the human race and probably inspired by difficult/tedious mechanical calculations combined with the Newtonian mechanistic shift of the Enlightenment, and the metaphor of the "clockwork universe". especially Babbages analytic engine seems like a highly sophisticated/evolved clockwork mechanism.

as other striking examples of theoretical synchronicity from computer science and independent discovery of complex/fundamental ideas, to underline the phenomenon, its now known from a NSA-declassified letter by John Nash (info by Noam Nisan) that he also came up with some of the ideas underlying computational complexity and codebreaking eg one-way/trap-door systems. this letter was written around the same time as the now-famous lost Godel letter also musing on foundations of complexity theory.

another example is Cook-Levin complexity theory of NP completeness. the Levin results were published in Russian and not "discovered" for years later.

essentially, historical awareness seems to increase over time and we now have a very good/detailed picture of the history of computers as far as a timeline, partly because the subject has such massive historical and economic significance during the Moore transistor miniaturization revolution starting in the 1960s (note that much of the secret military work was still classified in the 1950s!).

but that awareness was not as great in prior eras. so to attribute the same detailed historical awareness to earlier workers is misguided, unless possibly one wants to take it as as one of the foremost cases of a phenomenon of Mathematical Platonism.

the closest book to exploring these "threads" Ive found is from Pebbles to Computers, the Thread by Hans Blohm (1987)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.