2012 British Mathematical Colloquium (BMC), University of ...

2012 British Mathematical Colloquium (BMC), University of Kent Workshop on Turings Legacy in Mathematics & Computer Science 17th April 2012 Introduction: The Limits to Computation Greg Michaelson School of Mathematical & Computer Sciences Heriot-Watt University BMC 2012 1 Russells Paradox 1901 Bertrand Russell

naive set theory is contradictory self-reference set of all sets which are not members of themselves BMC 2012 2 Principia Mathematica

1910-13 Alfred North Whitehead Bertrand Russell show that all mathematics can be derived from symbolic logic BMC 2012 3 Hilberts Programme 1920 David Hilbert

show that Russell & Whitehead formalisation is: consistent: no contradictions complete: no unprovable theorems decidable: algorithm to determine if a mathematical assertion is a theorem entscheidungsproblem BMC 2012 4 Gdels Incompleteness Theorems 1931 Kurt Gdel Russell & Whitehead

mathematics is incomplete self-referential contradiction this theorem is not a theorem BMC 2012 5 Turing Machines

1936 Alan Turing model of computability machine inspects tape of cells with symbols tape can move left or right machine controlled by state to state transitions old state * old symbol -> new state * new symbol * direction BMC 2012 6 Turing Machines TM machine embodies

a specific computation Universal Turing Machine interpreter for any TM + tape description BMC 2012 7 Turing Machines entscheidungsproblem does arbitrary TM halt over arbitrary tape? undecidable diagonalisation + selfreferential contradiction

this TM only halts if it doesnt halt BMC 2012 8 -Calculus 1936 Alonzo Church model of effective calculability

expression: id.exp function (exp exp) application id identifier reduction ( id.exp1 exp2) ==> exp1[id/exp2] BMC 2012 9 -Calculus expression is in normal form if no more

reductions apply entscheidungsproblem does arbitrary expression have a normal form? undecidable diagonalisation + contradiction BMC 2012 10 Church-Turing Thesis Turing(1936): In a recent paper Alonzo Church has introduced an idea of "effective calculability", which is equivalent

to my "computability", but is very differently defined. Church also reaches similar conclusions about the Entscheidungsproblem. The proof of equivalence between "computability and "effective calculability" is outlined in an appendix to the present paper. BMC 2012 11 Church-Turing Thesis To show that every -definable sequence is computable, we have to show how to construct a machine to compute .... To prove that every computable sequence is definable, we must show how to find a formula M such that, for all integers n,

{M} (Nn) conv N1+(n)(n)n)... i.e. M is a expression that behaves like machine on input Nn BMC 2012 12 Church-Turing Thesis all models of computability are equivalent: can translate any instance of one model into an instance of any other model can construct an interpreter for any model in any other model formal results for any model have equivalences in any other model

applies to idealised: von Neumann machines programming languages BMC 2012 13 Logical Challenges there are formal models of computability in which undecidable properties of TMs are decidable Wegner (1997) TM tape cant change under external influence during computation interaction machines Wegner & Eberbach (2004)

calculus $ calculus = calculus + von Neumann/Morgernstern utility functions BMC 2012 14 Physical Challenges there are physical systems for which undecidable properties of TMs are decidable accelerating TMs - Copeland (2001) Malament-Hogarth space-time computation(1992) - Etesi & Nemeti (2002) analogue/real number computing Analog X machines Stannett (1990) da Costa & Doria (2009)

BMC 2012 15 The Challengers Challenged lots of people, including Cockshott, Mackenzie & Michaelson (2012) what are the concrete: TM undecidable problems which are now semidecidable? TM semi-decidable problems which are now decidable? TM undecidable problems which are now decidable? canonical/defining instances of the above? can it actually be built? BMC 2012

16 References A. D. Irvine, "Russell's Paradox", The Stanford Encyclopedia of Philosophy (n)Summer 2009 Edition), Edward N. Zalta (ed.), URL = . A. N. Whitehead and B. Russell. Principia Mathematica, 3 vols, Cambridge University Press, 1910, 1912, and 1913. Second edition, 1925 (Vol. 1), 1927 (Vols 2, 3). R. Zach, "Hilbert's Program", The Stanford Encyclopedia of Philosophy (n)Spring 2009 Edition), Edward N. Zalta (ed.), URL = . K. Godel, 1992. On Formally Undecidable Propositions Of Principia Mathematica And Related Systems, tr. B. Meltzer, with a comprehensive introduction by Richard Braithwaite. Dover reprint of the 1962 Basic Books edition. A. M. Turing, "On computable numbers, with an application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, 42 (1937), pp 230265.

A. Church, "An unsolvable problem of elementary number theory", American Journal of Mathematics, 58 (1936), pp 345363 P. Wegner, Why interaction is more powerful than algorithms, Communications of the ACM, Vol. 40, Issue 5, pp80-91, May 1997 P. Wegner and E. Eberbach, New Models of Computation, Computer Journal, vol.47, no.1, 2004, 4-9. BMC 2012 17 References P. B. J. Copeland, Accelerating Turing MachinesMinds and Machines 12: 281301, 2002 M. Hogarth, 1992, Does General Relativity Allow an Observer to View an Eternity in a Finite Time?, Foundations of Physics Letters, 5, 173181 G. Etesi, and I. Nemeti, 2002 Non-Turing computations via Malament-Hogarth space-times, Int.J.Theor.Phys. 41 (2002) 341370

M. Stannett (1990) 'X-machines and the Halting Problem: Building a super-Turing machine'. Formal Aspects of Computing 2, pp. 331-41. N.C.A. da Costa and F.A. Doria, How to build a hypercomputer, Applied Mathematics and Computation, Volume 215, Issue 4, 15 October 2009, Pages 1361-1367 P. Cockshott, L. M. Mackenzie and G. Michaelson, Computation and its Limits, OUP, 2012 BMC 2012 18 Visions of Johanna Inside the museum, Infinity goes up on trial. Voices echo this is what salvation must look like after a while... Bob Dylan(n)1966)

BMC 2012 19

Recently Viewed Presentations

  • Parody, Homage, Archetype & Allusion

    Parody, Homage, Archetype & Allusion

    Parody is the practice of taking something well known or renowned and making a mockery of it. i.e. "Scary Movie" franchise. Generally, parodies are meant to create a comic redo of a specific genre or artist.
  • Math Jeopardy - scott.k12.ky.us

    Math Jeopardy - scott.k12.ky.us

    What are the ways that the Renaissance spread north from Italy to the rest of Europe ? Greek and Roman. What are the cultures that the teaching and ideas of the Renaissance came from? They believed in the potential of...
  • FEDERAL REGULATION - miningquiz.com

    FEDERAL REGULATION - miningquiz.com

    FEDERAL REGULATION Hazardous Waste Operations and Emergency Response HAZWOPER FEDERAL REGULATION EPA DOT OSHA 40 CFR 49 CFR 29 CFR RCRA, EPCRA HM-181 General CAA, CWA, SDWA HM-126F Industry FIFRA Standards HAZWOPER WHO MUST COMPLY: Clean-up operations required by a...
  • Jewish Vocabulary

    Jewish Vocabulary

    Synagogue A Jewish house of worship and assembly, the synagogue is used for worship, prayer, and meetings. Rabbi The title means "my teacher" or "my master" and is given to a religious leader. Ghetto Beginning in 1939, the Nazis forced...
  • Billing Lecture

    Billing Lecture

    Note that there are times associated with many of these E&M codes. You may upcode to a higher E&M level based on time spent by the MD, face-to-face with the patient. For example, a patient presents with vaginitis and a...
  • Illustrating HIV/AIDS in the United States

    Illustrating HIV/AIDS in the United States

    Illustrating HIV/AIDS in the United States Washington, DC Rates of Hispanic/Latino & White Persons Living with an HIV or AIDS Diagnosis, by ZIP Code, Washington, DC, 2010
  • Introduction to Oral Histology Dr Firas Alsoleihat, BDS,

    Introduction to Oral Histology Dr Firas Alsoleihat, BDS,

    Cementum The prime function of cemntum is to give attachment of the tooth to collagen fibres of the periodontal ligament. Cementum can be repaired and regenerated Periodontal Ligament Dense fibrous connective tissue that attaches the tooth to the alveolar bone....
  • CHAPTER 2 AN OVERVIEW OF ICD-10-CM Copyright  2019

    CHAPTER 2 AN OVERVIEW OF ICD-10-CM Copyright 2019

    All codes in a chapter begin with a letter. Official Instructional Notations. Includes. Define or give examples of category content. Figure 2.13. Includes notation. (From Elsevier: Buck's 2019 ICD-10-CM Hospital Edition, St. Louis, 2019, Elsevier.)