turing

Information about turing

Published on January 5, 2008

Author: Ariane

Source: authorstream.com

Content

What Computers Can't Compute:  What Computers Can't Compute Dr Nick Benton Queens' College & Microsoft Research [email protected] Slide2:  David Hilbert (1862-1943) Hilbert's programme: To establish the foundations of mathematics, in particular by clarifying and justifying use of the infinite: ``The definitive clarification of the nature of the infinite has become necessary, not merely for the special interests of the individual sciences but for the honour of human understanding itself.'' Aimed to reconstitute infinitistic mathematics in terms of a formal system which could be proved (finitistically) consistent, complete and decidable. Slide3:  Consistent: It should be impossible to derive a contradiction (such as 1=2). Complete: All true statements should be provable. Decidable: There should be a (definite, finitary, terminating) procedure for deciding whether or not an arbitrary statement is provable. (The Entscheidungsproblem) There is the problem. Seek its solution. You can find it by pure reason, for in mathematics there is no ignorabimus. Wir müssen wissen, wir werden wissen Slide4:  Bertrand Russell (1872-1970) Alfred Whitehead (1861-1947) Russell's paradox showed inconsistency of naive foundations such as Frege's: {X | XX} "The set of sets which are not members of themselves" Theory of Types and Principia Mathematica (1910,1912,1913) Slide5:  Kurt Gödel (1906-1978) Uber formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (1931) Any sufficiently strong, consistent formal system must be Incomplete Unable to prove its own consistency Slide6:  Alan Turing (1912-1954) On computable numbers with an application to the Entscheidungsproblem (1936) Church, Kleene, Post Slide8:  x Turing's Model of a Mathematician Finite state brain Finite alphabet of symbols Infinite supply of notebooks Slide9:  The Turing Machine A A C G C T T G C 1 Replaces GC with TA Slide10:  The Turing Machine A A C G C T T G C 1 Replaces GC with TA Slide11:  The Turing Machine A A C G C T T G C 1 Replaces GC with TA Slide12:  The Turing Machine A A C G C T T G C 1 Replaces GC with TA Slide13:  The Turing Machine A A C G C T T G C 2 Replaces GC with TA Slide14:  The Turing Machine A A C G C T T G C 2 Replaces GC with TA Slide15:  The Turing Machine A A C G C T T G C 3 Replaces GC with TA Slide16:  The Turing Machine A A C G C T T G C 3 Replaces GC with TA Slide17:  The Turing Machine A A C T C T T G C 4 Replaces GC with TA Slide18:  The Turing Machine A A C T C T T G C 4 Replaces GC with TA Slide19:  The Turing Machine A A A T C T T G C 1 Replaces GC with TA Slide20:  Another example: Binary Addition Slide21:  So particular Turing Machine is specified by Its alphabet Its transition table Each TM then defines a partial function from Tapes to Tapes. Given a machine M and a tape T, there are two possible things that can happen when we run machine M on input tape T: EITHER the machine simply runs forever without stopping, OR The machine eventually stops with an output tape T’ M T T’ Slide22:  Since we can represent natural numbers on the tape (using decimal, binary, roman numerals, whatever), we can write TMs to compute (partial) functions from ℕ to ℕ. The word function has at least two senses. Mathematical. A function is a set of pairs, giving all the (argument, result) combinations together. So the ‘square’ function, for example, looks like {(0,0), (1,1), (2,4), (3,9),…}. Computational. A function is a procedure, method, algorithm, operation, formula for computing the result from the argument. There’s some kind of causal relation between input and output. Investigating the relationship between these two views (the denotational and the operational) is central to theoretical computer science. Slide23:  Not all mathematical functions are computable by a Turing machine. (we’ll see an example soon) But all other notions of computation which people have invented turn out to give exactly the same set of computable functions. That this is the essential meaning of ‘computable’ is known as the Church-Turing Hypothesis, though this is clearly not a rigorous notion. Slide24:  Turing’s first result. Since a particular TM is specified by a finite amount of information, we can encode it as a finite string of symbols in some alphabet (equivalently as a natural number). We’ll write M for the code of machine M. (the details of the coding scheme are unimportant…) But we can write M onto the tape, so one TM can take as input the code of another one (or even itself). There is a Universal Turing Machine, U Slide25:  If and only if For any machine M and tapes T and T’ Slide26:  Turing’s second result The ‘Halting Problem’ is undecidable There is NO machine H which computes whether or not any other machine will halt on a given input: M T H M,T YES NO iff iff Slide27:  Proof of the undecidability of the halting problem We’ll assume that there is such a machine, H, and derive a contradiction. First, we define a copy machine (this is easy): Slide28:  COPY H Now modify H so that it goes into a loop instead of printing ‘yes’ …and call the resulting machine H ’ …plug the copy machine into the front What happens when we feed H’ its own code? Slide29:  COPY H H’ H’, H’ Machine H’ terminates on input H’ if and only if The modified H terminates on input H’ ,H’ , which happens if and only if The original H prints ‘no’ on input H’ ,H’ , which happens if and only if Machine H’ does not terminate on input H’ Slide30:  COPY H H’ H’, H’ Hence our original assumption, that H exists, must be false. Slide31:  Corollaries of Turing’s result It’s uncomputable whether an arbitrary machine halts when given an empty initial tape. In fact, all ‘interesting’ properties of computer programs are uncomputable. For example It’s impossible to write a perfect virus checker. The `full employment theorem’ for compiler writers. The Entscheidungsproblem is unsolvable: Roughly, because ‘Turing machine M halts on tape T’ is expressible as a logical formula which, if true, will be provable (because it only requires a finite demonstration). Hence if there were a decision procedure for the provability of arbitrary propositions, there’d be one for the halting problem. This is the ‘full employment theorem’ for mathematicians. Slide32:  Further developments of Turing’s work Complexity theory. From ‘what can we compute?’ to `how fast can we compute?’. Turing machines are still a basic concept in this huge area of computer science. Higher-type recursion theory and synthetic domain theory. Once we add types, the notion of computable becomes rather more subtle. Developments in this area have led to ‘mathematical universes’ in which computability is built-in from the start, and these have been proposed as good places in which to model and reason about computer programs. Slide33:  Philosophy and Artificial Intelligence Implications of Gödel’s and Turing’s work for the philosophy of mind and the possibility of ‘thinking machines’ are still hotly debated. See for example Roger Penrose’s The Emperor’s New Mind and Shadows of the Mind. Really crazy stuff… DNA and restriction enzyme implementation of TMs It has been suggested that one could compute the uncomputable by sending computers through wormholes in space so that they run for an infinite amount of time in a finite amount of the observer’s time . Other developments Slide34:  One can encode the propositions and rules of inference of a formal system as natural numbers, so that statements about the system become statements about arithmetic. Thus, if the system is sufficiently powerful to prove things about arithmetic, it can talk (indirectly) about itself. The key idea is then to construct a proposition P which, under this interpretation, asserts P is not provable Then P must be true (for if P were false, P would be provable and hence, by consistency, true - a contradiction!) So P is true and unprovable, i.e. the system is incomplete. Proof of Gödel's Incompleteness Theorem. Slide35:  Further Reading Popular Alice’s Adventures in Wonderland and Through the Looking Glass (And What Alice Found There). Lewis Carroll. Godel, Escher, Bach: an Eternal Golden Braid. Douglas R. Hofstadter (Basic Books,1979) Alan Turing: the Enigma. Andrew Hodges (1983) http://www.turing.org.uk/ To Mock a Mockingbird and What is the Name of this Book?. Raymond Smullyan Academic The Undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions. Martin Davis (Raven Press,1965) From Frege to Gödel: A Sourcebook in Mathematical Logic. J. van Heijenoort (Harvard,1967)

Related presentations


Other presentations created by Ariane

Safe Winter Driving
04. 01. 2008
0 views

Safe Winter Driving

Diamond
14. 11. 2007
0 views

Diamond

Heart Attack 2007
04. 01. 2008
0 views

Heart Attack 2007

Food groups
04. 03. 2008
0 views

Food groups

Radio wave propagation S
07. 11. 2007
0 views

Radio wave propagation S

WHAT IS A SENTENCE
19. 11. 2007
0 views

WHAT IS A SENTENCE

IPv6 addressing
28. 09. 2007
0 views

IPv6 addressing

FL Geology
03. 10. 2007
0 views

FL Geology

Taylor
05. 12. 2007
0 views

Taylor

util summit one call
12. 12. 2007
0 views

util summit one call

Monroe
02. 11. 2007
0 views

Monroe

Our Story Engagement Party 2007
05. 11. 2007
0 views

Our Story Engagement Party 2007

China Movement Forward
11. 10. 2007
0 views

China Movement Forward

Presentation FATEALLCHEM English
04. 10. 2007
0 views

Presentation FATEALLCHEM English

azienda e impresa
20. 11. 2007
0 views

azienda e impresa

Opioids
22. 11. 2007
0 views

Opioids

Apsa
23. 11. 2007
0 views

Apsa

Equalizer Design
26. 11. 2007
0 views

Equalizer Design

presse16042002
01. 12. 2007
0 views

presse16042002

mnu page 19
17. 12. 2007
0 views

mnu page 19

cold war beginning
18. 12. 2007
0 views

cold war beginning

SCADA security
25. 12. 2007
0 views

SCADA security

LME LFG
30. 12. 2007
0 views

LME LFG

food allergy
03. 01. 2008
0 views

food allergy

lecture19
04. 01. 2008
0 views

lecture19

Vineyard Maintenance
07. 01. 2008
0 views

Vineyard Maintenance

Commodity Grapes
07. 01. 2008
0 views

Commodity Grapes

07 MITRE radar
06. 11. 2007
0 views

07 MITRE radar

mammoth wall new technologies
16. 11. 2007
0 views

mammoth wall new technologies

summary of warfare to date
04. 01. 2008
0 views

summary of warfare to date

yale presentation
24. 02. 2008
0 views

yale presentation

Korean War Lisa
28. 02. 2008
0 views

Korean War Lisa

Children Adolescents
11. 03. 2008
0 views

Children Adolescents

Futures Podcast Lectures Series
12. 03. 2008
0 views

Futures Podcast Lectures Series

ITS 13 07e
14. 03. 2008
0 views

ITS 13 07e

CONVERA
18. 03. 2008
0 views

CONVERA

Offshore Info Session 2007
27. 03. 2008
0 views

Offshore Info Session 2007

Reduce our impact
02. 10. 2007
0 views

Reduce our impact

nlpspo linkkdd04
13. 04. 2008
0 views

nlpspo linkkdd04

Morris9 28 05
19. 11. 2007
0 views

Morris9 28 05

tankleak jb10 06
08. 11. 2007
0 views

tankleak jb10 06

061101Panofsky
19. 12. 2007
0 views

061101Panofsky

UC Flex Town Hall 5 Final
27. 11. 2007
0 views

UC Flex Town Hall 5 Final

CEP retreat presentation 7 24 07
29. 10. 2007
0 views

CEP retreat presentation 7 24 07

12 Mufson lightBox may05
29. 11. 2007
0 views

12 Mufson lightBox may05

ANTHROPOLOGICAL APPROACH
13. 11. 2007
0 views

ANTHROPOLOGICAL APPROACH

vatant
04. 12. 2007
0 views

vatant

ebipres
07. 01. 2008
0 views

ebipres

lecture9 queryexpansion
06. 12. 2007
0 views

lecture9 queryexpansion

LeeEysturlid NCSS Presentation
21. 12. 2007
0 views

LeeEysturlid NCSS Presentation