Recall last lecture and Nondeterministic TMs Ola Svensson Computational Complexity TURING MACHINES The goals A model that can compute anything computable A model so simple and clean so that we can prove interesting results A Turing machine is described by a tuple A finite alphabet containing start symbolblank symbol A Turing machine is described by a tuple A finite alphabet containing A finite set of states containing and A function describing rules of each step: IF Input

symbol read THEN Work (output) tape read Current state Move input head New work (output) symbol Move work head Right Right Stay Left Stay Left Stay

Stay New state Example Start configuration of on input Input : Work/ output: State: IF Input symbol read THEN Work (output) tape read Current state Move input head

New work (output) symbol Move work head Right Right Stay Left Stay Left Stay Stay New state Example Input : Work/ output: State:

IF Input symbol read THEN Work (output) tape read Current state Move input head New work (output) symbol Move work head Right Right Stay Left Stay

Left Stay Stay New state Example Input : Work/ output: State: IF Input symbol read THEN Work (output) tape read Current state Move input head

New work (output) symbol Move work head Right Right Stay Left Stay Left Stay Stay New state Example Input : Work/ output: State:

IF Input symbol read THEN Work (output) tape read Current state Move input head New work (output) symbol Move work head Right Right Stay Left Stay

Left Stay Stay New state Example Input : Work/ output: State: IF Input symbol read THEN Work (output) tape read Current state Move input head

New work (output) symbol Move work head Right Right Stay Left Stay Left Stay Stay New state Example Input : Work/ output: State:

IF Input symbol read THEN Work (output) tape read Current state Move input head New work (output) symbol Move work head Right Right Stay Left Stay

Left Stay Stay New state Example Input : Work/ output: State: IF Input symbol read THEN Work (output) tape read Current state Move input head

New work (output) symbol Move work head Right Right Stay Left Stay Left Stay Stay New state Example Input : Work/ output: State: Hey, dont miss this! IF Input

symbol read THEN Work (output) tape read Current state Move input head New work (output) symbol Move work head Right Right Stay Left Stay Left

Stay Stay New state Example Input : Work/ output: State: IF Input symbol read THEN Work (output) tape read Current state Move input head New

work (output) symbol Move work head Right Right Stay Left Stay Left Stay Stay New state Example Input : Work/ output: State:

IF Input symbol read THEN Work (output) tape read Current state Move input head New work (output) symbol Move work head Right Right Stay Left Stay Left

Stay Stay New state Example Input : Work/ output: State: What do we compute? IF Input symbol read THEN Work (output) tape read Current state Move input head

New work (output) symbol Move work head Right Right Stay Left Stay Left Stay Stay New state Efficiency and Running Time Let and let Let be a Turing machine Efficiency and Running Time Let and let Let be a Turing machine

We say that computes if for every , whenever is initialized to the start configuration on input then it halts with written on its output type. Efficiency and Running Time Let and let Let be a Turing machine We say that computes if for every , whenever is initialized to the start configuration on input then it halts with written on its output type. We say that computes in -time if its computation on every input requires at most steps. Efficiency and Running Time Let and let Let be a Turing machine We say that computes if for every , whenever is initialized to the start configuration on input then it halts with written on its output type. We say that computes in -time if its computation on every input requires at most steps. DTIME(f(n)) = Set of languages that can be decided by a TM in

time Robustness of definition of Turing Machine The size of the alphabet doesnt really matter The number of tapes do not really matter (up to a square in the running time) It is able to simulate all other realistic models with polynomial slow down (except potentially quantum computers that still need to be built) Church-Turing Thesis: Any computable function can be computed by a Turing machine Universal Turing Machine Every binary string represents some Turing machine (write down A Turing machine has infinitely many representations (pad with ones) There exists a TM such that for every Moreover, if halts on input within steps then halts within steps where is a number independent of . ( depends on the number of states, alphabet, and tapes of ).

DIAGONALIZATION Cantors argument The set of infinite binary strings are uncountable = 2= 3 = 4 = 5= 6 = 7 = 1 = s is different from any string in the enumeration so it is not part of the enumeration Halting Problem The output of (? if doesnt halt) ={ 1 , 2 , 4 5 , 6 , } The set of strings for which or ? Halting Problem

The output of (? if doesnt halt) ={ 1 , 2 , 4 5 , 6 , } The set of strings for which or ? Suppose a TM M decides L. Let be its encoding. Then we get a contradiction on input since Deterministic Time Hierarchy The output of (? if does not halt in steps) ={ 1 , 2 , 4 5 , 6 , } The set of strings for which or ? Deterministic Time Hierarchy The output of (? if does not halt in steps) ={ 1 , 2 , 4 5 , 6 , } The set of strings for which or ? Suppose a TM M decides L in time n. Let be its encoding. Then we get a contradiction on input since Diagonalization The proof technique used two things about TMs 1. They can be encoded efficiently 2. There is a TM that can emulate any other without increasing running time or space too much Otherwise, they treated TMs as black boxes We will show today that such a proof cannot alone resolve P vs NP

NONDETERMINISTIC TURING MACHINES Nondeterministic Turing machines (NDTMs) Same definition as TMs except that NDTM has two transition functions and and a special state called When NDTM computes a function we envision that at each computational step it makes an arbitrary choice as to which of its two transition functions to apply For every input , we say that if there exists some sequences of these choices (called nondeterministic choices) that would make M reach on input Otherwise if every sequence of choices makes halt without reaching then we say We say that runs in -time if for every input and every sequence of nondeterministic choices, reaches either the halting state or within steps NTIME(f(n)) = Set of languages that can be decided by a NDTM in time Example

Input : Work/ output: State: IF Input Input symbol symbol read read THEN Work Work (output) (output) tape tape read read Current Current state state Move Move input input head head Right

Right Stay Stay New New work work (output) (output) symbol symbol for for Move Move work work head head New New state state Right Right Left Left Once we reach state , we run normal TM to check if number on work tape divides input. If then move to . If not move to Example

Input : Work/ output: State: IF Input Input symbol symbol read read THEN Work Work (output) (output) tape tape read read Current Current state state Move Move input input head head

Right Right Stay Stay New New work work (output) (output) symbol symbol for for Move Move work work head head New New state state Right Right Left Left Once we reach state , we run normal TM to check if number on work tape divides input. If then move to . If not move to Example

Input : Work/ output: State: IF Input Input symbol symbol read read THEN Work Work (output) (output) tape tape read read Current Current state state Move Move input input head

head Right Right Stay Stay New New work work (output) (output) symbol symbol for for Move Move work work head head New New state state Right Right Left Left Once we reach state , we run normal TM to check if number on work tape divides input. If then move to . If not move to

Example Input : Work/ output: State: IF Input Input symbol symbol read read THEN Work Work (output) (output) tape tape read read Current Current state state Move Move input input

head head Right Right Stay Stay New New work work (output) (output) symbol symbol for for Move Move work work head head New New state state Right Right Left Left Once we reach state , we run normal TM to check if number on work tape divides input. If then move to . If not move to

Example Input : Work/ output: State: IF Input Input symbol symbol read read THEN Work Work (output) (output) tape tape read read Current Current state state Move Move input

input head head Right Right Stay Stay New New work work (output) (output) symbol symbol for for Move Move work work head head New New state state Right Right Left Left Once we reach state , we run normal TM to check if number on work tape divides input.

If then move to . If not move to Example Input : Work/ output: State: IF Input Input symbol symbol read read THEN Work Work (output) (output) tape tape read read Current Current state state Move Move

input input head head Right Right Stay Stay New New work work (output) (output) symbol symbol for for Move Move work work head head New New state state Right Right Left Left Once we reach state , we run normal TM to check if number on work tape

divides input. If then move to . If not move to Example Input : Work/ output: State: IF Input Input symbol symbol read read THEN Work Work (output) (output) tape tape read read Current Current state state Move

Move input input head head Right Right Stay Stay New New work work (output) (output) symbol symbol for for Move Move work work head head New New state state Right Right Left Left

Once we reach state , we run normal TM to check if number on work tape divides input. If then move to . If not move to Example What language do we accept? Input : Work/ output: State: Now normal deterministic execution IF Input Input symbol symbol read read THEN Work Work (output) (output) tape tape read read Current Current state state

Move Move input input head head Right Right Stay Stay New New work work (output) (output) symbol symbol for for Move Move work work head head New New state state Right Right Left

Left Once we reach state , we run normal TM to check if number on work tape divides input. If then move to . If not move to