Limits of
Computation
2 – Effective Procedures & Algorithmic
Problems Bernhard Reus
1
Last time
• we met our first non-computable (undecidable) problem: Hilbert’s Entscheidungsproblem.
• We motivated why we are interested in the limits of computability.
• We’ve seen a problem for which a brute- force solution is intractable (TSP).
2
First Computability Question
need to sort
out first the terms in “quotes”
Can every “problem” be solved, i.e. “computed” by some “program”?
3
Effective Procedures
• in this lecture we fix the notion of
• program (“effective procedure”)
• problem
• computable problem
a procedure.
4
Algorithms
• algorithm: named (like algebra) after the ninth century Persian mathematician Al-Khwarizmi.
• Euclid’s famous algorithm for “greatest common divisor” (gcd)
• algorithm is an “effective method”
Euclid ca 330-275 BC
5
Effective Procedures, Algorithms
• “effective procedure” or “effective algorithm” replaces our earlier “program run on a computer”;
• abstracting away from concrete hardware; We can define it as we wish …
• … if we can justify the choice later.
6
Effective Procedures?
• What does effective procedure mean to you? Discuss!
effective
1 successful in producing a desired or intended result: effective solutions to environmental problems
(Oxford Dictionaries)
7
Effective Procedure
The naming goes back to Alan Turing: “A function is said to be effectively calculable if its values can be found by some purely mechanical process. . . . We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine “
Turing then defined a specific type of machine, now called “Turing machines”, thus defining formally a notion of computation
Alan Turing : 1936
8
Alan Turing : 1936
“Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child’s arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one- dimensional paper, i.e., on a tape divided into squares. I shall also suppose that the number of symbols which may be printed is finite. If we were to allow an infinity of symbols, then there would be symbols differing to an arbitrarily small extent. The effect of this restriction on the number of symbols is not very serious. It is always possible to use sequences of symbols in the place of single symbols. … The difference from our point of view between the single and compound symbols is that the compound symbols, if they are too lengthy, cannot be observed at a glance. .. We cannot tell at a glance whether 9999999999999999 and 999999999999999 are the
same.
9
Effective Procedure
Copeland gives the following definition:
“ ’Effective’ and its synonym ’mechanical’ … do not carry their everyday meaning. A method, or procedure, M, for achieving some desired result is called ’effective’ or ’mechanical’ just in case
1. M is set out in terms of a finite number of exact instructions (each instruction being expressed by means of a finite number of symbols);
2. M will, if carried out without error, always produce the desired result in a finite number of steps;
3. M can (in practice or in principle) be carried out by a human being unaided by any machinery save paper and pencil;
4. M demands no insight or ingenuity on the part of the human being carrying it out. “
10
What is not Effective?
• Can you give an example of a procedure that is not “effective”?
effective
1 successful in producing a desired or intended result: effective solutions to environmental problems
(Oxford Dictionaries)
11
Problem?
12
What’s Our Problem? • a general, uniform class of questions
•
• each of which can be given a definite and
answer means there is some clearly defined solution. • solving it means providing a function or deciding
uniform means there is some clearly defined “parameter” (input).
finite answer
• to the problem
i.e. we need to be able to describe a finite solutio
membership in a set
these are called
algorithmic problems
13
n
Problem Examples
defines function
Given any tree t, what is its height? uniform
Given any number n, is it even? uniform
“height”
decision problem (answer yes/no)
14
Problem Examples uniform
Given any graph G, and vertices s and t what is the shortest path in G from s to t?
special kind of “function” problem
optimisation problem (minimal/maximal solution)
15
Computing Solutions to Problems
algorithmic problems
Definition Provided a certain choice of effective procedures P, a (function or decision) problem is called P-computable if, and only if, its solution can be computed (calculated) by carrying out a specific such effective procedure in P. A decision problem that is P-computable is also called P-decidable.
• •
so programs (effective procedures) are solutions to computable/ decidable problems
we drop the “P” in P-computable if the language is clear from the context.
16
Reminder on Logic
17
Formal notation
• we will need to be formal in this module, otherwise there is no point in talking about things like computability;
• we use some mathematical language (but this does not mean we do maths) for:
• sets and relations
• functions (partial and total), polynomials etc. • basic probability theory (towards the end)
• and to denote logical arguments in proofs:
and, or, not, iff, forall, exists
will be introduced/ recapitulated in exercises and when needed
18
“if, and only if”
• it means: logical equivalence
• we will use this often and sometimes abbreviate it “iff”
• “A iff B” = “(A implies B) and (B implies A)”
• Consider examples:
A = “Rain” B = “Wet Road”
A =“divisible by 3” B = “sum of digits divisible by 3”
19
CHAPTER2NCTIONS
We say that and only if, every elemen write
2.2.SEBLEMS
where ) de .P denotes universal qua
In the above version ,)
. PROBLEMS 2.2. SETS, RELATIONS AND FU
S1✓S2 ()8x2T.x2S1)x2S2 S1=S2 ()8x2T.x2S1,x2S2
TS, RELATIONS AND FUNCTIONS CHAPTER 2. PRO
Sets
asetS1 isasubsetofasetS2 (orSiscontainedinS2)if,
subset
tofS isalsoanelementofS.Moreformallywecanalso r1elation forall 2 “in” (elementhood)
notes implication and , denotes equivalence and 8x 2 T
x2S [S ()x2S _x2S ntificationoverall1elem2entsoftyp1eT. 2
and (conjunction)
definitionweused1thep2hrase“if,a1ndonlyif2”(intheformal
or (disjunction)
x2S1\S2 ()x2S1^x2S2 x2S\S ()x2S^¬(x2S)
“if” (formally () for a good reason. For a definition, it i iff (if, and only if)
denotes logical disjunction (“or”), ^ denotes logical conjunction cases exactly. Consider the following statement: “Sets A a
notes logical negation (“not”). If x is not contained in A, we usuall
ers) are equal if S and T are both the empty set.” This is x 2 A) by simply writing
andnotjustsimportant where _ (“and”),
tocoverallndB(over and¬deyabbre-
natural numb obviously a
viate ¬(
correct statement about equality of sets A and B. But it is far from a definition of x 2/ A .
equality. The statement does not specify anything about the equality of non-empty If S is a set of elements of type T, we call T \S the complement of S, which is
sets. Clearly, its contraposition “If A and B are equal sets then A and B are both sometimes also abbreviated S.
empty” is wrong. Thus the statement “Sets A and B (over natural numbers) are equal
20
Example 2.2. Here are some concrete examples of set operations and their results: if, and only if, S and T are both the empty set.” is equally wrong.
{}
away from the number of occurrences. An object simply “is either i of elements of type T . The elementhood operation is a statement
hw
es ch
e s
u o
t
a re
e
ch H
et }n
y ss
,
n
=
H a
re oe
}n v
Ty S hge ,e
o indicate an infinite set when the condition P used to define it is clea
a
h
ave such knowledge for all objects of the given underlying type
defined a set.
fix some n ment x is
x 2 A
otation:
in set A (“belongs to A”, “is contained in A
finite set contSaienitngNn doiftfearteniot onbjects e , e , . . te down all the elements. In this case w1e u2sua
lements are in the set as follows (which can als
{e ,e ,…,e }
is a type and1 P(2x) dennotes a condition on varia
jects contained in a set, the elements of this set
finite set with n elements
{x 2 S | P(x) }
contains no elements at all and is usually denot
s of type T . The elementhood operation is a st elements of type S that have property P. Th
ted N (which contains 0), the integer number x2A
is denoted R. The type of Boolean values {tr in set A (“belongs to A”, “is contained in A”
set of those elements in S that have property P
(Sets).A annotwrillynwritet
swhicheobeused ets).IfSblexthen
lthoseob.Theemp esetthated{}or0/
felementatement setofalletypeof
sisdenosisdenot numbersue,false}
ementxis).Ifthes 21
annot write down all the elements. In this case we usually write t ere are some examples of finite sets with object (elements) in N: s which elements are in the set as follows (which can also be used
s:eths)e.sIeftSoifsnaatyupraelanudmPb(exr)sdceonnottaeisniancgotnhdeitihorneeonelveamrieanbtlse1x,t1h0ena set conta
”). If the .e iswri
{x 2 S | P(x) } ining no natural number.
he infinite set of all even natural numbers, whi elements of type S that have property P. The
}. The notation with … followed by a closin ted N (which contains 0), the integer numbers
an infinite set when the condition P used to defi END
is denoted R. The type of Boolean values {tr that in this example the condition P(x) is “x i
© 2008-21. Bernhard Reus, University of Sussex
n 2 }: the finite set containing the first thre
1 2 Nexttime:
0=10 and100=10 .Soinfactthissetis
me examples of finite sets with object (elemen
WHILE programs in lity of sets follows these examples.
detail: Syntax and
f natural numbers containiSnegmatnhtiecsthree elemen
lity and subsets). Let S1 and S2 be two sets r
even}:tchisthe set of all type of
10,12,…g}issom s is deno is denot
indicateneitiscl
numbersue,false} text.Noteseven”.
10n,0epowers 1 = 100, 1 equal to t
erearesots)inN: bout equa
:thesetots1,10a (Setequaangingo
soeft ocbojnetcatisn.inWgensoaynatthuartatlwnoumsebtesrS. 1 and S2 are equal, short S1 = 22
seeyvceonn}t:atihnexinaficntliytethsetsaomf aellelevmenentast.uTrhalisncuomnbfiermrs,swthhaitciht isethneous e1l0em, 1e2n,t.s. .a}r.eTinhethneosteatiaondwwithic.h. .nfotlltowuendiqbuyelaycdloefisinega}siest.som