ACM Comm 2012 03 Turing's Titanic Machine (Notes)

"Turing's Titanic Machine?" CACM March 2012

Turing's Titanic Machine? by S. Barry Cooper, p.74-83

Turing's Titanic Machine?

"Embodied and disembodied computer at the Turing Centenary."
What computation, in what kinds, and in what way, are needed for a Darwin Machine?
One machine's halting set is another machine's computable set. The trick finding the right machine.

People

1. Alan Mathison Turing[1]
2. John Myhill[2]
3. Samson Abramsky
4. Martin Davis, distinguished elder-statesman of computability". Standard Model champion.
5. Kurt Gödel[3]
6. David Deutsch[4] - ...placing of the standard model of quantum computing firmly within the scope of the Turing model

Ideas

1. The RMS Titanic sank, and Alan Turing was born, in 1912. There are some analogies between them.
2. Turing Model, adequacy and fitness. Still open to debate.
3. Mathematical, based on the Turing Model
   1. Classical computability, well developed and understood. What can be computed.
   2. Classical incomputability, well developed and understood. What can't be computed.
4. New computing paradigms
   1. Artificial Intelligence
   2. Alife
   3. Nature
   4. Internet
5. What does it mean to compute something?
6. Halting Set[5]
7. Naturally Arising Incomputable - objects. Associated by John Myhill with the Halting Set.
8. Hilbert's Tenth Problem. Negative Solution, 1970.
9. Diophantine Equation[6]
10. "How" incomputable is an object?
    1. Does incomputability come in levels?
11. "...the problem of recognizing whether a given Turing machine has incomputable halting set or not is very far from being computable." Which means that we can't determine if an object is computable or not.
12. "Computation Disembodied" Subtitle for the next section and just a fun phrase.
13. Abstracting computation away from the machine. This was Turning's great feat, but not perfectly complete.
14. Church-Turing Thesis
15. Challenges to the Standard Model for Computation. The first and last are conventional efforts. The last the least success.
    1. Reductionists: "Confident of the unsinkability of the standard model, one can apply it ever more widely to what we observe in nature, and let it mold our expectations of what computing machines can achieve." Or, "My fantasy world describes the Universe, perfectly." Hogwash. The Standard Model is only the latest step to a better idea.
    2. Impressionists: "Distrustful of the science, one can open one’s mind to observation and surprises, speculate about inconsistencies with the standard model, and seek to philosophically clarify one’s perceptions." No, not distrustful of the science. Distrustful of the ideology the fossils preach. The answer IS in the science. In testing new ideas against reality.
    3. Remodelers: "Renewing Turing, one can use one’s observations and ingenuity to design new models of computation, directly inspired by real-world processes or arising from abstract theoretical considerations, or both." Revising and updating the old idea, until it can be updated no more. See Newton and Einstein.
    4. Incompatibility (Recursion) Theorists: "Consistent with a genuine paradigm-change being in process, one can aim to develop the analysis of computability and incomputability, to the point where the theoretical context successfully hosts a convincing new view of what one observes, that is, a classical computability theoretic response." Or, now I can tell one from the other in the real world.
16. The question, again, is what is computable? Hard to impossible to ask a more general question than that.
17. The computer is a device for executing algorithms.
18. Theory of Mind
19. Quantum Physics
20. Emergence of form in nature
21. Wave Function Collapse[7]
22. Quantum randomness, under reasonable assumptions, entails incomputability.
23. Emergentism[8]
24. Computable is what we know, or can know, about the world.
25. Incomputable is what we don't know, or can't ever know, or can't perceive about the world.
26. Differences between computation in the Digital and Analog worlds boils down to Determinism. The Digital World is. The Analog World is not. The Turing Machine is Digital. A tomato plant is not. So is a grilled cheese sandwich.
27. Reductionism, reduce the Universe until it all fits nicely, and neatly, in your fantasy world. Then claiming your fantasy world describes the whole Universe.
28. Oracle Turing Machine
29. Halting Set. Any computation is just one quantifier away from a halting set.
    1. Changing the machine changes the quantifier needed to form a halting set. So, theoretically, there is some machine to solve each halting set.

References

1. Deutsch, D. Quantum theory, the Church-Turing principle, and the universal quantum computer. In Proceedings of the Royal Society A400 (1985) 97−117.
2. Turing's 1952 Morphogenesis article. Teuscher, C. Turing’s Connectionism. An Investigation of Neural Network Architectures, Springer-Verlag, London, 2002.
3. ACM Ubiquity Symposium on "What is Computation"? October 2010.
4. Springer’s Handbook of Natural Computing 2011

Internal Links

Parent Article: Reading Notes