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
what is the meaning of data definition

how to use excel..

what are the phases of oo progarmming or java?

Input Devices: i)  Keyboard is the most common form of input devices. It was originally designed in the last century. Since then, only minor improvements have taken place in k

They transfer the process flow, provisionally or totally, to a destiny, replicating this action until the counter is zero. LOOP LOOPE LOOPNE LOOP INSTRUCTION reason: To produce a c

The Python language has a lot of similarities to Perl, C and Java. Though, there are some specific differences between the languages. First Python Program: relative Mode Programmin

In this problem we will compare the performance of a vector processor with a system that contains a scalar processor and a GPU-based coprocessor. In the hybrid system, the host pr

100 animals and their respiratory organs

Process Control Management:   A  process  is an executing program. It is considered the standard unit of work within a computer system. Every executing program is treated as a

what is means with respect to software engineering?