Может ли более мощная вычислительная машина (машина Тьюринга) не решить проблему, которую можно решить с помощью менее мощной машины в иерархии Хомского - PullRequest
Новая
       60

Может ли более мощная вычислительная машина (машина Тьюринга) не решить проблему, которую можно решить с помощью менее мощной машины в иерархии Хомского

1 голос
/ 22 января 2020

Для набора входных алфавитов (a, b), скажем, язык L определяется как «Набор всех строк длины 2016 года».

так,

Первый сценарий: Конечные автоматы могут четко решить, находится ли какой-либо ввод данных над входными алфавитами (a, b), в L или нет, принимая или отклоняя его ИЛИ другими словами, он может решить, что длина входной строки равна 2016 или нет ?

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

Но, к сожалению, прошли годы, но машина Тьюринга не останавливается, то есть - "она впала в бесконечность oop для этого произвольного ввода".

Меня очень смущает тот факт, что почему даже будучи более мощным, чем конечные автоматы, машина Тьюринга не может решить, что решили конечные автоматы

Отредактировано:

Пример: L = ({M} | M - машина Тьюринга, которая принимает строка длина 2015)

мы знаем, что если мы увидим приведенный выше пример через призму обычного языка, то язык длины 2015 будет конечным и, следовательно, регулярным.

Но язык L для машины Тьюринга М неразрешимо и рекурсивно перечислимо.

это более или менее мое замешательство

1 Ответ

1 голос
/ 23 января 2020

Машины Тьюринга могут определять членство на любом обычном языке. Я думаю, что вы путаетесь в том, что TM может l oop навсегда, и, конечно, многие TM делают это, а также многие другие, которые также не выбирают какой-либо конкретный язык. Тем не менее, гарантированно будет ТМ, который решит любой обычный язык L:

  • примите DFA для L;
  • запишите ввод на ленте;
  • переход через DFA на основе символов, считанных с ленты слева направо;
  • halt-accept, если заканчивается в состоянии принятия;
  • halt-reject в противном случае
...