^^The decision problem.

The decision problem

is, roughly, a question with a yes/no answer. exs:

1. Is a given positive integer a prime number?
2. Are two given positive integers relatively prime?

decidable decision problem   there is an algorithm that always determines(correctly!) whether or not each instance of the problem has the answer yes or no.

Note we are asking for one algorithm that handles all cases: we want to settle all instances of the problem by common procedure.

The decision problems above are all decidable:

1. Trial division tells us in nitely many steps if a positive integer is prime. This may
   be very inefficient (e.g., for the number 2^82;589;933 - 1), but it works.
2. Euclid's algorithm tells us in nitely many steps if two positive integers are relatively prime.

We will not be giving a rigorous definition of an algorithm, but experience with standard
procedures for solving math questions

1. the division algorithm
2. the Euclidean algorithm in number theory

suggests what the concept is all about.

A key point is the finite nature of algorithms:

algorithm   a procedure with finitely many steps

like a computer program (programs do not have infinite length!) with no infinite loops allowed.

ref: kconrad.math.uconn.edu/blurbs/grouptheory/wordproblem.pdf

Talk

pagina creata in relazione a Word problem. Linguaggio formale.