Total algorithmic extension of an algorithm running on the bounded space

Abstract

It is proved that for every Turing machine M using space not greater than a done space constructible function s of the input data length n there exists a Turing machine M1 which is a total extension of M. Theorem 1. For every q-tape Turing machine M using space not greater than a done space constructible function s of the input data length n there exists a q-tape Turing machine M1 which is a total extension of M by means of a fixed constant. Proposition 1. For every exterior and interior alphabet of a Turing machine M the space used by a total q + 1-tape Turing machine M1 from theorem 1 is not greater than a linear function of the space used by the Turing machine M. Classes FP-SPACE and P-SPACE are extended up to the classes pFP-SPACE and pP-SPACE respectively, i.e. up to the classes of all partial functions and predicates computable by a Turing machine with the space not greater than a polynomial under the input data length. Proposition 3. For every function from pFP-SPACE its stop problem belongs to P-SPACE. Nevertheless the following theorem is valid. Theorem 3. Let a Turing machine from the class pP-SPACE M and a word X be input data for the following problem. The problem of applicability of M to X does not belong to the class P-SPACE. The following theorem uses the fact that a RAM-program transforms nonnegative integers in binary notation. Theorem 4. Every partial RAM-program P with logarithmic space bounded by a done space constructible function s of the input data length n may be extended by means of a fixed constant up to a total RAM-program P1 with logarithmic space bounded by a linear function of s(n). Coefficients of such a linear function depend of the parameters of the program P. The analogous assertion according a RASP-program is a corollary of this theorem. Refs 5.

Keywords:

Turing machine, RAM program, RASP program, stop-problem, classes P, FP, P-SPACE, FP-SPACE, LIN-SPACE, FLIN-SPACE