|
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
Аннотация:
В этой короткой статье мы анализируем вычислительные алгоритмы, моделируемые машинами Черча, Тьюринга, Поста в сравнении с алгоритмами, которые используют время вычисления в вычислительных инструкциях. Мы замечаем, что существует некоторое существенное различие в поведении таких вычислений, и иллюстрируем это примерами. Мы рассматриваем работу машин Тьюринга на лентах фиксированной длины и также замечаем примечательное различие.
Ключевые слова:
вычисления, алгоритм, универсальные машины Черча–Тьюринга, время вычисления.
Получена: 18.09.2020 Исправленный вариант: 23.11.2020 Принята: 26.12.2020
Образец цитирования:
Vladimir V. Rybakov, “A note on computation MTs with time in instructions or with tapes of fixed length”, Журн. СФУ. Сер. Матем. и физ., 14:1 (2021), 69–73
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/jsfu892 https://www.mathnet.ru/rus/jsfu/v14/i1/p69
|
Статистика просмотров: |
Страница аннотации: | 110 | PDF полного текста: | 58 | Список литературы: | 21 |
|