Доказывая, что машина Тьюринга M работает во времени $ o (2^{dn}) $

Question

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

Пусть $ M $ будет линейным пространством Тьюринга, состоящей из одной ленты. Мы говорим, что $ m $-это машина с линейным пространством, если M останавливается на каждом входе, и если есть константы $ C $ и $ n_ {0} $, что для всех входов $ x in sigma^{ ast} $ of Length $ n geq n_ {0} $, $ m $, работающие на $ x $, посещают максимум $ c cdot n $ ленточные квадраты.

Докажите, что для некоторых постоянных $ d $, $ m $ запускается во времени $ o (2^{dn}) $.

У меня есть пара идей с самого начала. Во -первых, моя интуиция говорит мне, что мне просто нужно построить алгоритм, который работает в соответствии с этими правилами и принимает/отклоняет во времени $ O (2^{dn}) $. Во -вторых, есть подсказка, которая говорит мне «рассмотреть количество конфигураций», однако, я не уверен, как это включить.

Спасибо заранее за любую помощь.

Answer 1

Ваша интуиция проблематична, по следующей причине: вам дают конкретную машину $ M $, а не язык. Поэтому, если вы опишите алгоритм, который работает в $ O (2^{dn}) $ и решит тот же язык, вы фактически докажите, что $ l (m) $ является решающим в $ O (2^{dn}) $, Но это не означает, что $ m $ сам запускается в этот период.

Как следует из подсказка, рассмотрите количество возможных конфигураций $ M $: Напомним, что конфигурация TM состоит из содержимого ленты, положения головы и состояния. Учитывая, что алфавит машины фиксирован, и что лента, используемая в районе $ m $ на $ x $, имеет размер $ c cdot | x | $, попробуйте связать количество возможных конфигураций (выраженные в размер $ m $ и $ | x | $)

Теперь помните, что $ M $ всегда останавливается. Что это значит в последовательности конфигураций, которые он проходит в своем запуске на $ x $?

Сочетая эти два наблюдения, вы получите ответ. Комментарий, если вам нужно больше намеков.