• Site Map

• Lectures

• Homework

• Tests/Exam

• Main Webpage

Homework Assignment 1

Due: by 2pm on Web 1 Oct
Worth: 8%

For each question, please write up detailed answers carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

1. In dyadic notation, integers are represented in base 2 using the digits 1 and 2 (instead of 0 and 1). For example, the integer 13 is represented by the dyadic string "221" because 13 = 2*4 + 2*2 + 1. Dyadic notation has one interesting property: each integer has a unique representation, because there cannot be any leading digits. This is unlike binary notation, where each integer has infinitely many representations (for example, each of the infinitely many binary strings "1101", "01101", "001101", "0001101", ... represents the same integer 13). In particular, note that the integer 0 is represented by the empty string (ε) in dyadic notation.

   Give a decider for language

   SORTED = { [a₁, a₂, ..., a_n] : n ∈ N, a_i ∈ {1,2}* for 1 ≤ i ≤ n and a₁ ≤ a₂ ≤ ... ≤ a_n using dyadic notation }.

   To be clear, the input alphabet for your TM will consist of the symbols '[', ']', ',', '1', '2', and your TM should accept all strings that represent a non-decreasing list of integers, rejecting all other strings (those that represent lists not sorted in non-decreasing order, and those that do not represent lists).

   For example, "[]" ∈ SORTED (it represents the empty list, which is vacuously sorted) and "[,]" ∈ SORTED (it represents the sorted list [0,0]), but "[1,]" ∉ SORTED (it represents the unsorted list [1,0]) and ",,][" ∉ SORTED (it doesn't even represent a list).

   Give a high-level description (the main idea in one paragraph), an implementation-level description (a numbered list that describes details of head movements and tape contents, but does not mention states), and a formal-level description (full transition table or transition diagram, as well as an explicit list of the tape alphabet) of your TM. Make sure to relate your formal-level description to the equivalent stages in the implementation-level description.

2. A partial function is one that may be undefined for certain values in its domain. For example, over the real numbers, 1/(x-2) is undefined at x = 2 and x^1/2 is undefined for all x < 0, but x² is defined everywhere.

   "Partial Function Computers" (PFCs) are similar to TMs except that they are used to compute partial functions rather than to recognize languages. More precisely, PFCs have only one halting state q_H (instead of the two halting states q_A, q_R), and we say that a PFC C computes the partial function f : Σ* → Σ* if C has the following behaviour, when started in initial configuration "_ q₀ w" (for any string w ∈ Σ*): if f(w) is defined, then C's computation eventually terminates (in state q_H) with f(w) writen on its tape; if f(w) is undefined, then C's computation never terminates. A partial function is "computable" if there is some PFC that computes it.

   Prove that for all partial functions f : Σ* → Σ*, f is computable (according to the definition above) if and only if the language

   L_f = { w#f(w) : w ∈ Σ* and f(w) is defined }

   is recognizable (where # ∉ Σ).

3. A "double-scan" Turing machine (DSTM) is similar to a regular TM, except that the head always reads and writes two squares at a time, and always moves two squares at a time. Formally, the transition function of a DSTM takes input in Q-{q_A,q_R} × Γ² and produces output in Q × Γ² × {L,R}, where 'L' means "move two squares to the left" and 'R' means "move two squares to the right" — as for a regular TM, the head does not move if the TM attemps to move left while scanning the two leftmost squares.

   Prove or disprove that DSTMs are equivalent to TMs. Give detailed implementation-level descriptions in your answer.

4. Consider the function f : {1}* → {1}* defined as follows.

   f(x) = ε   if x occurs as a string of consecutive digits somewhere in the decimal expansion of π;
   f(x) = 1^k   if x does not occur anywhere in the decimal expansion of π, where 1^k is the longest string of consecutive 1's that occurs anywhere in the decimal expansion of π.

   For example, suppose 1111 = 1⁴ is the longest string of consecutive 1's that occurs anywhere in the decimal expansion of π (i.e., the decimal expansion of π does not contain five 1's in a row anywhere). Then, f(ε) = f(1) = f(11) = f(111) = f(1111) = ε and f(1⁵) = f(1⁶) = ... = 1111.

   Show that f is computable (using the definition of "computable" given in class for total functions). Give both implementation-level and formal-level descriptions in your answer.

   Hints: You cannot assume that π contains every possible finite sequence of digits (this is a conjecture, not a known fact). And although an argument can be made that there exists a TM that computes successive digits in the decimal expansion of π, you do not need this fact in order to answer the question. Think of the possible values that the function can have, and reduce the question to the computation of a different function with the same values — consider breaking down your answer into various cases.