Прямая редукция, машина Тьюринга и DFA

Question

Я читал, и я пытаюсь понять сокращение, когда речь заходит об истинной машине. Вот как я это понимаю: это означает, что это превращает проблему А в проблему С. Но я не совсем уверен, как она полностью работает. давайте посмотрим на пример:

Учитывая язык L:

L ={<M,D>| M is s TM and D is a DFA so that L(M) = L(D)}, 

используя сокращение, как доказать Atm < L.

Мое решение:

M - это машина Тьюринга, которая принимает любую строку и останавливается на этой строке. D является DFA, если принимает язык L и его эквивалент для TM M. Atm - это TM, M, который принимает строку w.

Как вы можете доказать, используя прямое сокращение, которое Atm < L??

Answer 1

Нам нужно показать, что решатель для L может использоваться для определения экземпляров Atm, то есть решатель для L может использоваться для ответа на вопрос "принимает ли данный TM заданную входную строку?"

Учитывая экземпляр <M, w> Атм, нам нужно превратить его в экземпляр <M', D> этой проблемы, так что решение этой проблемы ответит другой.

Во-первых, построить M' чтобы L(M') = L(M) intersect {w}, Это можно сделать следующим образом. Создайте TM, который сканирует входную ленту и гарантирует, что w это вход. Если w не вход, остановка-отклонение. В противном случае вернитесь к передней части ленты и перейдите в прежнее начальное состояние M, Затем беги M как обычно. Очевидно, что это может только принять w, поскольку мы отвергли все остальное; и если M принимает w, это будет также, так как после начального этапа M работает нормально.

Во-вторых, построить D чтобы L(D) = {w}, это DFA буду иметь |w| + 2 состояния: начальное состояние, мертвое состояние и одно состояние на символ в w,

Теперь используйте наш решатель для L в случае <M', D>, Он будет остановлен, если и только если L(M') = L(D) = {w}, что возможно только если L(M) intersect {w} = {w} который, в свою очередь, удовлетворен только если L(M) содержит w, Так что, если мы остановимся и примем, то у нас есть ответ на наш случай <M, w> Атм.