TY - JOUR

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

AU - Косовский, Н.К.

AU - Косовская, Т.М.

PY - 2014

Y1 - 2014

N2 - Доказывается, что по всякой машине Тьюринга $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} расширя

AB - Доказывается, что по всякой машине Тьюринга $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} расширя

KW - машина Тьюринга

KW - РАМ программа

KW - РАСП программа

KW - проблема остановки алгоритма

KW - классы P

KW - FP

KW - P-SPACE

KW - FP-SPACE

KW - FLIN-SPACE

KW - FLIN-SPACE.

M3 - статья

VL - 1

SP - 368

EP - 376

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

SN - 1025-3106

IS - 3

ER -