The Limits Of Computing

Information about The Limits Of Computing

Published on January 7, 2008

Author: FunnyGuy

Source: authorstream.com

Content

Gödel to Turing to Chaitin to the Edge of Naturalism: Some Things Computers Will Never Do” :  Gödel to Turing to Chaitin to the Edge of Naturalism: Some Things Computers Will Never Do” Robert J. Marks II Distinguished Professor of Electrical and Computer Engineering Points...:  Points... Can anything be proved to be outside of reach of mathematics? In biology, are there phenomena that will never be explained by naturalism? There are such phenomena in computing. We can prove existence of the unprovable and the unknowable. What Might Be Unprovable?:  What Might Be Unprovable? Goldbach’s Conjecture All even numbers greater than 4 can be expressed as the sum of two prime numbers. For example: 24 = 17 + 7 100 = 97 + 3 150 = 139 + 11 Chaitin’s Incredible Number:  Chaitin’s Incredible Number  = Chaitin’s number = A number between zero and one. If we knew Chaitin’s number, to finite precision, we could prove (or disprove) most unproven problems in mathematics, including Goldbach’s conjecture. MATLAB has a value of . C++ has another value for . So does Java. Gregory Chaitin Meta Thought:  Meta Thought Fun Meta Thoughts Gödel’s Proof Who was Gödel? Turing Stop Test Who Was Turing? : Chaiten’s number. A single number between one and zero we know exists that could be used to prove all theorems – but a number we will never know. Meta Analysis:  Meta Analysis Meta = Self reference It can be true: “This sentence has five words.” It can be false “This sentence has twenty words.” Meta Food: You is what you eat. Meta Analysis can be Funny:  Meta Analysis can be Funny “And if I don’t cure your amnesia, I will cheerfully refund all your doctor’s fees.” Meta Statements Can Be Incomplete:  Meta Statements Can Be Incomplete Meta Statements Can Have No Resolution:  Meta Statements Can Have No Resolution If you write a book about how to fail at selling books, and your book doesn’t sell, are you a failure? Meta Statements Can Be Bipolar:  Meta Statements Can Be Bipolar “The Cretians are alway liars.” Titus 1:12b A Cretian Meta Statements Can Be Curious:  Meta Statements Can Be Curious This statement is true! This statement is true! Meta Thought Can Reveal Self Refuting Philosophies:  Meta Thought Can Reveal Self Refuting Philosophies I disagree. You’re wrong! And you’re right? Absolutely! Meta Thought Can Reveal Numerous Self Refuting Philosophies:  Meta Thought Can Reveal Numerous Self Refuting Philosophies Meta Statements Can Require Clarifying Context:  Mar 10:27b: ... with God all things are possible. Meta Statements Can Require Clarifying Context THEOREM: All integers are interesting:  THEOREM: All integers are interesting PROOF Assume there is a smallest uninteresting integer. Hmmmm. That’s interesting! Proof by contradiction. Berry’s Paradox:  Berry’s Paradox Let X be the smallest natural number that requires more than twenty words to define. Paradox: “Let X be the smallest natural number that requires more than twenty words to define” defines X using 15 words. Meta abilities separate Man from animals. C.S. Lewis, Mere Christianity:  Meta abilities separate Man from animals. C.S. Lewis, Mere Christianity The Moral Law is evident by the meta ability of Man to externally examine instincts, feelings and inclinations and make meta moral decisions of right and wrong. Meta Analysis on Euclid's Postulates (?????):  Meta Analysis on Euclid's Postulates (?????) 1. A straight line segment can be drawn joining any two points. 2. Any straight line segment can be extended indefinitely in a straight line. 3. Given any straight line segment, a circle can be drawn having the segment as radius and one endpoint as center. 4. All right angles are congruent. 5. If two lines are drawn which intersect a third in such a way that the sum of the inner angles on one side is less than two right angles, then the two lines inevitably must intersect each other on that side if extended far enough. Meta Thought Can Topple Mathematical Disciplines:  Meta Thought Can Topple Mathematical Disciplines Gödel’s Proof (1931) showed , from any set of assumptions, there are truths that cannot be proven. Kurt Gödel (1906 - 1978) Slide20:  Time Magazine’s Top 100 Persons of the Twentieth Century http://en.wikipedia.org/wiki/Time_100:_The_Most_Important_People_of_the_Century Scientists & Thinkers • Leo Baekeland (1863-1944), Belgian-American chemist who invented Bakelite • Tim Berners-Lee (b. 1955), inventor of the World Wide Web • Rachel Carson (1907-1964), American marine biologist • Francis Crick (1916-2004) and James D. Watson (b. 1928), Scientists who discovered the DNA structure • Albert Einstein (1879-1955), German-born theoretical physicist, author of the theory of relativity • Philo Farnsworth (1906-1971), American inventor who invented the electronic television • Enrico Fermi (1901-1954), Italian physicist, most noted for his work on the development of the first nuclear reactor • Alexander Fleming (1881-1955), Scottish biologist and pharmacologist, he discovered the penicillin • Sigmund Freud (1856-1939), Austrian neurologist and psychiatrist, founder of psychoanalytic school of psychology • Robert Goddard (1882-1945), American professor and scientist, pioneer of controlled, liquid-fueled rocketry • Kurt Gödel • Edwin Hubble (1889-1953), American astronomer • John Maynard Keynes (1883-1946), British economist • Louis (1903-1972), Mary (1913-1996) and Richard Leakey (b. 1944), British and Kenyan archaeologists • Jean Piaget (1896-1980), Swiss philosopher, natural scientist and developmental psychologist • Jonas Salk (1914-1995), American physician and researcher developed of the first successful polio vaccine • William Shockley (1910-1989), British-born American physicist who invented the transistor • Alan Turing • Ludwig Wittgenstein (1889-1951), Austrian philosopher • Wilbur (1867-1912) and Orville Wright (1871-1948), builders of the world's first successful airplane (1912-1954), English mathematician, logician & cryptographer (1906-1978), Austrian-American mathematician & philosopher Slide21:  Gödel With Einstein at the Princeton Institute Slide22:  Gödel’s View on Evolutionary Informatics [EvoInfo.org]... “The formation in geological time of the human body by the laws of physics (or any other laws of similar nature), starting from a random distribution of elementary particles and the field is as unlikely as the separation of the atmosphere into its components. The complexity of the living things has to be present within the material [from which they are derived] or in the laws [governing their formation]” H. Wang. “On `computabilism’ and physicalism: Some Problems.” in Nature’s Imagination, J. Cornwall, Ed, pp.161-189, Oxford University Press (1995). Slide23:  http://en.wikipedia.org/wiki/G%C3%B6del's_ontological_proof Gödel offered an ontological proof that God exists Gödel’s Proof Oversimplified :  Gödel’s Proof Oversimplified For any theory... Theorem X: Theorem X cannot be proved. If we don’t prove Theorem X, the system is INCOMPLETE. If we prove Theorem X, the system is INCONSISTENT. What Might Be Unprovable?:  What Might Be Unprovable? Goldbach’s Conjecture All even numbers greater than 4 can be expressed as the sum of two prime numbers. For example: 32 = 29 + 3 144 = 131 +13 8 = 5 + 3 What Might Be Unprovable?:  What Might Be Unprovable? 2. Is there an odd perfect number? 6 = 3 + 2 +1 28= 14 + 7 + 4 + 2 + 1 Euclid showed N = 2n-1(2n-1) is perfect when 2n-1 is (Mersenne) prime. 44 known What Might Be Unprovable?:  What Might Be Unprovable? 3. Riemann Hypothesis (1859). The real part of any non-trivial zero of the Riemann zeta function is ½. A $1,000,000 prize has been offered by the Clay Mathematics Institute for the first correct proof of the Riemann hypothesis. Russell Crowe, as John Nash, discussed the Riemann Hypothesis in the motion picture “A Beautiful Mind.” In 2004, Xavier Gourdon and Patrick Demichel verified the Riemann hypothesis through the first ten trillion non-trivial zeros . http://en.wikipedia.org/wiki/Riemann_hypothesis Alan Turing: Father of Modern Computer Science:  Alan Turing: Father of Modern Computer Science Alan Turing (23 June 1912 – 7 June 1954) The Turing Test The Universal Turing Machine Decrypted Enigma The Turing Halting Problem Alan Turing’s Private Life:  Alan Turing’s Private Life Turing recognized his homosexuality as a teenager. A boy at school to whom Turing was attracted suddenly died of bovine tuberculosis. This loss shattered Turing's religious faith and led him into atheism and the conviction that all phenomena must have materialistic explanations. There was no soul in the machine nor any mind behind a brain. But how, then, did thought and consciousness arise? After being arrested for homosexual acts, Turing committed suicide in 1954. http://www.time.com/time/time100/scientist/profile/turing02.html Gödel’s Proof Application & The Turing Halting Problem :  Gödel’s Proof Application & The Turing Halting Problem Can we write a computer program to determine if another arbitrary computer program will ever stop? No! Using Gödel’s proof, Turing showed this was not possible. Turing If we could solve the halting problem ...:  If we could solve the halting problem ... We could find the answers to all open math theory. For example, Goldbach’s Conjecture How? Write a program to perform a sequential search, submit it to the “halting program”. If it halted, the conjecture is true. If not, it isn’t. Proof of the Halting Theorem:  Proof of the Halting Theorem Let p be a with input i . Both p and i can be expressed as a finite string of bits. Assume there is a halting program, h. The Program t (for trouble) uses h:  The Program t (for trouble) uses h The program t , below, can be represented by a string of bits. i What happens when we input i = t ?  A meta problem. t(i) The Meta Paradox:  The Meta Paradox t t(t) Quod erat demonstrandum... :  Quod erat demonstrandum... Therefore, by reductio ad absurdum, there exists no halting program. Chaitin’s Mystical, Magical Number, . Kraft Inequality. :  Chaitin’s Mystical, Magical Number, . Kraft Inequality. Length of Codewords 2, 3, 3, 3, 4, 5, 5 Note: 2-2+ 2-3+2-3+2-3+2-4+2-5+2-5= 1 Chaitin’s Mystical, Magical Number. :  Chaitin’s Mystical, Magical Number. Gregory Chaitin                     Chaitin’s Mystical, Magical Number, . Kraft Inequality. :  Chaitin’s Mystical, Magical Number, . Kraft Inequality. Let the pth codeword be of length ℓp Chaitin’s Mystical, Magical Number, . Programs That Halt & Don’t :  Chaitin’s Mystical, Magical Number, . Programs That Halt & Don’t 0 1 01 00 11 10 000 001 100 101 1000 1001 10000 10001 Some programs Halt and other’s Don’t Halt 100000 100001 Chaitin’s Mystical, Magical Number, . Programs That Halt & Don’t :  Chaitin’s Mystical, Magical Number, . Programs That Halt & Don’t 0 1 01 00 11 10 000 001 100 101 1000 1001 10000 10001 Express =Pr[Halt] in binary... 100000 100001 Chaitin’s Mystical, Magical Number, . Programs That Halt & Don’t :  Chaitin’s Mystical, Magical Number, . Programs That Halt & Don’t 1000 1001 10000 10001 100000 100001 Run all three bit programs until 3 is achieved. This identifies all the programs that will halt and all those that do not halt! Chaitin’s Mystical, Magical Number, . Programs That Halt & Don’t :  Chaitin’s Mystical, Magical Number, . Programs That Halt & Don’t 0 1 01 00 11 10 000 001 100 101 1000 1001 10000 10001 100000 100001 If 000 halts, Goldbach’s conjecture is false. If 000 doesn’t halt, Goldbach’s conjecture true. A search program for Goldbach’s conjecture Because we know 3, we can resolve Goldbach’s conjecture. Chaitin’s Mystical, Magical Number, .:  Chaitin’s Mystical, Magical Number, .  = Prob[ U(p) halts] IF we knew , we could know whether any program halted or not. We could prove or disprove all theorems.  exists, but is unknowable. Gregory Chaitin (1947- ) Chaitin’s number is not computable. A list of programs...:  Chaitin’s number is not computable. A list of programs... Programs 01 11 000 001 1001 10001 100000 100001 Chaitin’s number is not computable. A list of programs and outputs. Cantor diagonalization:  Chaitin’s number is not computable. A list of programs and outputs. Cantor diagonalization Programs 01 11 000 001 1001 10001 100000 100001 Computable Numbers 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 - - - - - 1 0 0 1 1 0 1 0 0 0 1 0 0 - - - 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 Astonishing Conclusion:  Astonishing Conclusion There are things that are true and are known to exist that will never be proven nor computed. Gödel vs. Turing: A Contrast in World Views and Motivation:  Theist. Did not believe in Darwinism. Worked on a mathematical proof of the existence of God. Gödel vs. Turing: A Contrast in World Views and Motivation Observations:  Observations Theism or Atheism is not directly determined by intellect. Worldview can mold motivation. It cannot, however, stand in the way of truth when pursued without bias. We are at an undisputed edge of naturalism.:  We are at an undisputed edge of naturalism. Does Science ever reach the edge of naturalism? If so, will we ever know we are at the edge?   Slide50:  Finis Finis Finis Finis Finis Finis

Related presentations


Other presentations created by FunnyGuy

history
02. 05. 2008
0 views

history

julac2001
28. 04. 2008
0 views

julac2001

sandiego
22. 04. 2008
0 views

sandiego

ch20
18. 04. 2008
0 views

ch20

unepmahomed
16. 04. 2008
0 views

unepmahomed

lecture14
13. 04. 2008
0 views

lecture14

oca
10. 04. 2008
0 views

oca

rexford slides
18. 06. 2007
0 views

rexford slides

Pepsi Presenation
18. 06. 2007
0 views

Pepsi Presenation

MATERIALHANDLING
27. 02. 2008
0 views

MATERIALHANDLING

ny subway
27. 09. 2007
0 views

ny subway

July20 KNN
05. 10. 2007
0 views

July20 KNN

VertebratePPP
10. 10. 2007
0 views

VertebratePPP

Wide World of Animals
10. 10. 2007
0 views

Wide World of Animals

cc
15. 10. 2007
0 views

cc

School for Scandal lecture
17. 10. 2007
0 views

School for Scandal lecture

Profesionesyoficios2
22. 10. 2007
0 views

Profesionesyoficios2

Lecture3 NLP grammars parsing
21. 10. 2007
0 views

Lecture3 NLP grammars parsing

lec6 sensanal 05
05. 10. 2007
0 views

lec6 sensanal 05

PPMcNeely
23. 10. 2007
0 views

PPMcNeely

California Demographics 101
29. 10. 2007
0 views

California Demographics 101

Varying sent struct2
30. 10. 2007
0 views

Varying sent struct2

bio435 660 chap3 pt1
16. 11. 2007
0 views

bio435 660 chap3 pt1

dogscatsrabbits
19. 11. 2007
0 views

dogscatsrabbits

Workshop Marketing
20. 11. 2007
0 views

Workshop Marketing

Sablony
15. 11. 2007
0 views

Sablony

poultry prod
26. 11. 2007
0 views

poultry prod

lublin072806
23. 10. 2007
0 views

lublin072806

hcbscrisis
30. 10. 2007
0 views

hcbscrisis

lecture06
30. 12. 2007
0 views

lecture06

mites
01. 01. 2008
0 views

mites

COE Permit Procedure
03. 01. 2008
0 views

COE Permit Procedure

Miss You
09. 08. 2007
0 views

Miss You

history of malaria 2006
16. 10. 2007
0 views

history of malaria 2006

P0200412274947173437 13
16. 10. 2007
0 views

P0200412274947173437 13

Dalby presentation
31. 10. 2007
0 views

Dalby presentation

Medievallyrics
27. 11. 2007
0 views

Medievallyrics

metalurgy
05. 01. 2008
0 views

metalurgy

Sym06ppt Oram
29. 10. 2007
0 views

Sym06ppt Oram

cdc obesity 04
03. 08. 2007
0 views

cdc obesity 04

LSMD
07. 11. 2007
0 views

LSMD

gatewayspace
15. 10. 2007
0 views

gatewayspace

ENG private sector 2004
23. 11. 2007
0 views

ENG private sector 2004

Lecture8dna
15. 10. 2007
0 views

Lecture8dna

Tim POPL
04. 10. 2007
0 views

Tim POPL

M E Quiz Maria
24. 02. 2008
0 views

M E Quiz Maria

Ch 12 LMIs
29. 10. 2007
0 views

Ch 12 LMIs

FloodLATEST
29. 02. 2008
0 views

FloodLATEST

New Orleans
26. 06. 2007
0 views

New Orleans

M Surdeanu
26. 06. 2007
0 views

M Surdeanu

Mulvey
26. 06. 2007
0 views

Mulvey

law enforcement
19. 02. 2008
0 views

law enforcement

510Women Gender and DDR
06. 03. 2008
0 views

510Women Gender and DDR

NACEpresentation
10. 03. 2008
0 views

NACEpresentation

ec101Chp16
04. 10. 2007
0 views

ec101Chp16

De Toulon aux Canaries
24. 10. 2007
0 views

De Toulon aux Canaries

Tides pp
11. 03. 2008
0 views

Tides pp

Gaved Heath Eisenstadt Wikisym06
12. 03. 2008
0 views

Gaved Heath Eisenstadt Wikisym06

MVD
26. 06. 2007
0 views

MVD

MAGICJFee
22. 10. 2007
0 views

MAGICJFee

Neil Avent
20. 03. 2008
0 views

Neil Avent

The Great Wall of China
25. 03. 2008
0 views

The Great Wall of China

mikey
16. 10. 2007
0 views

mikey

12 hydro wind
07. 04. 2008
0 views

12 hydro wind

How to Apply for a Job
23. 10. 2007
0 views

How to Apply for a Job

Tice Materials 28
03. 01. 2008
0 views

Tice Materials 28

Ecot pres
09. 04. 2008
0 views

Ecot pres

melladoRomeprodNov11 04
31. 10. 2007
0 views

melladoRomeprodNov11 04

intro lect 4
07. 12. 2007
0 views

intro lect 4

peter
18. 06. 2007
0 views

peter

Pay Attention 092904
18. 06. 2007
0 views

Pay Attention 092904

p35 hamilton
18. 06. 2007
0 views

p35 hamilton

Riverside Ballroom Day2 215
18. 06. 2007
0 views

Riverside Ballroom Day2 215

QS plat sg2k
18. 06. 2007
0 views

QS plat sg2k

Prensky 04 07 NCLB post
18. 06. 2007
0 views

Prensky 04 07 NCLB post

pimrc 05 B
18. 06. 2007
0 views

pimrc 05 B

phys 560 Solar Neutrinos
18. 06. 2007
0 views

phys 560 Solar Neutrinos

HSTF Background
01. 11. 2007
0 views

HSTF Background

cis vdotolev
12. 10. 2007
0 views

cis vdotolev

impact of assessment
22. 10. 2007
0 views

impact of assessment

lecture20
28. 12. 2007
0 views

lecture20

poetry
15. 06. 2007
0 views

poetry

Context Future Technology
15. 06. 2007
0 views

Context Future Technology

New Credibility
15. 06. 2007
0 views

New Credibility

Secrets To Scientific Selling
15. 06. 2007
0 views

Secrets To Scientific Selling

Problem Solving Strategies
15. 06. 2007
0 views

Problem Solving Strategies

Power of one Person
15. 06. 2007
0 views

Power of one Person

Jack Dugan
26. 02. 2008
0 views

Jack Dugan

Prot Franjo
22. 11. 2007
0 views

Prot Franjo

pledge
15. 06. 2007
0 views

pledge

NOVE BernabeuMorales
01. 10. 2007
0 views

NOVE BernabeuMorales

vaisanen 181005
07. 10. 2007
0 views

vaisanen 181005

ASOCFILE092003051211 1920
22. 10. 2007
0 views

ASOCFILE092003051211 1920

01 Review of BKK Property Mkt
27. 03. 2008
0 views

01 Review of BKK Property Mkt

2006drt6903cours11
14. 11. 2007
0 views

2006drt6903cours11

abcstrea
19. 11. 2007
0 views

abcstrea

Yang Slid Sho
07. 11. 2007
0 views

Yang Slid Sho

IISR
26. 10. 2007
0 views

IISR

Mon Naughton
26. 06. 2007
0 views

Mon Naughton

praust
21. 11. 2007
0 views

praust

RH vili
18. 06. 2007
0 views

RH vili

DIPRE
17. 10. 2007
0 views

DIPRE

presentation prof liu
15. 10. 2007
0 views

presentation prof liu

Dynafluid Nozzle
03. 01. 2008
0 views

Dynafluid Nozzle