Limits of
Computation
I – Intro & Motivation Bernhard Reus
1
Let’s step back in time
2
This man had a dream
1646-1716
The “stepped reckoner” (Staffelwalze): the first digital (mechanical) calculator performing arithmetic
Gottfried Wilhelm Leibniz
Alas, it did not work reliably!
maybe I’m the first computer
scientist!
1672-1694 invented differential & integral calculus (independently of Newton), modern formal logic, and more
3
This man had a dream too
1928
“The Entscheidungsproblem (German for “decision problem”) asks for a procedure which allows one to decide, using a finite number of operations, on the validity, respectively the satisfiability, of a given logical expression (in number theory).”
yes no
David Hilbert believed strongly that there exists a solution to the “Entscheidungsproblem”
decision procedure
4
1932/1936
These guys shattered it
(formalisation
of) arithmetic cannot be complete
and consistent
Kurt Gödel
true sentences of arithmetic cannot be
decided
Alan M Turing Alonzo Church
5
“Entscheidungsproblem”
There is no program/machine/procedure that can decide whether any given formula in arithmetic is actually true. Sorry David Hilbert!
Alan M.Turing: ‘On computable numbers, with an application to the Entscheidungsproblem’ from Proceedings of the London Mathematical Society, (Ser. 2, Vol. 42, 1937);
6
Major Impact on Science
• not every problem (that can be clearly formalised and understood) can be solved (in this case the answer is yes/no only) by a program
• So, there are obviously limits to what programs can do!!
7
Sometimes we cannot compute it!
e.g. Hilbert’s Decision Problem from earlier
8
Computability Questions
• Are there problems that cannot be solved by a program on a computer?
• Does it matter which computer/language we use?
• Can one identify classes of problems that can be solved by programs or that can’t be solved by programs?
• How can one see or find out that a problem can’t be solved by a program?
9
Sometimes we cannot afford it!
10
Annoyingly…
• … even decidable (computable) problems sometimes are problematic.
• They may take a long time to compute.
TOO LONG ACTUALLY!
11
Examples of computable problems that are intractable
12
Towers of Hanoi
• move all disks from 1st to 3rd rod
• only take/put disks from/on top of rods • never put disk on a smaller disk.
13
Towers of Hanoi (cont’d)
• for N disks it takes 2N-1 moves to complete the task
• if you could move one million disks per second (!), for N=64 you’d still need about 585,000 years to finish the job!
Even for meditating monks this is too long!
disks
moves
3
7
4
15
8
255
16
64535
32
4,294 bn
64
18,44 bn bn
14
TravellingSalesmanProblem
• Given a number of cities and the costs of travelling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the start?
15
TravellingSalesmanProblem Combinatorial
• the number of tours to search through grows exponentially with the number of cities N, namely (n-1)! / 2
• Any brute force technique must fail. But are there clever ways?
explosion
cities
tours
3
1
4
3
8
2520
16
653.8 bn
32
4.11×1033
64
0.99×1087
There are only
about 1080 atoms in the known universe.
16
Computational Complexity
•
•
Questions
Which problems can be solved within certain limits of time (and space)?
Are there resource limits within which certain combinatorial problems cannot be solved?
•
• Does adding resources allow one to solve more problems?
Are intractable problems good for anything?
• How does one deal with intractable problems in practice?
• Can new emerging computing paradigms like Quantum computing and Molecular computing help?
17
Why are these important questions? Audience Participation
18
So what is this module for?
• you know the principles of
programming
➼ Programming Concepts
➼ Data Structures & Algorithms
➼ Program Analysis
• you know how to write programs
new:
Programs as objects of scientific study
19
Organisation & Overview
20
Scientific Questions About Programs
• What are programs? What are their limitations?
• What are their limits in terms of what we can achieve with programs?
• How can we spot the limits?
• How can we circumnavigate them?
• Can we exploit those limits for a benefit?
21
• Organisation 2021
Lectures
Mon 11am, Tues 5pm (for the time being all on Zoom)
• Classes
Wed 10am, Fri 12am, Fri 5pm (needed?) start in teaching week 2
Sussex Direct tells you which group you’re in, please stay there throughout the term Zoom)
• Coursework
Problem Set (60% week 6, March 4th)
+Test (40% week 11,April 29th online)
• Assessment 50% CWK + 50% UEX
• Web Canvas Site (with all info)
(for now on
22
There is a Reading List for this module on Canvas.
CourseText
eBook
price for United Kingdom (gross) Buy eBook
£26.99
shameless plug
a few copies in the library
Softcover
condensed notes will be available for free on Canvas
£33.99
ISBN 978-3-319-27889-6
Digitally watermarked, DRM-free
Included format: EPUB, PDF
ebooks can be used on all reading devices Immediate eBook download after purchase
http://www.springer.com/services+for+this+book?SGWID=0-1772415-3260-0-9783319278872
23
Other literature
• Neil D Jones: Computability and Complexity From a Programming Perspective,
MIT Press, 1997.
Online copy on Canvas Links page.
• Also useful maybe:
Hopcroft, Motwani, Ullmann: Introduction to Automata Theory, Languages, and Computation, Addison Wesley
24
END
© 2008-21. Bernhard Reus, University of Sussex
Next time:
We define “Algorithms and Algorithmic Problems”
25