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
Problem 1 What is conditional operator? Using conditional operator find a smallest number between two numbers Defining conditional operator Using it to find smallest n

Question 1 Briefly explain waveform Characteristics Question 2 Write a note on: types of Microphones Question 3 Briefly explain Magnetic Properties of Audiotape

E-R diagram and details for college management system

2. What benefits can a company gain by managing its own information infrastructure and services?

wrap that computes a customer water bill. The bill include Rs.100 water demand charge + a consumption charge of Rs.1.5 for every thousand gallons used. Consumption is figured from


1. In each of the following situations, indicate whether f = O(g), or f = O(g), or both (in which case f = T(g)). Briefly explain why. (a) f(n)=10n5 +8n2,g(n)=20n4 +7n3 +300 (b) f

#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

Question 1 What are the important Issues in Search Problem Question 2 What do you mean by Predicates? Briefly explain Question 3 What are the advantages of Wireles

Question 1 What is mobile telephone initialization? Explain the three main goals of this procedure Define GSM system operations Introduction to mobile telephone initializ