Тип публикации: статья из журнала
Год издания: 2021
Идентификатор DOI: 10.17516/1997-1397-2021-14-1-69-73
Ключевые слова: computations, universal church-turing machines, time of computation, вычисления, алгоритм, универсальные машины черча-тьюринга, время вычисления
Аннотация: 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 consiПоказать полностьюder working of MTs on tapes of fixed length and observe again noticed difference. В этой короткой статье мы анализируем вычислительные алгоритмы, моделируемыемашинами Черча, Тьюринга, Поста в сравнении с алгоритмами, которые используют время вычисления в вычислительных инструкциях. Мы замечаем, что существует некоторое существенноеразличие в поведении таких вычислений, и иллюстрируем это примерами. Мы рассматриваем работу машин Тьюринга на лентах фиксированной длины и также замечаем примечательное различие 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. © Siberian Federal University. All rights reserved.
Журнал: Журнал Сибирского федерального университета. Серия: Математика и физика
Выпуск журнала: Т.14, №1
Номера страниц: 69-73
ISSN журнала: 19971397
Место издания: Красноярск
Издатель: Сибирский федеральный университет