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

  1. 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 …
  2. microeconomics

    Sam Johnson started a small machine shop, Machines, Inc., in his garage and incorporated it in March of 2002 as a calendar-year corporation. At that time, he began using his personal computer and tools solely for the business as part …
  3. 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 …
  4. 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 …
  5. 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 …
  6. MATH-PLEASE 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 …
  7. 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 …
  8. PHI 208

    Present three specific questions that you would ask in the Turing Test to determine if something is real or artificial intelligence.
  9. 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?
  10. 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

More Similar Questions