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

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

Результат исследований: Научные публикации в периодических изданияхстатья

Аннотация

Доказывается, что по всякой машине Тьюринга $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} расширя
Язык оригиналарусский
Страницы (с-по)368-376
ЖурналВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ
Том1
Номер выпуска3
СостояниеОпубликовано - 2014

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

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

Цитировать