Question

A Turing machine with stay put instead of left is similar to an ordinary Turing machine,...

A Turing machine with stay put instead of left is similar to an ordinary Turing machine, but the transition function has the form

δ: Q×Γ→ Q×Γ×{R,S}

At each point, the machine can move its head right or let it stay in the same position. Show that this Turing machine variant is not equivalent to the usual version. What class of languages do these machines recognize?

Homework Answers

Answer #1

It is easy to see that we can simulate any DFA on a Turing machine with stay put instead of left. The only non-trivial modification is to add transitions from the state in F to qaccept Upon reading a blank, and from states outside F to qreject Upon reading a blank.

Next, we start with a Turing machine M = (Q, Σ, Γ, δ, q0, qaccept, qreject) with stay put instead of left, and show how we can construct a DFA (Q', Σ' , δ', q' 0 , F) that recognizes the same language. The intuition here is that M cannot move left and cannot read anything it has written on the tape as soon as it moves right, and therefore it has essentially only one-way access to its input, much like a DFA

First, we modify M as follows; note that these changes do not affect the language it recognizes.

  • Add a new symbol so that M never writes blanks on the tape; instead, M writes the new symbol when it’s going to write blanks, and we extend the transition function so that upon reading this new symbol, it behaves as though it read a blank.
  • When M transitions into qreject or qaccept, the reading head moves right (and never stays put).

Set Q' = Q, Σ' = Σ, q '0 = q0, and consider the transition function:

(for q ∈ Q and σ ∈ Σ). Observe that there are finitely many state-alphabet pairs, M either ends up either staying put and looping, or eventually moves right, and thus δ 0 is well-defined. Finally, we define F to be the set containing qaccept and all states q ∈ Q, q ≠ qaccept, qreject such that M starting at q and reading blanks, eventually enters qaccept.

so these machines only recognize regular languages.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Design a FSM for a Vending Machine In this task, you will design a FSM for...
Design a FSM for a Vending Machine In this task, you will design a FSM for a simple (albeit strange) vending machine of office supplies. The vending machine sells three possible items, each at a different cost: Item Cost Pencil 10 cents Eraser 20 cents Pen 30 cents The vending machines accepts nickels (worth 5 cents), dimes (worth 10 cents), and quarters (worth 25 cents). Physically, it is only possible to insert a single coin at a time. The vending...
Sign In INNOVATION Deep Change: How Operational Innovation Can Transform Your Company by Michael Hammer From...
Sign In INNOVATION Deep Change: How Operational Innovation Can Transform Your Company by Michael Hammer From the April 2004 Issue Save Share 8.95 In 1991, Progressive Insurance, an automobile insurer based in Mayfield Village, Ohio, had approximately $1.3 billion in sales. By 2002, that figure had grown to $9.5 billion. What fashionable strategies did Progressive employ to achieve sevenfold growth in just over a decade? Was it positioned in a high-growth industry? Hardly. Auto insurance is a mature, 100-year-old industry...
Please answer the following Case analysis questions 1-How is New Balance performing compared to its primary...
Please answer the following Case analysis questions 1-How is New Balance performing compared to its primary rivals? How will the acquisition of Reebok by Adidas impact the structure of the athletic shoe industry? Is this likely to be favorable or unfavorable for New Balance? 2- What issues does New Balance management need to address? 3-What recommendations would you make to New Balance Management? What does New Balance need to do to continue to be successful? Should management continue to invest...
What tools could AA leaders have used to increase their awareness of internal and external issues?...
What tools could AA leaders have used to increase their awareness of internal and external issues? ???ALASKA AIRLINES: NAVIGATING CHANGE In the autumn of 2007, Alaska Airlines executives adjourned at the end of a long and stressful day in the midst of a multi-day strategic planning session. Most headed outside to relax, unwind and enjoy a bonfire on the shore of Semiahmoo Spit, outside the meeting venue in Blaine, a seaport town in northwest Washington state. Meanwhile, several members of...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT