Computation
I – Intro & Motivation
Let’s step back in time
Copyright By PowCoder代写 加微信 powcoder
This man had a dream
The “stepped reckoner” (Staffelwalze): the first digital (mechanical) calculator performing arithmetic
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
This man had a dream too
“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).”
believed strongly that there exists a solution to the “Entscheidungsproblem”
decision procedure
These guys shattered it
(formalisation
of) arithmetic cannot be complete
and consistent
true sentences of arithmetic cannot be
Turing Alonzo Church
“Entscheidungsproblem”
There is no program/machine/procedure that can decide whether any given formula in arithmetic is actually true. Sorry !
.Turing: ‘On computable numbers, with an application to the Entscheidungsproblem’ from Proceedings of the London Mathematical Society, (Ser. 2, Vol. 42, 1937);
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!!
Sometimes we cannot compute it!
e.g. Hilbert’s Decision Problem from earlier
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?
Sometimes we cannot afford it!
Annoyingly…
• … even decidable (computable) problems sometimes are problematic.
• They may take a long time to compute.
TOO LONG ACTUALLY!
Examples of computable problems that are intractable
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.
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!
18,44 bn bn
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?
Computational Complexity
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?
Why are these important questions? udience Participation
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
Programs as objects of scientific study
Organisation & Overview
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?
• Organisation 2022
Tue 11am SHAW-AS1, Thur 10am SHAW-AS2
Tue 1pm JB G36,Thur 3pm and 4pm,ARUN-1B, start in week 2 Sussex Direct tells you which group you’re in, please stay there throughout the term
• Coursework
Problem Set (60% week 6, March 3rd) + Test (40% week 11, April 28th, online)
DISCLAIMER: dates may change, always consult Sussex Direct!
• Assessment 50% CWK + 50% CEX (online)
• Web Canvas Site (with all info)
There is a Reading List for this module on Canvas.
CourseText
condensed notes will be available for free on Canvas
shameless plug
a few copies in the library
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
price for United Kingdom (gross) Buy eBook
http://www.springer.com/services+for+this+book?SGWID=0-1772415-3260-0-9783319278872
Other literature
• 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,
© 2008-22. , University of Sussex
Next time:
We define “Algorithms and Algorithmic Problems”
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com