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!

No one has answered this question yet.

Answer this Question

Related Questions

Science 8 - IN science we are talking about chemical prefixes and compound names...
Math- Geometry Proofs - What are some ways to prove that a triange is isoscles? ...
Computer Questions - I posted some computer questions and my answers on Saturday...
Science - Hi, I have two questions about biology I need help with. 1) Some ...
RESEARCH REPORT - HI I WOULD LIKE TO KNOW WHAT I CAN POSSIBLY PROVE ABOUT EITHER...
Questions - Okay, so I'm doing this project on careers and I need pictures. ...
Science - Design a Turing Machine with One infinitely long tape containing 0, 1...
calc - i need to sketch a graph that satisfies all of these conditions: - it is ...
Modern History - Hi Guys! Okay sweet, here goes. I'm supposed to be keeping ...
probability - out of 250 students interviewed at a community college, 90 were ...

For Further Reading

First Name:
School Subject:
Answer: