- Hilbert's Tenth Problem - discover an algorithm to find integral roots for polynomials:
- Leading to another example of a TD algorithm
- Leading to an example TR but TD algorithm
- Hilbert's Second Problem - discover an algorithm to determine if a mathematical statement is true or false:
- Proved that no algorithm exists!
- Solving second and tenth problems required a
**formal definition of an algorithm**: - Church Turing Thesis
- Intuitive and formal definitions of an algorithm are equivalent
- All programming languages are equivalent

- Hilbert's Problems: 1900, 23 challenge problems for the 20th century
- Tenth Problem: Find an
**algorithm**to determine if a polynomial has an integral root - Polynomial p has integral roots if the variables of p can be assigned to integer values to make p evaluate to 0
- Example: p(x) = x^2 -3x + 2 = (x-1)*(x-2) has integral roots 1 and 2 because p(1) = p(2) = 0
- Problem Solved (1970): Recognizer possible, but no decider

- Problem: language D = {p | p is a string that represents a polynomial of one variable with an integral root}
- D is decidable
- A TM can be built that decised whether or not a polynomial p is in D (ie has an integral root)
- D is decidable because for polynomials over one variable, a limit for the root is known to exist
- (ie the root must be between ± Limit)
- Machine M Decides D:
- Input is a polynomial p over variable x
- Evaluate p with x set successively to 0, 1, -1, 2, -2, ... Limit, -Limit
- If p evaluates to 0 for any x, accept. Otherwise reject.

- It's been proved that there is NO limit to the roots when there are more one variable in an polynomial
- Problem: language D = {p | p is a string that represents a polynomial with an integral root}
- D is recognizable, but not decidable
- Machine M recognizes D:
- Input is a polynomial p over variables x, y, ...
- Evaluate p with x, y, ... set successively to all combinations of 0, 1, -1, 2, -2, ...
- If p evaluates to 0 for any combination, accept
- For polynomials over several variables, it is proven that no limit exists
- if p has integral roots, the algorithm will find them
- but if p has no integral roots, the algorithm runs forever
- Thus M is a recognizer but not a decider

- Hilbert's second problem:
- Given a set of formal system and a mathematical statement give an algorithm to determine if a statement is true or false in the system.
- No such algorithm (ie decider) can exist: proved in 1936, independently, by Alonzo Church and Alan Turing
- The negative result for the Tenth problem also implies the negative result for the Second problem

- Solving Second and Tenth Problems required a formal definition of an algorithm
- Let's look at informal and formal definitions

- Informal definition:
- Finite number number of steps
- Each step doable
- Eventually halts
- Could in theory be done with pencil and paper
- If you have enough of each and enough time
- Informal definition long accepted (eg Euclid's algorithm for greatest common factor)
- But, informal definition not good enough for analysis of what algorithms are possible

- Alonzo Church invented λ calculus (defining computation with mathematical functions)
- Turing invented Turing Machines
- Equivalent definitions:
- λ calculus and Turing Machines have been proved equivalent
- Anything calculated by one can be calculated by the other
- Other equivalent definitions have been developed (eg Post Correspendence Problems)

- Church-Turing thesis: Informal notion of algorithm is the same as (any of) the formal definition(s)
- Result: Anything that can be computed (in the informal sense) can be computed with a Turing Machine (or with the λ calculus, or with ...)
- This is a Thesis:
- Could it be proved?
- Could it be disproved (ie shown to be false)?

- Any language that can simulate a TM has equivalent power
- Called:
**Turing Complete Languages** - What languages can simulate a TM: Virtually all
- Language wars???
- All Turing Complete languages are equivalent in power
- although not in readability/writability
- and there are memory constraints, as well

- So far we have seen:
- Turing Decidable Languages
- Turing Recognizable Languages
- Turing Recognizable Languages that are not Decidable
- In Chapter 4 we will see:
- That languages that are
**NOT***Turing Recognizable***must exist** - Some specific languages that are not Turing recognizable
- In the process we see how to prove that a language is not recognizable