April 23, 2014

Homework Help: Computer Science

Posted by Yu on Saturday, December 8, 2012 at 11:51pm.

I need some help about Turing Machines, and prove by reductions.

Here are the 2 questions:

1. Sketch the construction of a Turing Machine that decides the language
L = a^i where i is not prime.

2. Show that the language 2Strings is not recursive by reducing any one of the two lan-
guages Member or Halt, to 2Strings.

2Strings = a language with at least 2 distinct strings
Halt = {<M,w> | M halts on input w}


Any help would be greatly appreciated!

Answer this Question

First Name:
School Subject:

Related Questions

Computer - How much was the first computer? Cost of the first computer? You have...
Science - Design a Turing Machine with One infinitely long tape containing 0, 1...
Science - I need a Title to my research paper, my topic is about ...
probability - out of 250 students interviewed at a community college, 90 were ...
grammar - Diagram the simple subject and the simple predicate of each sentence. ...
science - name some of the simple machines!!!
computer services - I need help to find more information about the computer ...
Computer Science - In the program Turing, how would you move an box randomly ...
science - So I have to do this project on simple machines. The invention we need...
science please help - So I have to do this project on simple machines. The ...