Turing Machine in cui il passaggio successivo è determinato dallo stato e dai simboli fino alla testa di lettura/scrittura

Question

Dato un tipo di macchina per la rotazione modificata in cui

$ Delta = Q Times Gamma^* implica Q Times Gamma Times {L, R } $

dove il passo successivo della macchina è determinato dallo stato attuale e qualunque cosa sia scritta sul nastro fino al punto corrente.

Ad esempio: se il contenuto del nastro è $ a _ab _ $ $ $ a $, e la testa è a sinistra $, quindi il passaggio successivo è determinato dallo stato e dalla parola $ a _ab _ $$.

1. Come posso dimostrare che i linguaggi non riconosciuti possono essere riconosciuti con questi tipi di macchine?
2. Quelle macchine contraddicono la tesi della chiesa e della durata?