Абстрактная модель машины Тьюринга

Абстрактная модель машины Тьюринга

• МТ =

МТ =

Машина Тьюринга состоит из трех частей: ленты, считывающе-записывающей головки и логического устройства

• Машина Тьюринга состоит из трех частей: ленты, считывающе-записывающей головки и логического устройства

• Лента выступает в качестве внешней памяти; она считается неограниченной (бесконечной)

Головка неподвижна, а лента передвигается относительно нее вправо или влево.

• Головка неподвижна, а лента передвигается относительно нее вправо или влево.
• Машина работает в некотором произвольном конечном алфавите
• A = {ε a1…a n} – этот алфавит называется внешним.
• В нем выделяется специальный символ – ε, называемый пустым – его посылка в какую-либо ячейку стирает тот символ, который до этого там находился, и оставляет ячейку пустой.