# The Limits Of Computing

Information about The Limits Of Computing

Published on January 7, 2008

Author: FunnyGuy

Source: authorstream.com

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

02. 05. 2008
0 views

28. 04. 2008
0 views

22. 04. 2008
0 views

18. 04. 2008
0 views

17. 04. 2008
0 views

16. 04. 2008
0 views

14. 04. 2008
0 views

13. 04. 2008
0 views

10. 04. 2008
0 views

22. 10. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

27. 02. 2008
0 views

27. 09. 2007
0 views

05. 10. 2007
0 views

10. 10. 2007
0 views

10. 10. 2007
0 views

15. 10. 2007
0 views

17. 10. 2007
0 views

22. 10. 2007
0 views

21. 10. 2007
0 views

05. 10. 2007
0 views

15. 10. 2007
0 views

23. 10. 2007
0 views

29. 10. 2007
0 views

30. 10. 2007
0 views

15. 11. 2007
0 views

16. 11. 2007
0 views

19. 11. 2007
0 views

20. 11. 2007
0 views

15. 11. 2007
0 views

26. 11. 2007
0 views

23. 10. 2007
0 views

30. 10. 2007
0 views

30. 12. 2007
0 views

01. 01. 2008
0 views

03. 01. 2008
0 views

09. 08. 2007
0 views

16. 10. 2007
0 views

16. 10. 2007
0 views

31. 10. 2007
0 views

27. 11. 2007
0 views

05. 01. 2008
0 views

29. 10. 2007
0 views

03. 08. 2007
0 views

03. 08. 2007
0 views

07. 11. 2007
0 views

15. 10. 2007
0 views

23. 11. 2007
0 views

15. 10. 2007
0 views

04. 10. 2007
0 views

24. 02. 2008
0 views

29. 10. 2007
0 views

29. 02. 2008
0 views

26. 06. 2007
0 views

26. 06. 2007
0 views

26. 06. 2007
0 views

19. 02. 2008
0 views

06. 03. 2008
0 views

10. 03. 2008
0 views

04. 10. 2007
0 views

24. 10. 2007
0 views

11. 03. 2008
0 views

12. 03. 2008
0 views

26. 06. 2007
0 views

22. 10. 2007
0 views

20. 03. 2008
0 views

25. 03. 2008
0 views

16. 10. 2007
0 views

07. 04. 2008
0 views

23. 10. 2007
0 views

03. 01. 2008
0 views

09. 04. 2008
0 views

31. 10. 2007
0 views

07. 12. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

01. 11. 2007
0 views

04. 03. 2008
0 views

12. 10. 2007
0 views

22. 10. 2007
0 views

28. 12. 2007
0 views

15. 06. 2007
0 views

15. 06. 2007
0 views

15. 06. 2007
0 views

15. 06. 2007
0 views

15. 06. 2007
0 views

15. 06. 2007
0 views

27. 09. 2007
0 views

26. 02. 2008
0 views

22. 11. 2007
0 views

15. 06. 2007
0 views

01. 10. 2007
0 views

07. 10. 2007
0 views

22. 10. 2007
0 views

27. 03. 2008
0 views

14. 11. 2007
0 views

19. 11. 2007
0 views

07. 11. 2007
0 views

26. 10. 2007
0 views

26. 06. 2007
0 views

21. 11. 2007
0 views

18. 06. 2007
0 views

17. 10. 2007
0 views

15. 10. 2007
0 views

03. 01. 2008
0 views