# 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