4 ms·

I often feel that Alan gets adequate credit but Alonzo too little. There must be something I don't get.

microcolonel 10y ago
Idunno, they made two equivalent models of computation. I think that Alan's discrete computational model is more useful for programmable computers, Alonzo's is more useful for FPGAs and circuitry. Alan just turned out to have the model which was most amenable to direct mapping of a stored-program computer. If you want to run Alonzo's model on a stored program computer, you need a compiler. And to do it efficiently, you need a better compiler than has ever been devised.
sn41 10y ago
Turing discovered the Universal machine. Church tried convincing Godel that lambda-calculus is universal, but Godel wasn't ready to accept it. When Turing defined his machine model as a model for mechanical computation, Godel was convinced. In an appendix to that paper, Turing also showed that his model was computationally equivalent to the lambda calculus. This involved writing a "universal" lambda expression, i.e. a combinator. (Y combinator is the most famous one, I think that was discovered by Haskell B. Curry.) It was when Turing proved this equivalence that Godel accepted lambda calculus as a model of intuitive computation. In between, I have heard that Church's student, Kleene, did formulate fixed-point combinators when proving addition was computable in the lambda-calculus. Kleene was then convinced that this was a universal model of computation. I do not know why Church did not follow this up. So Turing does have some primacy over Church. *edit: Most of Turing's work on this was done as an undergraduate at Cambridge, /before/ he became Church's doctoral student. So the work was not done under Church's supervision. If you want to read further, you can read Soare's work on this tangled history: http://www.people.cs.uchicago.edu/~soare/History/compute.pdf http://www.people.cs.uchicago.edu/~soare/History/compute.pdf https://en.wikipedia.org/wiki/History_of_the_Church%E2%80%93Turing_thesis#Soare https://en.wikipedia.org/wiki/History_of_the_Church%E2%80%93...
- vilhelm_s 10y ago
  Surely Church must also have discovered the universal machine? Church's major result was the undecidability of the halting problem, and to set up the diagonalization proof you need a notion of interpreting a program. Looking at his paper[0], he has THEOREM XII. It is possible to associate simultaneously with every well-formed formula an enumeration of the formulas obtainable from it by conversion, in such a way that the function of two variables, whose value, when taken of a well-formed formula A and a positive integer n, is the n-th formula in the enumeration of the formulas obtainable from A by conversion, is recursive. THEOREM XVI. Every recursive function of positive integers is λ-definable. So approximately, Theorem XII gives an algorithm for evaluating a program A n steps, and theorem XVI says that this algorithm can be compiled in the a λ-calculus program. Church cites a paper by Kleene for this construction[1]. It's true that the Kleene doesn't prove this using a general recursion combinator like the Y combinator; instead he first shows how to λ-encode primitive recursive functions, and gives a combinator for the μ operator [2]. When you talk about Church "not following up" the notion of universality, I'm not sure what more you would want him to do. Of course he did not prove that λ-calculus was equivalent to Turing machines, because those had not been invented yet. But he and Kleene did prove that the λ-definable functions coincide with the μ-recursive functions, which was the best known model of universal computation. And he argues ([0] section 7) that this captures the intuitive notions of "a function for which there exists an algorithm" and "a function which can be proven to have a given value". [0] https://www.ics.uci.edu/~lopes/teaching/inf212W12/readings/church.pdf https://www.ics.uci.edu/~lopes/teaching/inf212W12/readings/c... [1] https://projecteuclid.org/download/pdf_1/euclid.dmj/1077489488 https://projecteuclid.org/download/pdf_1/euclid.dmj/10774894... [2] https://en.wikipedia.org/wiki/%CE%9C-recursive_function https://en.wikipedia.org/wiki/%CE%9C-recursive_function
danharaj 10y ago
Turing was Church's doctoral student, too. In fact, Church taught many of the greatest computer scientists of the last century. Perhaps he doesn't get as much credit as he should because his influence is so pervasive and impossible to separate from his peers' accomplishments. https://www.genealogy.math.ndsu.nodak.edu/id.php?id=8011 https://www.genealogy.math.ndsu.nodak.edu/id.php?id=8011
- jwdunne 10y ago
  Perhaps the manner of his last years and eventual death is the reason for that. The man has a statue on a bench in Manchester. It's in the gay village.
WorldMaker 10y ago
To add to other good answers here, I think there is something of the practical versus academic bias to be seen here as well. It was always hinted, but recently verified as documents have been declassified, that much of Mr. Turing's efforts after World War II were attempts to explore the consequences and abilities of devices he managed to actually build during the war, but was unable to continue working directly on after the war, so he did what he could skirting what tools he could use and how he could tell people based on what had been classified. I think that makes Mr. Church and his American team's work all the more interesting because they hadn't built practical machines and presumably never saw practical machines and worked almost exclusively in theory. But it's tougher for our culture sometimes to credit the theorists and academics than it is to credit practical genius. Especially with the declassified documents of the incredible practical computing work Mr. Turing accomplished during the war (and helping the war effort), it is easy to give him a lion's share of the credit and ignore some of the equally fascinating/important academic work of Mr. Turing's contemporaries. (Especially knowing in retrospect that the practical work fed the academic work and vice versa.)
fmap 10y ago
Turing gets more credit in popular culture, but academically Church is more influential. Just look at the list of Church's PhD students: http://www.genealogy.ams.org/id.php?id=8011 http://www.genealogy.ams.org/id.php?id=8011 I have no clue why Turing became such a pop-culture icon, though...
- mehaveaccount 10y ago
  >I have no clue why Turing became such a pop-culture icon, though... Turing had personal attributes that culture-makers in NY and Hollywood want to promote to people.
- krapp 10y ago
  Turing doesn't really have the status of a pop-culture icon. Outside of the phrase "Turing complete", and maybe historical accounts around breaking the Enigma, I doubt most people have even heard of him. He's definitely more known than Alonzo Church, though.
  - lou1306 10y ago
    What about "The Imitation Game"? I suppose that movie made Turing a quite well known figure, especially viz. Church.

Idunno, they made two equivalent models of computation. I think that Alan's discrete computational model is more useful for programmable computers, Alonzo's is more useful for FPGAs and circuitry. Alan just turned out to have the model which was most amenable to direct mapping of a stored-program computer. If you want to run Alonzo's model on a stored program computer, you need a compiler. And to do it efficiently, you need a better compiler than has ever been devised.

sn41 10y ago

Turing discovered the Universal machine. Church tried convincing Godel that lambda-calculus is universal, but Godel wasn't ready to accept it. When Turing defined his machine model as a model for mechanical computation, Godel was convinced. In an appendix to that paper, Turing also showed that his model was computationally equivalent to the lambda calculus. This involved writing a "universal" lambda expression, i.e. a combinator. (Y combinator is the most famous one, I think that was discovered by Haskell B. Curry.) It was when Turing proved this equivalence that Godel accepted lambda calculus as a model of intuitive computation. In between, I have heard that Church's student, Kleene, did formulate fixed-point combinators when proving addition was computable in the lambda-calculus. Kleene was then convinced that this was a universal model of computation. I do not know why Church did not follow this up. So Turing does have some primacy over Church. *edit: Most of Turing's work on this was done as an undergraduate at Cambridge, /before/ he became Church's doctoral student. So the work was not done under Church's supervision. If you want to read further, you can read Soare's work on this tangled history: http://www.people.cs.uchicago.edu/~soare/History/compute.pdf http://www.people.cs.uchicago.edu/~soare/History/compute.pdf https://en.wikipedia.org/wiki/History_of_the_Church%E2%80%93Turing_thesis#Soare https://en.wikipedia.org/wiki/History_of_the_Church%E2%80%93...

vilhelm_s 10y ago
Surely Church must also have discovered the universal machine? Church's major result was the undecidability of the halting problem, and to set up the diagonalization proof you need a notion of interpreting a program. Looking at his paper[0], he has THEOREM XII. It is possible to associate simultaneously with every well-formed formula an enumeration of the formulas obtainable from it by conversion, in such a way that the function of two variables, whose value, when taken of a well-formed formula A and a positive integer n, is the n-th formula in the enumeration of the formulas obtainable from A by conversion, is recursive. THEOREM XVI. Every recursive function of positive integers is λ-definable. So approximately, Theorem XII gives an algorithm for evaluating a program A n steps, and theorem XVI says that this algorithm can be compiled in the a λ-calculus program. Church cites a paper by Kleene for this construction[1]. It's true that the Kleene doesn't prove this using a general recursion combinator like the Y combinator; instead he first shows how to λ-encode primitive recursive functions, and gives a combinator for the μ operator [2]. When you talk about Church "not following up" the notion of universality, I'm not sure what more you would want him to do. Of course he did not prove that λ-calculus was equivalent to Turing machines, because those had not been invented yet. But he and Kleene did prove that the λ-definable functions coincide with the μ-recursive functions, which was the best known model of universal computation. And he argues ([0] section 7) that this captures the intuitive notions of "a function for which there exists an algorithm" and "a function which can be proven to have a given value". [0] https://www.ics.uci.edu/~lopes/teaching/inf212W12/readings/church.pdf https://www.ics.uci.edu/~lopes/teaching/inf212W12/readings/c... [1] https://projecteuclid.org/download/pdf_1/euclid.dmj/1077489488 https://projecteuclid.org/download/pdf_1/euclid.dmj/10774894... [2] https://en.wikipedia.org/wiki/%CE%9C-recursive_function https://en.wikipedia.org/wiki/%CE%9C-recursive_function

danharaj 10y ago

Turing was Church's doctoral student, too. In fact, Church taught many of the greatest computer scientists of the last century. Perhaps he doesn't get as much credit as he should because his influence is so pervasive and impossible to separate from his peers' accomplishments. https://www.genealogy.math.ndsu.nodak.edu/id.php?id=8011 https://www.genealogy.math.ndsu.nodak.edu/id.php?id=8011

jwdunne 10y ago
Perhaps the manner of his last years and eventual death is the reason for that. The man has a statue on a bench in Manchester. It's in the gay village.

WorldMaker 10y ago

To add to other good answers here, I think there is something of the practical versus academic bias to be seen here as well. It was always hinted, but recently verified as documents have been declassified, that much of Mr. Turing's efforts after World War II were attempts to explore the consequences and abilities of devices he managed to actually build during the war, but was unable to continue working directly on after the war, so he did what he could skirting what tools he could use and how he could tell people based on what had been classified. I think that makes Mr. Church and his American team's work all the more interesting because they hadn't built practical machines and presumably never saw practical machines and worked almost exclusively in theory. But it's tougher for our culture sometimes to credit the theorists and academics than it is to credit practical genius. Especially with the declassified documents of the incredible practical computing work Mr. Turing accomplished during the war (and helping the war effort), it is easy to give him a lion's share of the credit and ignore some of the equally fascinating/important academic work of Mr. Turing's contemporaries. (Especially knowing in retrospect that the practical work fed the academic work and vice versa.)

fmap 10y ago

Turing gets more credit in popular culture, but academically Church is more influential. Just look at the list of Church's PhD students: http://www.genealogy.ams.org/id.php?id=8011 http://www.genealogy.ams.org/id.php?id=8011 I have no clue why Turing became such a pop-culture icon, though...

mehaveaccount 10y ago
>I have no clue why Turing became such a pop-culture icon, though... Turing had personal attributes that culture-makers in NY and Hollywood want to promote to people.
krapp 10y ago
Turing doesn't really have the status of a pop-culture icon. Outside of the phrase "Turing complete", and maybe historical accounts around breaking the Enigma, I doubt most people have even heard of him. He's definitely more known than Alonzo Church, though.
- lou1306 10y ago
  What about "The Imitation Game"? I suppose that movie made Turing a quite well known figure, especially viz. Church.