Turing machine where the next step is determined by the state and the symbols up to the read/write head
-
05-11-2019 - |
質問
Given a modified type of turning machine where
$\delta = Q\times \Gamma^* \implies Q\times \Gamma \times \{L,R\}$
where the next step of the machine is determined by the current state and whatever written on the tape up to the current point.
For example: if the tape content is $a\_ab\_\$\$a$, and the head is on the left \$, then the next step is determined by the state and the word $a\_ab\_\$$.
- How can I prove that unrecognized languages can be recognized with these types of machines?
- Do those machines contradict the Church–Turing thesis?
正しい解決策はありません
所属していません cs.stackexchange