Understanding Complexity Theory and Turing Machines

CMSC 28100 Introduction to Complexity Theory Complexity Theory Spring 2025 Instructor: William Hoza 1

Homework Exercises 1-4 are available in Canvas (due on Tuesday) If you aren t officially enrolled, send me an email Office hours (Thursday, Friday, Monday) are a good place to find study partners / homework collaborators 2

Which problems Which problems can be solved can be solved through computation? through computation? 3

Defining Turing machines rigorously Definition: A Turing machine is a 7-tuple ? = ?,?0,?accept,?reject, , ,? such that Warning: The definition in the ?is a finite set (the set of states ) textbook is slightly different. Sorry! (The two models are equivalent.) ?0,?accept,?reject ? and ?accept ?reject is a finite set of symbols (the tape alphabet ) is a symbol (the blank symbol ) 0,1, and 0,1 ? is a function ?:? ? {L,R}(the transition function ) 4

Configurations of a Turing machine Let ? = ?,?0,?accept,?reject, , ,? be a Turing machine A configuration is a triple (?,?,?) where ? , ? ?, ? , and ? ? Interpretation: The tape currently contains ?? The machine is currently in state ? and the head is pointing at the first symbol of ? ?1 ?2 ?? ?2 ?? ?1 ? 5

The initial configuration Let ? 0,1 be an input The initial configuration of ? on ? is ?0? ?0 if ? = ? if ? ? 6

The next configuration For any configuration ???, we define NEXT ??? as follows: Break ??? into individual symbols: ??? = ?1?2 ?? 1????1?2?3 ?? If ? ?,?1 = ? ,?,R , then NEXT ??? = ?1?2 ?? 1???? ?2?3 ?? Edge case: If ? = 1, then NEXT ??? = ?1?2 ?? 1???? If ? ?,?1 = ? ,?,L , then NEXT ??? = ?1?2 ?? 1? ????2?3 ?? Edge case: If ? = 0, then NEXT ??? = ? ? ?2?3 ?? We write NEXT???? if ? is not clear from context 7

Halting configurations An accepting configuration is a configuration of the form ??accept? A rejecting configuration is a configuration of the form ??reject? A halting configuration is an accepting or rejecting configuration 8

Computation history Let ? 0,1 be an input Let ?0 be the initial configuration of ? on ? Inductively, for each ? , let ??+1= NEXT ?? The computation history of ? on ? is the sequence ?0,?1, ,??, where ?? is the first halting configuration in the sequence If there is no such ??, then the computation history is ?0,?1,?2, (infinite) 9

Accepting, rejecting, and looping If the computation history of ? on ? ends with an accepting configuration, then we say that ? accepts ? If the computation history of ? on ? ends with a rejecting configuration, then we say that ? rejects ? In either of those cases, we say that ? halts on ?. If the computation history of ? on ? is infinite, then we say that ? loops on ? 10

Time Suppose the computation history of ? on ? is ?0,?1, ,?? We say that ? is the running time of ? on ? If ? loops on ?, then its running time on ? is We say that ? halts on ? within ? steps if the running time of ? on ? is at most ? 11

Space The space used by ? on ?is the number of cells that are used I.e., the head visits the cell OR the cell initially contains an input bit (Can be ) Which of the following statements is false? A: Space used on ? is at most B: If ? halts on ? within |?| steps, then ? halts on ?? Formally, let ?0,?1, be the (finite or infinite) computation history of ? on ? ? + 1 + running time on ? C: If ? halts on ?, then ? uses a finite amount of space on ? D: If ? uses a finite amount of space on ?, then ? halts on ? Write ??= ??,??,?? where ?? , ?? ?, ?? Respond at PollEv.com/whoza or text whoza to 22333 The space used by ? on ? is max ???? ? 12

Which problems Which problems can be solved can be solved through computation? through computation? 13

Languages A binary language is a set ? 0,1 Each language ? 0,1 represents a distinct computational problem: Given ? 0,1 , figure out whether ? ? 14

Deciding a language Let ? be a Turing machine and let ? 0,1 We say that ? decides ? if ? accepts every ? ?, and ? rejects every ? 0,1 ? This is a mathematical model of what it means to solve a problem 15

Example: Palindromes Informal problem statement: Given ? 0,1 , determine whether ? is the same forward and backward. The same problem, formulated as a language: PALINDROMES = ? 0,1 ? is the same forward and backward 16

Example: A TM that decides PALINDROMES 0,1 R L ?0 0 R ?reject ?0 0,1 L L ?1 1 ?accept 0,1 R 17

Example: Parity Informal problem statement: Given ? 0,1 , determine whether the number of ones in ? is even or odd. The same problem, formulated as a language: PARITY = ? 0,1 ? has an odd number of ones 18

Example: A TM that decides PARITY Let ? = ?,?0, 1, 0, , ,? , where ? = ?0,?1, 0, 1, = 0,1, , and ? ??,? = ??+?,?,R if ? 0,1 ?,?,R (Addition is mod 2) if ? = Claim:?decides PARITY ? 0,1 ? has an odd number of ones Proof sketch: Let ?0,?1, be the computation history of ? on ? 0,1? By induction on ?, we have ??= ?1?2 ????1+ +????+1 ?? for all ? < ? Consequently, ??= ???1+ +?? and ??+1= ? ?1+ +?? 19

Example: Primality testing Informal problem statement: Given ? , determine whether ?is prime. Formulating the problem as a language: Let ? denote the binary encoding of ?, i.e., the standard base-2 representation of ? Example: 6 = 110. Note that ? whereas ? {0,1} Language: PRIMES = ? ? is a prime number 20

Encoding the input as a string OBJECTION: The fact that I have to encode the input before feeding it into a Turing machine seems fishy. This is not a pipe. (1929 painting by Ren Magritte) RESPONSE: The same is true of human computation! We say, Given a natural number, determine whether it is prime, but is it truly possible to give someone an abstract concept such as a number? Being pedantic, we could speak more precisely and say, Given a piece of text, determine whether it represents/encodes a prime number 21

Larger alphabets OBJECTION: Fine, the input needs to be encoded as a string. But why does it have to be a binary string? What about larger alphabets? RESPONSE 1: The Turing machine definition can be modified to handle inputs over other alphabets. We focus on binary inputs for simplicity s sake RESPONSE 2: We can always encode symbols from other alphabets in binary 22

Example: ASCII [NUL] 0000000 [CR] 0001101 [SS] 0011010 ' 0100111 4 0110100 A 1000001 N 1001110 [ 1011011 h 1101000 u 1110101 [SOH] 0000001 [SO] 0001110 [ESC] 0011011 ( 0101000 5 0110101 B 1000010 O 1001111 \ 1011100 i 1101001 v 1110110 [STX] 0000010 [SI] 0001111 [FS] 0011100 ) 0101001 6 0110110 C 1000011 P 1010000 ] 1011101 j 1101010 w 1110111 [ETX] 0000011 [DLE] 0010000 [GS] 0011101 * 0101010 7 0110111 D 1000100 Q 1010001 ^ 1011110 k 1101011 x 1111000 [EOT] 0000100 [DC1] 0010001 [RS] 0011110 + 0101011 8 0111000 E 1000101 R 1010010 _ 1011111 l 1101100 y 1111001 [ENQ] 0000101 [DC2] 0010010 [US] 0011111 , 0101100 9 0111001 F 1000110 S 1010011 ` 1100000 m 1101101 z 1111010 [ACK] 0000110 [DC3] 0010011 [SPACE] 0100000 - 0101101 : 0111010 G 1000111 T 1010100 a 1100001 n 1101110 { 1111011 [BEL] 0000111 [DC4] 0010100 ! 0100001 . 0101110 ; 0111011 H 1001000 U 1010101 b 1100010 o 1101111 | 1111100 [BS] [HT] [LF] [VT] [FF] 0001000 [NAK] 0010101 " 0100010 / 0101111 < 0111100 I 1001001 V 1010110 c 1100011 p 1110000 } 1111101 0001001 [SYN] 0010110 # 0100011 0 0110000 = 0111101 J 1001010 W 1010111 d 1100100 q 1110001 ~ 1111110 0001010 [ETB] 0010111 $ 0100100 1 0110001 > 0111110 K 1001011 X 1011000 e 1100101 r 1110010 [DEL] 1111111 0001011 [CAN] 0011000 % 0100101 2 0110010 ? 0111111 L 1001100 Y 1011001 f 1100110 s 1110011 0001100 [EM] 0011001 & 0100110 3 0110011 @ 1000000 M 1001101 Z 1011010 g 1100111 t 1110100 23

Another encoding example: Connectivity Informal problem statement: Given a ?-vertex graph ?, determine whether it is connected Formulating the problem as a language: Let ? 0,1?2 denote the adjacency matrix of ? Language: CONNECTED = ? ? is a connected graph 24

Multiple possible encodings OBJECTION: Why are we using adjacency matrices instead of adjacency lists? RESPONSE:It doesn t matter much which encoding we use, because it is not hard to convert between the two encodings 25

Encoding other things as strings General convention: If ? is any mathematical object that can be written down (a number, a graph, a polynomial, ), then we use the notation ? to denote some reasonable encoding of ? as a binary string It typically doesn t matter which specific encoding we use, provided we choose something reasonable If you are unsure how ? should be defined in a particular case, ask! 26

Invalid inputs Informal problem statement: Given a graph ?, determine whether it is connected The same problem, formulated as a language: CONNECTED = ? ? is a connected graph What if we are given ? 0,1 that is not the encoding of any graph? Suppose we want to decide CONNECTED A: This situation cannot occur B:It doesn t matter what we do If we are given ? where ? is a connected graph, we should accept C: We can accept or reject, but we must not loop D: We must reject If we are given ? where ? is a disconnected graph, we should reject Respond at PollEv.com/whoza or text whoza to 22333 27