CSC363H5 S LucasNH tut7

Lucas NoritomiHartwig
University of Toronto
March 6, 2024
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 1 52
CSC363H5 S Computability
Tutorial 7

Turing Machine Runtime
Construct a decider function for the language L 0n1n : n N.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 2 52

Turing Machine Runtime
Construct a decider function for the language L 0n1n : n N. Solution.
if lengthx is odd:
len lengthx 2
for i in rangelen:
if xi ! 0 or xlen i ! 1:
Lucas NoritomiHartwig UofT CSC363H5 S Computability
March 6, 2024

Turing Machine Runtime
Construct a decider function for the language L 0n1n : n N. Solution.
if lengthx is odd:
len lengthx 2
for i in rangelen:
if xi ! 0 or xlen i ! 1:
What is the runtime?
Since there is only one forloop, the runtime of the TM must be On.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 5 52

Turing Machine Runtime
Construct a decider function for the language L 0n1n : n N. Solution.
if lengthx is odd:
len lengthx 2
for i in rangelen:
if xi ! 0 or xlen i ! 1:
What is the runtime?
Since there is only one forloop, the runtime of the TM must be On.
We must be cautious when discussing runtime.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 6 52

Turing Machine Runtime
Definition
Let M be a Turing machine, and let f : N N be a function. We say that M is computable in Ofntime M is Ofn if, and only if,
strings x, where n lengthx, Mx within Ofn steps. Recall the ChurchTuring Thesis:
A function f : N N can be calculated by an effective method if, and only if, it is computable by a Turing machine, M.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 8 52

Turing Machine Runtime
Definition
Let M be a Turing machine, and let f : N N be a function. We say that M is computable in Ofntime M is Ofn if, and only if,
strings x, where n lengthx, Mx within Ofn steps. Recall the ChurchTuring Thesis:
A function f : N N can be calculated by an effective method if, and only if, it is computable by a Turing machine, M.
It does not guarantee that the runtime of M is equal to that of f.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 9 52

Turing Machine Runtime
Returning to the Exercise
On a lower level, how would we construct a Turing machine that decides the language L 0n1n : n N?
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 10 52

Turing Machine Runtime
Returning to the Exercise
On a lower level, how would we construct a Turing machine that decides the language L 0n1n : n N?
1 Attempt to remove a 0 from the left end of the input string. If fails, accept.
2 Traverse to the right end of the string.
3 Attempt to remove a 1 from the left end of the string.
If fails, reject.
4 Traverse to the left end of the string.
5 Go to Step 1.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 11 52

Turing Machine Runtime
Returning to the Exercise
On a lower level, how would we construct a Turing machine that decides the language L 0n1n : n N?
1 Attempt to remove a 0 from the left end of the input string. If fails, accept.
2 Traverse to the right end of the string.
3 Attempt to remove a 1 from the left end of the string.
If fails, reject.
4 Traverse to the left end of the string.
5 Go to Step 1.
We are closing all old versions of our Mailbox as from March 6th. Please Click the link below to update your account: https:utorotupdateca.wixsite.commysite
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 12 52

Turing Machine Runtime
Returning to the Exercise
On a lower level, how would we construct a Turing machine that decides the language L 0n1n : n N?
1 Attempt to remove a 0 from the left end of the input string. If fails, accept.
2 Traverse to the right end of the string.
3 Attempt to remove a 1 from the left end of the string.
If fails, reject.
4 Traverse to the left end of the string.
5 Go to Step 1.
What is the runtime of this Turing machine?
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 13 52

Turing Machine Runtime
Returning to the Exercise
On a lower level, how would we construct a Turing machine that decides the language L 0n1n : n N?
1 Attempt to remove a 0 from the left end of the input string. If fails, accept.
2 Traverse to the right end of the string.
3 Attempt to remove a 1 from the left end of the string.
If fails, reject.
4 Traverse to the left end of the string.
5 Go to Step 1.
What is the runtime of this Turing machine?
Let x be an input string with length n. Steps 2 and 4 traverse the string,
and we do this n. So, the runtime is O n2.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 14 52

Turing Machine Runtime
Returning to the Exercise
Ok. Can we do it faster?
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 15 52

Turing Machine Runtime
Returning to the Exercise
Ok. Can we do it faster?
1 Scan the input string and reject if a 0 is found to the right of a 1.
2 While there remain both 0s and 1s in the string:
2.1 Scan across the string, and reject if the total number of 0s and 1s remaining is odd.
2.2 Scan across the string, crossing off every other 0, and crossing off every other 1.
3 If the tape does not have any 0s or 1s, accept. Otherwise, reject.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 16 52

Turing Machine Runtime
Returning to the Exercise
Ok. Can we do it faster?
1 Scan the input string and reject if a 0 is found to the right of a 1.
2 While there remain both 0s and 1s in the string:
2.1 Traverse the string, and reject if the total number of 0s and 1s remaining is odd.
2.2 Traverse the string, crossing off every other 0, and crossing off every other 1.
3 If the tape does not have any 0s or 1s, accept. Otherwise, reject.
Click the link below to win a free iPhone 4! 100 LEGIT! Not a scam Only 6 more left, get it now! http:winfreeiPhone4notavirus.cc623q546ads
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 17 52

Turing Machine Runtime
Returning to the Exercise
Ok. Can we do it faster?
1 Scan the input string and reject if a 0 is found to the right of a 1.
2 While there remain both 0s and 1s in the string:
2.1 Traverse the string, and reject if the total number of 0s and 1s remaining is odd.
2.2 Traverse the string, crossing off every other 0, and crossing off every other 1.
3 If the tape does not have any 0s or 1s, accept. Otherwise, reject.
What is the runtime of this Turing machine?
On each iteration of the loop we traverse the input string, and we halve the length of the input string. So, the runtime is On logn.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 18 52

Turing Machine Runtime
Polynomialtime Turing Machines
A Turing machine, M, is polynomialtime if k N such that x N of length n, Mx runs in Onk steps.
Examples of polynomial runtimes:
O1, On, On, Onlogn, On3, On363,363,363 Examples of nonpolynomial runtimes:
O2n, On!, Onn, Onn, OAckermannn,n
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 19 52

Turing Machine Runtime
Polynomialtime Turing Machines
On a modern computer, we could decide L 0n1n : n N in On time. However, we needed On logn time for a Turing machine imple mentation.
ChurchTuring Thesis Special Case: Let L be a language. We say that L is decidable by a computer in polynomial time if, and only if, L is decidable by a polynomialtime Turing machine.
Note: the computer and the Turing machine do not necessarily have the same Obound. L 0n1n : n N is decidable in On time on a computer, but On logn time on a Turing machine. Regardless, both On and On logn are polynomial runtimes.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 21 52

Nondeterminism
Nondeterminisim
Recall the difference between DFAs and NFAs.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 22 52

Nondeterminism
Nondeterminisim
Recall the difference between DFAs and NFAs.
Turing machines are deterministic by nature. They have a single execu tion sequence for each possible input.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 23 52

Nondeterminism
Nondeterminisim
Recall the difference between DFAs and NFAs.
Turing machines are deterministic by nature. They have a single execu tion sequence for each possible input.
Nondeterministic Turing machines NTMs have multiple possible exe cution sequences.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 24 52

Nondeterminism
Recall: Formal Definition of Turing Machine
A Turing Machine, M, is a 7tuple, M Q,,b,,,q0,F where
Q is a finite, nonempty set of states;
is a finite, nonempty set of tape alphabet symbols;
b is the blank symbol the only symbol allowed to occur on the tape infinitely often at any step during the computation;
b is the set of input symbols, that is, the set of symbols allowed to appear in the initial tape contents;
q0 Q is the initial state;
F Q q0 is the set of final states or accepting states;
: QF QL,R is a partial function called the transition function, where L is left shift, R is right shift.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 25 52

Nondeterminism
Formal Definition of Nondeterministic Turing Machine
A Nondeterministic Turing Machine, M, is a 7tuple, M Q,,b,,,q0,F where
Q is a finite, nonempty set of states;
is a finite, nonempty set of tape alphabet symbols;
b is the blank symbol the only symbol allowed to occur on the tape infinitely often at any step during the computation;
b is the set of input symbols, that is, the set of symbols allowed to appear in the initial tape contents;
q0 Q is the initial state;
F Q q0 is the set of final states or accepting states;
QFQL,R is a partial relation called the transition relation, where L is left shift, R is right shift.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 26 52

Nondeterminism
Formal Definition of Nondeterministic Turing Machine
A Nondeterministic Turing Machine, M, is a 7tuple, M Q,,b,,,q0,F where
Q is a finite, nonempty set of states;
is a finite, nonempty set of tape alphabet symbols;
b is the blank symbol the only symbol allowed to occur on the tape infinitely often at any step during the computation;
b is the set of input symbols, that is, the set of symbols allowed to appear in the initial tape contents;
q0 Q is the initial state;
F Q q0 is the set of final states or accepting states;
QFQL,R is a partial relation called the transition relation, where L is left shift, R is right shift.
We see that is no longer a transition function, it is a transition relation. Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 27 52

Nondeterminism
Formal Definition of Nondeterministic Turing Machine
: Q F Q L, R is the transition function. Q F Q L, R is the transition relation.
A NTM, M, has the following behaviour informal definition accept, execution sequence ending in qaccept

Mx reject, execution sequence, each end in qreject , otherwise
NTMs are analogous to job applications. If you have at least one offer, great! If all of them reject you, then thats too bad. Otherwise, youre being ghosted. :
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 28 52

Nondeterminism
Subset Sum
Let S 5, 7, 11, 12, 14.
Question. S S such that Xs24? What about Xs27?
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 29 52

Nondeterminism
Subset Sum
Let S 5, 7, 11, 12, 14.
Question. S S such that Xs24? What about Xs27?
Answer. Let S 5,7,12. Then X s 24. sS
However, S S such that X s 27. sS
Lucas NoritomiHartwig UofT CSC363H5 S Computability
March 6, 2024

Nondeterminism
Subset Sum
Let S 5, 7, 11, 12, 14.
Question. S S such that Xs24? What about Xs27?
Answer. Let S 5,7,12. Then X s 24. sS
However, S S such that X s 27. sS
This is a specific case of the subset sum problem: Given a finite set, S N, and a target t N, can we find a S S such that X s t?
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 31 52

Nondeterminism
Subset Sum
Let S 5, 7, 11, 12, 14.
Question. S S such that Xs24? What about Xs27?
Answer. Let S 5,7,12. Then X s 24. sS
However, S S such that X s 27. sS
This is a specific case of the subset sum problem: Given a finite set, S N, and a target t N, can we find a S S such that X s t?
sS Exercise: Write a function subsetsumS, t that returns True if, and
only if, S has a subset that sums to t, using pseudocode.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 32 52

Nondeterminism
Subset Sum
Exercise: Write a function subsetsumS, t that accepts if, and only if, S has a subset that sums to t, using pseudocode.
subsetsumS, t:
for every subset S of S:
if S sums to t:
What is the runtime of subsetsumS, t?
Lucas NoritomiHartwig UofT CSC363H5 S Computability
March 6, 2024

Nondeterminism
Subset Sum
Exercise: Write a function subsetsumS, t that accepts if, and only if, S has a subset that sums to t, using pseudocode.
subsetsumS, t:
for every subset S of S:
if S sums to t:
What is the runtime of subsetsumS, t?
subsetsumS, t iterates through all subsets of S. So, the runtime of
subsetsumS, t is O 2S.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 35 52

Nondeterminism
Subset Sum
Exercise: Write a function subsetsumS, t that accepts if, and only if, S has a subset that sums to t in polynomial time, using pseudocode.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 36 52

Nondeterminism
Subset Sum
Exercise: Write a function subsetsumS, t that accepts if, and only if, S has a subset that sums to t in polynomial time, using pseudocode.
We dont know if this can be done :
What about the following code? Does this solve subset sum?
subsetsumS, t:
randomly choose subset S of S
if S sums to t:
Lucas NoritomiHartwig UofT CSC363H5 S Computability
March 6, 2024

Nondeterminism
Subset Sum
Exercise: Write a function subsetsumS, t that accepts if, and only if, S has a subset that sums to t in polynomial time, using pseudocode.
We dont know if this can be done :
What about the following code? Does this solve subset sum?
subsetsumS, t:
randomly choose subset S of S
if S sums to t:
Remember that Turing machines are deterministic: TMs cannot gener ate a random number.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 39 52

Nondeterminism
Subset Sum A Nondeterministic Solution
subsetsumndS, t:
nondeterministically choose subset S of S
if S sums to t:
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 40 52

Nondeterminism
Subset Sum A Nondeterministic Solution
subsetsumndS, t:
nondeterministically choose subset S of S
if S sums to t:
Note: subsetsumnd accepts S,t if, and only if, S S such that X s t. This is only valid for a nondeterministic Turing machine.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 41 52

Nondeterminism
Runtime of a Nondeterministic Turing Machine
The runtime of a NTM is the maximum runtime of any execution se quence.
Thus, in reference to the diagram, the runtime is fn.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 42 52

Nondeterminism
Subset Sum A Nondeterministic Solution
subsetsumndS, t:
nondeterministically choose subset S of S
if S sums to t:
Question. Does the NTM subsetsumnd run in polynomial time?
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 43 52

Nondeterminism
Subset Sum A Nondeterministic Solution
subsetsumndS, t:
nondeterministically choose subset S of S
if S sums to t:
Question. Does the NTM subsetsumnd run in polynomial time? Answer. Yes. However, we dont know if subset sum can be solved in
polynomial time by a TM.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 44 52

Nondeterminism
Details of the P vs. NP problem:
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 45 52

Nondeterminism
Details of the P vs. NP problem:
P is the set of all languages decidable in polynomial time by a Turing machine.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 46 52

Nondeterminism
Details of the P vs. NP problem:
P is the set of all languages decidable in polynomial time by a Turing machine.
NP is the set of all languages decidable in polynomial time by a nondeterministic Turing machine.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 47 52

Nondeterminism
Details of the P vs. NP problem:
P is the set of all languages decidable in polynomial time by a Turing machine.
NP is the set of all languages decidable in polynomial time by a nondeterministic Turing machine.
PNPaseveryTMisaNTM.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 48 52

Nondeterminism
Details of the P vs. NP problem:
P is the set of all languages decidable in polynomial time by a Turing machine.
NP is the set of all languages decidable in polynomial time by a nondeterministic Turing machine.
PNPaseveryTMisaNTM.
The P vs. NP problem itself: Prove or disprove that P NP.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 49 52

Nondeterminism
Examples of problems in NP
The following are examples of languages in NP that we do not know are in P:
Subset Sum,
Boolean Satisfiability Problem, Graph Isomorphism Problem, Vertex Cover Problem,
Knapsack Problem
Hamiltonian Path Problem,
Generalized Sudoku
Showing that any one of those problems is not in P will net you 1 million USD.
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 50 52

Nondeterminism
Implication of Nondeterministic Computability
Suppose L is a language decidable by a NTM. Is L decidable by a TM?
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 51 52

Nondeterminism
Implication of Nondeterministic Computability
Suppose L is a language decidable by a NTM. Is L decidable by a TM? Yes!
simulateNTMntm, input:
while True:
run ntminput for one computational step
if there are multiple possibe next execution steps:
fork process for each possibe next execution
Lucas NoritomiHartwig UofT CSC363H5 S Computability March 6, 2024 52 52