Friday
October 24, 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:
Answer:

Related Questions

Science - Design a Turing Machine with One infinitely long tape containing 0, 1...
PHI 208 - Present three specific questions that you would ask in the Turing Test...
MATH - A company makes three products X, Y and Z. Each product requires ...
MATH- please help! - A company makes three products X, Y and Z. Each product ...
MATH-PLEASE HELPPP!!!! - A company makes three products X, Y and Z. Each product...
math- im really confused! please help!! - A company makes three products X, Y ...
Computer Science - In the program Turing, how would you move an box randomly ...
PHYICS - a turn table is turing at a rate of 45 rad/sec and comes to rest after ...
microeconomics - Sam Johnson started a small machine shop, Machines, Inc., in ...
computer science - Prove that the following language is not context free: L = {a...

Search
Members