CS代考计算机代写 algorithm data structure Limits of

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).”
decision yes
procedure
David Hilbert believed strongly that there exists a
solution to the “Entscheidungsproblem” 4
no

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