- Номер
- Журнал СФУ. Математика и физика. 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
Журнал СФУ. Математика и физика / Заметка о вычислениях на машинах Тьюринга со временем вычислений в машинных инструкциях или на лентах фиксированной длины
Полный текст (.pdf)