ITEC 420 2023fall ibarland

home—lectures—exams—hws—D2L—zoom (snow day)

Turing Machines
hw05

• Due 2022-Dec-01 (Fri) 23:59.
• Reading: §§17.1– 17.3, and §§17.6– 17.7.
• Please put your solutions in order and clearly label each with the problem number.
• Submit a .pdf, containing any pictures and handwritten work. You are welcome to try to keep the file-size small by providing the lowest-resolution images, so long as I can still read all the transitions.

Turing Machine instructions

• Use turingmachine.io to create your Turing Machines.
• I recommend saving your work periodically (pasting into a text-file). Some students have reported losing work by mis-clicking, in previous semesters.
• Your file should declare blank = '_'.
• Note: that site already uses the convention that the tape-head starts on the first (non-blank) character of the input (or which is blank if the input is empty).
• For a machine that computes a function, have your machine finish so with the read-head back on the first (non-blank) character of the result.
• For a decider, finishing in a state whose named accept (or, starts with the accept if you want multiple accept-states) to indicate acceptance. Finishing in any other state will be interpreted as rejecting the input. (The tape-contents are irrelevent.)
• As always, make sure that you correctly handle the empty-string as input.
• For each TM, submit on D2L a plain-text file named username-hw05-#i-tm.yaml (for example: ibarland-hw05-#3-tm.yaml). That file should be the contents of the text-pane of your machine on turingmachine.io. It should include:
  • Be sure to verify you can use turingmachine.io » Import » Choose Files to upload your file.
    (This is how I'll view your file. Be aware that the file is indentation-sensitive!)
  • Your username and problem# near the top, as well as this hw URL (www.radford.edu/itec420/2023fall-ibarland/Homeworks/hw05.html).
  • The URL https://turingmachine.io/?import-gist=ID (where the ID is numeric-only). Verify that the link works (even if you've logged out of github).
• If able, please save your file by creating a gist at gist.github.com. (Be sure you save the the file as found via turingmachine.io » Share » Copy to Clipboard; it includes your diagram-info in addition to the machine-instruction-file.)
• Feel free to use the duplicate-a-string example from lecture as an example/template, or pad aⁿbb^m (m ≤ n) to aⁿbⁿ , or look at that site's samples "palindrome" or "binary-increment".

1. Write a TM to compute function f where f(w) = wy$, w  ∈  {a,b}*, y  ∈  {_}*, and |y| = 2|w|.

   Note: This is similar to our example of duplicating a string (u to uu) except that the duplicated-bits are all spaces (and then followed by '$').

   Note: We use the fact that this machine exists in passing, in the Ch17b slides, writing a non-deterministic decider for composite numbers.

2. Write a Turing Machine to decide L={x-y=z : x,y,z ∈ 1*}.
   

   To clarify: The input alphabet for this language is Σ={-,=,1}, and (for example) 111-11111=1∈ L. (That is, are checking just the syntax of unary-subtraction.)

   note: This definition allows any/all of x,y,z can have zero 1s.

   yaml gotcha: You must include single-quotes around -. (However they are not needed for =.)

3. Write a Turing Machine to decide L = {x-y=z : x,y,z ∈ 1*, and |x| - |y| = |z|}.
   (That is, we verify semantics of unary-subtraction.)

   Note: Start with a copy of your answer to the previous problem. (Be sure to save that one first!)

   tip:

   If you are decrementing both x and y: Remove a 1 from y before finding a corresponding 1 in x. (That way, in case y has reached zero (ε), you don't need to go back to un-change a decrement to x.)

   Furthermore: My solution removed 1s from the right edge of y and z (but the left edge of x). I think this might help keep a solution slightly simpler?

   Note: My solution used 4 phases, and each phase had 4 states on average. (However, there is a solution with as few as 9 states.)

4. Suppose we have a deterministic TM M = (K,Σ,δ,s,Γ,{n,y}), and q₁≠s is one of the states in K
   (where as usual: n and y are reject and accept states respectively, ␣ indicates the blank/space character, and machine's read-head initially starts on the space preceding its input).

   Consider the logic formulas: (i) ∀ γ  ∈  Γ, δ(s,γ) = (q₁,γ,→), and (ii) ∀ k  ∈  K ∖ {s}, δ(k,␣) = (yes,␣,←)
   Recall that ∖ is set-subtraction, and γ is a lower-case gamma.

   1. In informal English, what does (i) say? (Your answer will be scored on both correctness and clarity/simplicity.)
   2. In informal English, what does (ii) say?
   3. Assuming (a) and (b) both hold, how does M procede, given the empty-string as input?
   4. Assuming (a) and (b) both hold, L(M) could not be the set of palindromes, nor the set of strings ending in a, nor {aⁿbⁿcⁿ}, but it could be (for all we know) {a*}. Explain.

      hint: How does a TM know if it's seen all the characters of its input?

5. based on textbook Exercises 20.7.5-6
   1. Explain why, if L₁ and L₂ are both decidable, then L₁ ∖ L₂ must also be decidable.
   2. Give languages L₁, L₂ such that L₁ is undecidable, L₂ is decidable, and L₁ ∖ L₂ is decidable.
   3. Give languages L₁, L₂ such that L₁ is undecidable, L₂ is decidable, and L₁ ∖ L₂ is undecidable.

   hint: Consider simple, “extreme” sets-of-strings, just like you consider extreme inputs when writing unit tests (e.g. for a function that takes in doubles, one might test 0.0 and Double.POSITIVE_INFINITY).

6. Rich, exercise 21.8.4 Show that H_ALL = {<M> : Turing machine M halts on all w  ∈  Σ^*} is not in D by reduction from HALT.

home—lectures—exams—hws—D2L—zoom (snow day)

This page licensed CC-BY 4.0 Ian Barland Page last generated

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu