Журнал СФУ. Математика и физика / Заметка о вычислениях на машинах Тьюринга со временем вычислений в машинных инструкциях или на лентах фиксированной длины

Полный текст (.pdf)
Номер
Журнал СФУ. Математика и физика. 2021 14 (1)
Авторы
Рыбаков, Владимир В.
Контактная информация
Рыбаков, Владимир В.: Сибирский федеральный университет Красноярск, Российская Федерация; Институт систем информатики им. А. П. Ершова Новосибирск, Российская Федерация
Ключевые слова
computations; universal Church-Turing Machines; time of computation; вычисления; алгоритм; универсальные машины Черча-Тьюринга; время вычисления
Аннотация

В этой короткой статье мы анализируем вычислительные алгоритмы, моделируемые машинами Черча, Тьюринга, Поста в сравнении с алгоритмами, которые используют время вычисления в вычислительных инструкциях. Мы замечаем, что существует некоторое существенное различие в поведении таких вычислений, и иллюстрируем это примерами. Мы рассматриваем работу машин Тьюринга на лентах фиксированной длины и также замечаем примечательное различие

Страницы
69–73
DOI
10.17516/1997-1397-2021-14-1-69-73
Статья в архиве электронных ресурсов СФУ
https://elib.sfu-kras.ru/handle/2311/137825