[SOLVED] CS algorithm data structure Limits of

Limits of
Computation
I Intro & Motivation Bernhard Reus
1
Lets 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 Im 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 Godel
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. Hilberts 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 cant be solved by programs?
How can one see or find out that a problem cant 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 (contd)
for N disks it takes 2N-1 moves to complete the task
if you could move one million disks per second (!), for N=64 youd 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.111033
64
0.991087
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 youre 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