1.Is the following a Turing machine? Please explain either how exactly to build

Question

1.Is the following a Turing machine? Please explain either how exactly to build it or precisely why it is not a Turing machine. M(n) = {halt if M (n) diverges diverge if M (n) halts} .5. Given the Turing machine Mi, consider the machine: M(x) ={M (i) if x is a blank diverge otherwise If x is blank, when does the machine accept? If x is not a blank, what does the machine accept? 6. Describe the reduction which took place in the last problem. Comment on the unsolvability of the blank tape halting problem. 8. Define the following problems as predicates or membership problems for sets and prove whether or not they are solvable. a) If an arbitrary Turing machine halts for all even numbers. b) Whether an arbitrary Turing machine has over 176 instructions. c) If you will get an A in the next computer course you take. 10. Explain precisely what is meant when we say that a Turing machine has entered an infinite loop. Prove that detecting this occurrence for arbitrary Turing machines is unsolvable.

Explanation / Answer

Formal definition Hopcroft and Ullman (1979, p. 148) formally defined a (one- tape) Turing machine as a 7- tuple where is a finite, non-empty set of states is a finite, non-empty set of the tape alphabet/symbols is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation) is the set of input symbols is the initial state is the set of final or accepting states. is a partial function called the transition function , where L is left shift, R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.) Anything that operates according to these specifications is a Turing machine.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.