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
How to make a stale marriage program by implementing the Gale Shapley algorithm using Java program

Question 1 Explain the following system design tools in detail System Flowcharts Decision tables Decision trees Organization charts Question 2 Write s

Question 1 What is difference between cathode ray tube monitors and LCD monitors? List three popular types of operating systems and give brief introduction of each type Que

#queA register is a memory location surrounded by the CPU itself, designed to be rapidly accessed for purposes of fast data retrieval. Processors normally hold a register array, wh

Problem 1. Explain the different categories of instructions. Explanation of 4 categories 2. Explain the steps to be followed for the addition of floating point numb

ryby db fgrh herbgh buyh hehg gvo hb bbithbs bgshbshdgbh bubfvhb bs v h hjjg jdk jnmnv j

What is new? ERP, on the other hand begins with a fresh relook at the existing business. In fact it is the result of a happy marriage between Business Process Reengineering (BP


akrenda club has just opened their jym and pools services. They need a system that can keep record of total sales of each. The club has silver and gold members. The silver members

Using only the digits 1-6 how many five digit numbers can be formed? How many of these have at least a 5? How many of them have either no 5 or no 6?