Post a New Question

Computer Science

posted by .

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

First Name
School Subject
Your Answer

Similar Questions

More Related Questions

Post a New Question