A note on computation MTs with time in instructions or with tapes of fixed length
Vladimir V. Rybakovab
a A. P. Ershov Institute of Informatics Systems, Novosibirsk, Russian Federation
b Siberian Federal University Krasnoyarsk, Russian Federation
In this short note we analyze the computation algorithms modelled by Church–Turing–Post machines with algorithms for computation which use amount of time spent for computation (number of steps) in their own definitions. We notice some difference and illustrate that there are distinctions in behaviour of such algorithms; also we consider working of MTs on tapes of fixed length and observe again noticed difference.
computations, universal Church–Turing Machines, time of computation.
|Russian Foundation for Basic Research
|Ministry of Science and Higher Education of the Russian Federation
|Supported by RFBR and Krasnoyarsk Regional Fund of Science,
research project 18-41-240005; Supported by RFFI (-RFBR) and
Krasnoyarsk Regional Fund of Science, research project 18-41-240005; supported by the Krasnoyarsk Mathematical Centre and financed by the Ministry of Science and Higher Education of the Russian Federation (Grant no. 075-02-2020-1534/1).
PDF file (91 kB)
Received in revised form: 23.11.2020
Vladimir V. Rybakov, “A note on computation MTs with time in instructions or with tapes of fixed length”, J. Sib. Fed. Univ. Math. Phys., 14:1 (2021), 69–73
Citation in format AMSBIB
\paper A note on computation MTs with time in instructions or with tapes of fixed length
\jour J. Sib. Fed. Univ. Math. Phys.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|