What is the longest you might need to watch in order to draw

Assignment Help Computer Engineering

Reference no: EM131859368

Problem

Suppose you are given a Turing machine T (you have the transition diagram), and you are watching T processing an input string. At each step you can see the configuration of the TM: the state, the tape contents, and the tape head position.

a. Suppose that for some n, the tape head does not move past square n while you are watching. If the pattern continues, will you be able to conclude at some point that the TM is in an infinite loop? If so, what is the longest you might need to watch in order to draw this conclusion?

b. Suppose that in each move you observe, the tape head moves right. If the pattern continues, will you be able to conclude at some point that the TM is in an infinite loop? If so, what is the longest you might need to watch in order to draw this conclusion?

Reference no: EM131859368

Questions Cloud

What is integrated marketing communications : What is Integrated Marketing Communications and why is it so important in the 21st century for marketers to embrace this?

Possession with intent to distribute methamphetamine : He is arrested for possession with intent to distribute methamphetamine

Define the purpose of a strategic plan : In your own words, define the purpose of a strategic plan and explain the steps an organization goes through in developing one.

Crime-and-justice events by politicians : Discuss how criminal policy is debated and covered in the media noting how references to crime-and-justice events by politicians

What is the longest you might need to watch in order to draw : Will you be able to conclude at some point that the TM is in an infinite loop? If so, what is the longest you might need to watch in order to draw conclusion?

How is social media useful for marketing research : For these companies, how is social media useful for marketing research? What other companies and products might benefit from this approach? Why?

What level of burning is required to constitute arson : What level of burning is required to constitute arson? What levels of burning do not constitute arson?

What is the difference between a brand and a brand name : What is the difference between a brand and a brand name? What are some of the most famous brand names and why?

Describe how to construct a nondeterministic tm accepting l : Suppose T is a TM accepting a language L. Describe how to construct a nondeterministic TM accepting L*.

User Account

All Pages