179 views
0 votes
0 votes
A $k$-head Turing machine has $k$ heads reading cells of one tape. A move of this $TM$ depends on the state and on the symbol scanned by each head. In one move, the $TM$ can change state, write a new symbol on the cell scanned by each head, and can move each head left, right, or keep it stationary. Since several heads may be scanning the same cell, we assume the heads are numbered $1$ through $k$, and the symbol written by the highest numbered head  scanning a given cell is the one that actually gets written there. Prove that the languages accepted by $k$-head Turing machines are the same as those accepted by ordinary $TM's$.

Please log in or register to answer this question.

Related questions