COSC 517 Models of Computation Assignment

Assignment Help Theory of Computation

Reference no: EM132454721

COSC 517 Models of Computation - Ducane University

Question 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 <q, B, 1, q> <q, x, y, q> <q, 1, L, p> <p, B, 1, p> <p, 1, L, s> <s, B, 1, s> 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.)

Question 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.

Question 3. Suppose that M is a Turing machine 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 ?

Question 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.

Question 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.)

Reference no: EM132454721

Questions Cloud

Describe the basic elements of a project life cycle : Describe the basic elements of a project life cycle. Why is an understanding of the life cycle relevant for our understanding of projects?

Discussing possible evidence of gods existence : Discussing possible evidence of God's existence, which philosopher makes the best, or strongest argument for or against the existence of God

Define the lowest observed adverse effect level : Define the lowest observed adverse effect level (LOAEL) and the no observed adverse effect level (NOAEL), and describe how they relate to the point of departure

Project - Current Issues in Accounting, Auditing, or Tax : Project - Current Issues in Accounting, Auditing, or Tax. Provide an overview of the topic that you are researching. Present the current status of the topic

COSC 517 Models of Computation Assignment : COSC 517 Models of Computation Assignment Help and Solution, Ducane University - Assessment Writing Service - Show that the class of Turing-acceptable languages

What are tips to successfully write a good paper : What are tips to successfully write a good paper, at the university level?

Develop that specific athlete : The course is Sports Conditioning. For your course paper you will be training a specific athlete. For this assignment, you will develop that specific athlete.

Did the country adopt IFRS or did they make changes : Choose a country that has already adopted IFRS. Did the country adopt IFRS or did they make changes to IFRS to adapt to their country's culture or regulations

Heilbrunn timeine of art history : Select and abstract work of art from this weeks reading from the Heilbrunn Timeine of Art History website or any reputable art museum

User Account

All Pages