# CS代考计算机代写 algorithm Limits of

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)

x2S1S2 ()x2S1^x2S2 x2SS ()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