A model of computation：練習問題

A Turing machine transition function is represented as:
\(\delta(q_1, 0) = (q_2, 1, R)\)
Which of the following best describes the action of the machine when it is in state \(q_1\) and reads a '0' on the tape?

A Turing machine transition function is defined as: \(\delta(q_a, 1) = (q_b, 0, L)\). If the tape currently reads ...B 1 1 0 B... and the head is over the second '1' (from the left) in state \(q_a\), what will be the tape content and head position after this single transition?

A Turing machine is designed to increment a unary number (represented by a string of 1s). The head starts at the leftmost '1'. Which set of rules would effectively move the head to the right end of the string and append a '1' before halting?

Which of the following is a fundamental component of a Turing machine as defined in the AQA specification?

Which of the following represents the equivalence between a transition function and a state transition diagram for a Turing machine?

A Universal Turing Machine (UTM) is a fundamental model in computation. Explain how the UTM embodies the stored program concept.

A Turing machine transition function is given as \(\delta: Q \times \Sigma \rightarrow Q \times \Sigma \times \{L, R, S\}\). Explain the significance of the \(Q\) and \(\Sigma\) components in this formal model.

A Turing machine is defined to have a finite set of states. According to the specification, if a machine enters a state from which there are no outgoing transitions for the current tape symbol, what specific name is given to this type of state?

A Turing machine is defined by the following transition rules, where 'B' represents a blank space and the tape initially contains the string "11" followed by blanks. The machine starts in state \(S_0\) at the first '1'.

Rule 1: \((S_0, 1) → (S_0, 1, R)\)
Rule 2: \((S_0, B) → (S_1, 0, L)\)
Rule 3: \((S_1, 1) → (S_1, 1, L)\)
Rule 4: \((S_1, B) → (H_a, B, R)\)

Describe the final contents of the tape and the final position of the read-write head when the machine reaches the halting state \(H_a\).

In the context of A model of computation, the Halting Problem is a significant theoretical limit.

(a) Define what the Halting Problem is.
(b) Explain why the Halting Problem is described as undecidable.
(c) Describe the significance of the Halting Problem for the limits of what a computer can compute.