Теорема о линейном ускорении - Linear speedup theorem

В теории сложности вычислений теорема о линейном ускорении для машин Тьюринга утверждает, что для любого действительного c> 0 и любой k- ленточной машины Тьюринга, решающей задачу за время f (n) , существует другая k- ленточная машина, которая решает ту же проблему в время не более f (n) / c + 2n + 3 , где k> 1 . Если исходная машина недетерминирована , то новая машина также недетерминирована. Конкретные константы 2 и 3 в 2n + 3 могут быть уменьшены, например, до n + 2 .

Доказательство

Конструкция основана на упаковку несколько магнитофонов символов оригинальной машины M в один символ ленты новой машины N . Это имеет тот же эффект, что и использование более длинных слов и команд в процессорах: ускоряет вычисления, но увеличивает размер машины. Сколько старых символов упаковано в новый, зависит от желаемого ускорения.

Предположим, новая машина упаковывает три старых символа в новый символ. Тогда алфавит новой машины : Он состоит из исходных символов и упакованных символов. В новой машине такое же количество лент k> 1 . Состояние N состоит из следующих компонентов: ${\ Displaystyle \ Sigma \ cup \ Sigma ^ {3}}$

• состояние `` М '';
• для каждой ленты: три упакованных символа, которые описывают упакованный символ под заголовком, упакованный символ слева и упакованный символ справа; и
• для каждой ленты: исходное положение головы в упакованном символ под головкой N .

Новая машина N начинается с кодирования данного ввода в новый алфавит (поэтому его алфавит должен включать ). Например, если вход для 2-ленты M находится слева, то после кодирования конфигурация ленты N будет справа: ${\ displaystyle \ Sigma}$

[#

_

а

б

б

а

б

б

а

_

...]

[#

(_, _, _)

(_, _, _)

(_, _, _)

...]

[#

_

_

_

_

_

_

_

_

_

...]

[#

(_, а, б)

(б, а, б)

(б, а, _)

...]

Новая машина упаковывает три старых символа (например, пустой символ _ , символ a и символ b ) в новый символ ( (_, a, b) ) и копирует его на вторую ленту, стирая при этом первую ленту. В конце инициализации новая машина направляет свою голову в начало. В целом это занимает 2n + 3 шага.

После инициализации состояние N равно , где символ означает, что он будет заполнен машиной позже; символ означает, что голова оригинальной машины указывает на первые символы внутри и . Теперь машина начинает моделировать m = 3 перехода M, используя шесть собственных переходов (в данном конкретном случае ускорения не будет, но в целом m может быть намного больше шести). Пусть конфигурации M и N следующие: ${\ displaystyle (q_ {0}; ~~~?, (\ _, \ _, \ _),?; ~~~?, (\ _, a, b),?; ~~~ [1,1 ])}$${\ displaystyle?}$${\ displaystyle [1,1]}$${\ Displaystyle (\ _, \ _, \ _)}$${\ Displaystyle (\ _, а, Ь)}$

[#

_

_

б

б

а

б

б

а

_

...]

[#

(_, а, б)

(б, а, б)

( b , _, _)

...]

[#

_

а

б

б

а

б

б

_

_

...]

[#

(_, _, б )

(б, а, б)

(б, а, _)

...]

где жирным шрифтом обозначено положение головы. Состояние N есть . Теперь происходит следующее: ${\ displaystyle (q; ~~~?, (\ _, \ _, b),?; ~~~?, (b, \ _, \ _),?; ~~~ [3,1])}$

• N перемещается вправо, влево, влево, вправо. После четырех ходов машина N полностью заполнена, и ее состояние становится ${\ displaystyle?}$${\ displaystyle (q; ~~~ \ #, (\ _, \ _, b), (b, a, b); ~~~ (b, a, b), (b, \ _, \ _) , (\ _, \ _, \ _); ~~~ [3,1])}$
• Теперь N обновляет свои символы и состояние в соответствии с m = 3 переходами исходной машины. Для этого может потребоваться два хода (обновить текущий символ и обновить один из соседних символов). Предположим, что исходная машина движется следующим образом (с соответствующей конфигурацией N справа):

[#

_

_

_

_

_

б

б

а

_

...]

[#

(_, а, б)

( b , _, _)

(_, _, _)

...]

[#

_

а

б

б

_

_

_

_

_

...]

[#

(_, _, _)

(_, _, б )

(б, а, _)

...]

Таким образом, состояние N становится . ${\ displaystyle (q '; ~~~?, (\ _, \ _, b),?; ~~~?, (b, \ _, \ _),?; ~~~ [3,1]) }$

Сложность

Инициализация требует 2n + 3 шагов. При моделировании 6 шагов N имитации м стадии М . Выбор m> 6c дает время работы . ${\ Displaystyle \ Leq е (п) / с + 2n + 3}$

Рекомендации