1. **Problem 7a: Define the minimization (µ) operator and its use in µ-recursive functions.** The minimization operator $ \mu $ applied to a function $ f(k, x_1, \ldots, x_n) $ finds the smallest $ k $ such that $ f(k, x_1, \ldots, x_n) = 0 $, if such $ k $ exists. Formally: $$ \mu k [f(k, x_1, \ldots, x_n) = 0] = \text{the least } k \text{ with } f(k, x_1, \ldots, x_n) = 0 $$ If no such $ k $ exists, the function is undefined (partial). This operator extends primitive recursive functions (which are total) to partial functions, creating the class of $ \mu $-recursive (partial recursive) functions. 2. **Problem 7b: Construct a specific $ \mu $-recursive function $ F(e) $ whose domain is codes of Turing machines halting on input 0.** Define $ F(e) = \mu k [T(e, 0, k) = 1] $, where $ T(e, x, k) $ is a primitive recursive predicate that simulates the Turing machine encoded by $ e $ on input $ x $ for $ k $ steps and returns 1 if it halts within $ k $ steps, else 0. Construction steps: - Use primitive recursive functions to encode Turing machine steps. - Define $ T(e, 0, k) $ to check halting within $ k $ steps. - Apply minimization $ \mu k $ to find the halting time. 3. **Problem 7c: Explain why $ F $ is partial and its domain illustrates the link between $ \mu $-recursive functions and recursively enumerable sets.** $ F(e) $ is partial because if the machine $ e $ does not halt on input 0, $ \mu k $ never finds a $ k $ with $ T(e, 0, k) = 1 $, so $ F(e) $ is undefined. The domain of $ F $ is exactly the set of codes of Turing machines halting on 0, which is recursively enumerable but not recursive. Thus, $ \mu $-recursive functions correspond to partial functions whose domains are recursively enumerable sets. --- 4. **Problem 8a: Construct a recursively enumerable but not recursive language $ L $.** Define $ L = \{ e \mid \text{Turing machine encoded by } e \text{ halts on input } 0 \} $. This language contains exactly the codes of Turing machines that halt on input 0. 5. **Problem 8b: Prove $ L $ is recursively enumerable by describing a Turing machine recognizing $ L $.** Construct a Turing machine $ M $ that on input $ e $: - Simulates the machine encoded by $ e $ on input 0 step-by-step. - If the simulation halts, $ M $ accepts $ e $. Since $ M $ accepts exactly those $ e $ where the machine halts, $ L $ is recursively enumerable. 6. **Problem 8c: Prove $ L $ is not recursive and interpret the result.** If $ L $ were recursive, its complement $ \overline{L} $ (machines that do not halt on 0) would also be recursively enumerable. But $ \overline{L} $ is not recursively enumerable (Halting problem is undecidable). Hence, $ L $ is not recursive. Interpretation: The halting problem is semi-decidable; we can recognize halting machines but cannot decide halting for all machines. --- 7. **Problem 9: Choose Algorithm A (DFA Simulation on an Input String).** **a) Pseudocode and input size:** Input: DFA $ M = (Q, \Sigma, \delta, q_0, F) $, string $ w = a_1 a_2 \ldots a_n $ Pseudocode: 1. Set current state $ q := q_0 $ 2. For $ i = 1 $ to $ n $: - Set $ q := \delta(q, a_i) $ 3. If $ q \in F $, accept; else reject. Input size parameter $ n $ is the length of the input string. **b) Running time analysis:** - Each step processes one symbol and updates state in constant time. - Total steps: $ n $ **c) Big-O notation and efficiency:** Running time is $ O(n) $, linear in input size. This is efficient and practical for string recognition by DFAs.