ACtE07 · Chapter 7Programming & Applications🏛️ Past Licensure QuestionID: 2fde2edb
In the standard definition of a single-tape Turing Machine, which of the following atomic tape head operations cannot be performed in a single step?
In the standard definition of a single-tape Turing Machine, which of the following atomic tape head operations cannot be performed in a single step?
Multiple Choice Options
- A
Overwriting a symbol on the current cell
- B
Moving the read/write head left or right
- C✓ Correct Option
Splicing/inserting a new cell between two existing tape cells
- D
Reading the symbol under the current head
Detailed Technical Solution & Explanation
A standard Turing machine operates on a fixed 1D tape grid indexed by integers. In a single atomic step, it reads a symbol, overwrites it with a symbol, and moves left or right. It cannot 'insert' or 'splice' a brand new cell between two adjacent tape cells in a single transition—insertion requires shifting all downstream cells cell-by-cell.
Option Analysis:
•
Option A (Overwriting a symbol on the current cell): A fundamental atomic primitive ().
•
Option B (Moving the read/write head left or right): Standard tape head motion ( or ).
•
Option C (Splicing/inserting a new cell between...): Correct. Standard tape geometry is rigid; inserting an extra cell requires an algorithm to shift all subsequent cells.
•
Option D (Reading the symbol under the current ...): Standard sensory input of the transition function.
Reference: Mock Test 07NEC Licensure Syllabus