Computer Science 3331A/B Study Guide - Midterm Guide: Turing Machine, Empty String

• School: Western University
• Department: Computer Science
• Course: Computer Science 3331A/B
• Professor: Lucian Ilie

Document Summary

We can construct a turing machine m which semidecides empty string, ab, and abab. We can also build a turing machine m1 that semidecides the complement of empty string, ab, and abab. This would show l1 to be decidable: not in sd. If < m, w> not-h : m does not halt on w, so m# rejects and oracle rejects. However, the above creates a contradiction, and so is not in sd: not in sd. R is a reduction from not-h which is defined as: If < m, w> not-h : m does not halt if it accepts nothing, oracle accepts. If < m, w> not-h: m halts on w and accepts as (ab)* is infinite, so oracle does not accept. Is finite, so refer to part 3 as they are equivalent: not in sd, sd. R is a reduction from h which is defined as: R() : construct the description of m#(x) that, on input x, operates as.