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

Н.К. Косовский, Т.М. Косовская

Research output

Abstract

Доказывается, что по всякой машине Тьюринга $M$, использующей память, не превосходящую заданной конструируемой по памяти функции $s$ от длины записи исходных данных $n$, можно построить применимую к любым исходным данным машину Тьюринга $M_1$, являющуюся продолжением машины Тьюринга $M$. {\bf Теорема 1.} {\it По всякой $q$-ленточной машине Тьюринга $M$, использующей память, не превосходящую заданной конструируемой по памяти функции $s$ от длины записи исходных данных $n$, можно построить применимую к любым исходным данным $q+1$-ленточной машину Тьюринга $M_1$, являющуюся продолжением машины Тьюринга $M$ одной и той же произвольной наперёд заданной константой.} {\bf Утверждение 1.} {\it Для каждого внешнего и внутреннего алфавита машины Тьюринга $M$ память, используемая всюду применимой $q+1$-ленточной машиной $M_1$, являющаяся продолжением $q$-ленточной машины $M$ из условия теоремы, не превосходит линейной функции от размера памяти, используемой машиной $M$.} Классы {\bf FP-SPACE} и {\bf P-SPACE} расширя
Original languageRussian
Pages (from-to)368-376
JournalВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ
Volume1
Issue number3
Publication statusPublished - 2014

Cite this