Theory of computation, computer science, Basic Computer Science

I define a restricted form of TMs M as follows. Given any input x on the tape of M, the initial portion of the tape that holds x is read-only and one-way. That is, M cannot write on input x, and M cannot move back (to the left) on input x. But beyond this portion of x, M works as a normal TM. What kind of languages can be accepted by this restricted form of TMs? Is the emptiness (i.e., whether a given TM in the restricted form accepts a non-empty language) is decidable? Prove it.
Posted Date: 2/19/2012 10:58:46 PM | Location : United States







Related Discussions:- Theory of computation, computer science, Assignment Help, Ask Question on Theory of computation, computer science, Get Answer, Expert's Help, Theory of computation, computer science Discussions

Write discussion on Theory of computation, computer science
Your posts are moderated
Related Questions
Opening files 0FH function is used to open an FCB file the 21H interruption. The element, the name and extension of the file must be initialized previous to opening it. The DX regi

Indexing a page on internet: Once, the spiders have completed the task of finding information about Web pages, the search engine must store the information in such way that yo

write a basic program for f= a+b+c//2

a cloth merchant A cloth showroom has announced the following seasonal discounts on purchase of items: Purchase amount Discount Mill items Handloom items 0-100 - 5% 101-200 5% 7.5%

Question 1 Explain with an example the three kinds of relationships that are most important in object oriented modeling Question 2 Describe the Common Modeling techniques in

Discuss the factors considered during output design

what is the computer science

Computer Storage: Computer systems include two types of digital information storage: internal storage, within the CPU, and the backing (back up) storage on external devices su

Question 1 Explain the basic structure of a C program with an example 2 What would be the value of x after execution of the following statements? 3.What are the commonly u

QUESTION (a) Give the representation of a queue as an abstract data type. (b) What is a priority queue? Give two types of priority queues. (c) The following program does