## TM Parts

• FSM and Tape (Infinite in 1 direction)

• $\Sigma \subset\ \Gamma$

• $\textrm{ blank } \in \Gamma, \textrm{ blank } \notin \Sigma$

• Transition: Read, Write, Move (L/R), state
• Move Left on Left end of tape leaves head on left end
• Unique accept state, unique reject state

## Computation

• Tape initially has Input string on left end, rest of tape has blanks

• Computation ends if accept or reject state is entered

• Computation can loop

## Accepting/Recognizing a String

• $M$ accepts $w$ if $w$ determines a computation from the initial state to the accept state

• $M$ does NOT accept a string if the computation on w
• Enters the reject state (halting the machine)
• Loops

## Looping

• Notice that the TM is deterministic and it loops

• NFA and NPDA can loop, but
• DFA and DPDA can not loop

## Do More Tapes Give More Power?

• No: A single tape machine can simulate a mutitape machine
• How: Encode multiple tapes on a single tape
• Example: Encode Tapes 1 and 2 onto Tape 3
• Assume machine M1 has tape T1
• Assume machine M2 has two tapes T2 and T3(and two read heads)
• Transitions Read/Write pairs of symbols, and move a pair of directions

• Simulate M2 on Machine M1 (with tape T1)

• Example: Tape 2: 123 (head on 2) and Tape 3: abc (head on c)
• Use a special symbol (eg #) to separate tapes on T1: 123#abc
• Use dotted symbols to mark tape head: dotted 2 and c above
• Rewrite transitions to update dotted symbols, etc

## Does Nondeterminism Give Extra Power?

• No: A DTM can simulate a NTM
• How: Use 3 tapes to simulate all possible computations (until accept/reject):
1. Tape 1: copy of input string
2. Tape 2: used to execute current computation
• Step 1: copy input string from tape 1
• Step 2: execute branches of computation as shown on tape 3
3. Tape 3: Lists branches taken in all computations of length 1, 2, 3, ...
• Tries $b$ branches at each step, where $b$ is max number of branches out of a state
• Example: if b is 3, try 1; 2; 3; 1,1; 1,2; 1,3; 2,1; 2,2; ... 3,3; 1,1,1; ...

## Accepting/Recognizing a Language

• $L(M)$ is the language Accepted/Recognized by TM $M$
• $L(M)=\{w|M \textrm{ accepts } w\}$
• We say, $M$ accepts/recognizes $L$ iff
• $w \in L(M) \Rightarrow M$ halts on $w$ in accept state
• $w \notin L(M) \Rightarrow M$ halts on $w$ in reject state, or loops

## Deciding a Language

• We say, $M$ decides $L$ iff
• $w \in L(M) \Rightarrow M$ halts on $w$ in accept state
• $w \notin L(M) \Rightarrow M$ halts on $w$ in reject state (ie does not loop)
• (ie $w \in L^C \Rightarrow M \textrm{ enters reject state}$

## Turing Recognizable and Turing Decidable Languages

• Language $L$ is Turing Recognizable iff some TM $M$ recognizes $L$

• Language $L$ is Turing Decidable iff some TM $M$ decides $L$

• All languages we've seen so far have been TR and TD

• Later we will see: non-TR languages exist (more languages than TMs)

## Example 1

• TM $M_1$: Transitions from start state:
• loop on 0 and move Right
• enter Accept on blank
• Enter reject state on 1

• What is $L_1 = L(M_1)$?

• Is $L_1$ TR?
• Is $L_1$ TD?

## Example 2

• TM $M_2$: Transitions from start state:
• loop on 0 and move Right
• enter Accept on blank
• Enter Loop state on 1 (ie move left on all inputs, forever)
• In loop state, move Left on all inputs, forever)

• What is $L_2 = L(M_2)$?

• Does $M_2$ recognize $L_2$?
• Does $M_2$ decide $L_2$?

• Is $L_2$ TR?
• Is $L_2$ TD?

• Be careful of this distinction: Being TR/TD vs having a recognizer/decider
• If L has a Decider it is ...
• If L has a Recognizer it is ...

## A Hierarchy of Languages

• All: ?? (All Languages is all sets of strings)
• TR: ??
• TD: $w\textrm{#}w$
• CF: $0^n1^n$
• RL: $0^n$

## A Language that is TR but not TD

• Define a language that is TR but not TD in the context of integer roots to polynomials with integer coefficients

• Example polynomial: $7x^2y+3z$
• Set the polynomial equal to 0 to get a Diophantine equation
• Example Diophantine equation: $7x^2y+3z = 0$
• First look at polynomials in 1 variables
• Then look at polynomials in more than 1 variable

## Polynomials in 1 Variable

• Some example polynomials in 1 variable:
1. $x^2+3x+2$
2. $x^2+1$
3. $7x^{23}+9x^{13}-3x^{10}+x^2-5$

• Which have integer roots?

## The Language of Polynomials with Integer Solutions

• Let $D_1$ be the language of all polynomials of one variable with integer roots
• Assume a proper encoding of polynomials as strings
• Are the polynomials above in this language

• TM $M_1$ determines whether polynomial $P$ is in $D_1$:
• Try all values for x: 0, 1, -1, 2, -2, 3, -3, ...
• If $x$ is a root for $P$, then accept
• If $x$ is a not root for $P$, then machine will loop

• Can we make $M_1$ halt?
• Yes: for any $P$, a limit for $x$ is known
• Only need to test up to that limit
• Modify $M_1$ so that it rejects if it reaches this limit

• IS $D_1$ TR? Is it TD?

## Polynomials in Several Variables

• Consider 2 variables: $x$ and $y$
• Example: $7x^2y^3 + 9x^2y + 7x • Let$D$be the language of all polynomials of with any number of variables variables with integer roots • Define machine$M$, similar to (modified)$M_1$above: try$(x, y)$values (0,0), (0,1), (1,0), (1,1), (0,2), ... • Are there limits for x and y? Yes • However, it has been proven that no limit exists for arbitrary number of variables • Thus if$P \in D$, then$M$halts and Accepts, • But if$P \notin D$, then$M$loops • Is$D\$ TR? Is it TD?

## A TR but not TD Language

• You might ask, is there a clever TM that determines if there are integer roots without simply trying values
• It has been proven that there is not such a machine
• Can't do better than trying pairs
• This was done essentially by showing that Diophantine Equations and TMs are equivalent
• For every DE you can find an equivalent TM
• For every TM you can find an equivalent DE

• It has been proved (around 1970) that no TM can determine if an arbitrary polynomial has integer roots

• Thus, language D is Turing Recognizable but not Turing Decidable

## Hilbert's Problems and What is Computation?

• In 1900 David Hilbert presented 23 most important math problems
• Hilbert: most famous, influential mathematician of his time

• Problem 10: Find a procedure for determining if a polynomial has integer roots
• As seen above, can be done for 1 or 2 variables, not for any number

• Problem 2: Find a general procedure for determining if a given statement can be proved from a set of axioms (and proof rules)

## What is Computation

• Answer to problem 2 (and later problem 10) required a formal definition of computation

• Turing invented Turing Machines to show that Problem 2 cannot be solved
• Independently proved by Church (using functions - ie lambda calculus)
• Turing followed work by Godel

## Godel's Theorem (1931)

• Any math system has true statements that cannot be proved to be true
• (Key Idea) Statement N: Statement N has no proof within the system
• If we could prove N, then N would have a proof and thus N would be false
• Thus, we can't prove N, and so it is true

• Thus we have a statement that is true, but can't be proved (within the system)

• Formal proof is much more complicated

## Church's Thesis

• Several definitions of computation have been invented
• Turing Machines
• Lambda Calculus (eg functions)
• Post Correspondence (like dominos - see text)
• Diophantine equations
• Others ...
• All have been proven to be equivalent
• Anything computable in one is computable in any

• Led to Church's Thesis:
• Anything that is computable, by any possible definition, is computable by a TM
• Is this provable?

## Turing Complete Languages: The End to Language Wars

• Languages that can implement a TM are called Turing Complete
• Subject to time and memory limitation

• Turing Complete languages can calculate anything

• Thus, all Turing Complete languages are equivalent in power
• Although some are easier to use than others

## Non TR Languages

• Next up: Non-TR languages

• Begin by defining language classes (eg ADFA)

ITEC 420 Course Page,