Problem 1: Let M be any deterministic Turing machine which has exactly four states, q, p, s, and t, input alphabet {x, y}, and tape alphabet {x, y, 1}. Design another (multitape) Turing machine, U (a restricted version of the universal Turing machine) which will simulate one step of M , given M 's transition function. That is, M will start with the transition function of M , followed by a blank, followed by a configuration of M on its input tape. It will write the next configuration of M to its output tape. U will have the input and tape alphabet {q, p, s, t, x, y, 1, b, r, l} where q, p, s, and t will be used to represent the corresponding states of M, x, y, and 1 will represent M 's tape alphabet, b will stand for M 's blank, and l and r will stand for M 's L and R actions, respectively, in both the description of M 's transition function and configuration.
For example, if the input tape consists of "qb1qqxyqq1lppb1pp1lssb1sBqb" that means that M 's transition function is and its current configuration is in state q with the tape head pointing to a blank on a blank tape. The output should be the result of one step of M, that is, the output configuration is "q1". If the input configuration was "q1" the output would be "pB1". If the input configuration was "xq1" the output would be "px1".
(Since U 's tape alphabet contains all the states and tape symbols of M , there's no need to do any standardized encoding.)
Problem 2: Does an arbitrary deterministic Turing machine always accept some language? Does an arbitrary non-deterministic Turing machine always accept some language? Explain your answers.
Problem 3: Suppose that M is Turing machines that replaces its input by two copies of its input separated by a blank, and then calls the universal Turing machine U on the result, e.g., give the tape contents "aba" overwrites the tape with "abaBaba" and calls the U on the new contents. What happens when M is started on a tape which contains the description of M ?
Problem 4: What's the relationship between ( m + 1) % x and m % x among natural numbers? Write a primitive recursive function, mod, using the book's notation for computing m % x. Use only other functions that we have shown to be primitive recursive.
Problem 5: Show that the class of Turing-acceptable languages is closed under union. (Hint: This is a little trickier than it may seem, since the start state of a TM may have incoming edges.)
Turing Machines Assignment Help, Homework Help tutors are available 24x7 to secure top-notch grades.
Tags: Turing Machines Assignment Help, Turing Machines Homework Help, Turing Machines Coursework, Turing Machines Solved Assignments