Computer Science
posted by Yu .
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!
Respond to this Question
Similar Questions

Computer Science
In the program Turing, how would you move an box randomly around the screen. This is what I have so far: for row: 3..10 for column: 10..30 locate (row,column) put " ".. end for I think this creates a box. How would I move this box … 
microeconomics
Sam Johnson started a small machine shop, Machines, Inc., in his garage and incorporated it in March of 2002 as a calendaryear corporation. At that time, he began using his personal computer and tools solely for the business as part … 
MATH
A company makes three products X, Y and Z. Each product requires processing by three machines A, B and C. The time required to produce one unit of each product is shown below. Product X: Machine A: 1 Machine B: 2 Machine C: 2 Product … 
MATH please help!
A company makes three products X, Y and Z. Each product requires processing by three machines A, B and C. The time required to produce one unit of each product is shown below. Product X: Machine A: 1 Machine B: 2 Machine C: 2 Product … 
math im really confused! please help!!
A company makes three products X, Y and Z. Each product requires processing by three machines A, B and C. The time required to produce one unit of each product is shown below. Product X: Machine A: 1 Machine B: 2 Machine C: 2 Product … 
MATHPLEASE HELPPP!!!!
A company makes three products X, Y and Z. Each product requires processing by three machines A, B and C. The time required to produce one unit of each product is shown below. Product X: Machine A: 1 Machine B: 2 Machine C: 2 Product … 
Science
Design a Turing Machine with One infinitely long tape containing 0, 1, or blank The minimal number of states in its transition An input number written on the tape initially that computes the function of f(n)=nĂ—4 for any natural number … 
PHI 208
Present three specific questions that you would ask in the Turing Test to determine if something is real or artificial intelligence. 
PHYICS
a turn table is turing at a rate of 45 rad/sec and comes to rest after 5 second.how many rotation does it make before coming to rest? 
language arts
Can All Conflicts Be Resolved? In this discussion, you will post issues related to the relationships of humans and machines and the conflicts they involve. To support your ideas, refer to the texts in this lesson, other texts you have