ITEC 420 - Section 3.3 - Church-Turing Thesis

Overview

• 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 Tenth Problem

• 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

Tenth Problem - Polynomials of One Variable: Decidable

• 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:
1. Input is a polynomial p over variable x
2. Evaluate p with x set successively to 0, 1, -1, 2, -2, ... Limit, -Limit
3. If p evaluates to 0 for any x, accept. Otherwise reject.

Tenth Problem - Polynomials of More than One Variable: NOT Decidable

• 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:
1. Input is a polynomial p over variables x, y, ...
2. Evaluate p with x, y, ... set successively to all combinations of 0, 1, -1, 2, -2, ...
3. 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

• 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

Definitions of Algorithms

• Solving Second and Tenth Problems required a formal definition of an algorithm


• Let's look at informal and formal definitions

Algorithm - Informal Definition

• 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

Formal Definitions of Algorithm

• 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

• 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)?

CT Thesis and Language Wars

• 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

Coming in Chapter 4: Unrecognizable Languages

• 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