Означает ли принятие, что ТМ будет читать и распознавать символ из ячейки, с которой он в данный момент читает? И это тот случай, когда ТМ останавливается, если вход разрешим?
terminology
turing-machines
undecidability
sdfasdgasg
источник
источник
Ответы:
Принятие и отклонение состояния, в которое может в конечном итоге войти машина Тьюринга, основано на строке, считанной с ленты, а не только на символе из одной ячейки. Конечно, решение о вводе принимающей или отклоняющей ленты в конечном итоге принимается на основе одного символа.
Машина Тьюринга может либо в конечном итоге войти в принимающее состояние, либо в отклоненное состояние, либо выполнить цикл навсегда. Если он входит в состояние принятия или отклонения, он останавливается.
Говорят, что машина Тьюринга является полной, если она останавливается на всех входах.
Язык, принимаемый машиной Тьюринга, представляет собой набор всех слов, которые, будучи предоставлены в качестве входных данных для машины Тьюринга, приводят к тому, что машина Тьюринга переходит в состояние принятия.
Язык считается разрешимым тогда и только тогда, когда существует полная машина Тьюринга, которая будет принимать язык.
источник