# 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
• 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