Полная алгоритмическая доопределимость любых алгоритмов, работающих на ограниченной памяти

Аннотация

Доказывается, что по всякой машине Тьюринга M, использующей память, не превосходящую заданной конструируемой по памяти функции s от длины записи исходных данных n, можно построить применимую к любым исходным данным машину Тьюринга M1,являющуюся продолжением машины Тьюринга M. Теорема 1. Повсякой q-ленточной машине Тьюринга M, использующей память, не превосходящую заданной конструируемой по памяти функции s от длины записи исходных данных n, можно построить применимую к любым исходным данным q +1-ленточной машину Тьюринга M1, являющуюся продолжением машины Тьюринга M одной и той же произвольной наперёд заданной константой. Утверждение 1. Для каждого внешнего и внутреннего алфавита машины Тьюринга M память, используемая всюду применимой q +1-ленточной машиной M1, являющаяся продолжением q-ленточной машины M из условия теоремы, не превосходит линейной функции от размера памяти, используемой машиной M. Классы FP-SPACE и P-SPACE расширяются до классов pFP-SPACE и pP-SPACE соответственно, то есть до классов частичных (partial) функций и предикатов, вычисляемых на машине Тьюринга с памятью, не превосходящей полинома от длины записи исходных данных...

Ключевые слова:

машина Тьюринга, РАМ программа, РАСП программа, проблема остановки алгоритма, классы P, FP, P-SPACE, FP-SPACE, LIN-SPACE, FLIN-SPACE