Оглавление [Скрыть]
Указательный станок
-
Определение и типы машин-указателей
- Машина-указатель – это атомистическая вычислительная машина с графом в качестве структуры памяти.
- Алгоритмы с указателями ограничены моделью машины-указателя.
- Существуют различные типы машин-указателей, включая связывающие автоматы, машины Колмогорова-Успенского и машины с древовидными указателями.
-
Структура и вычисления
- Машины-указатели не содержат арифметических инструкций, а вычисления основаны на чтении символов и изменении структуры памяти.
- Модель машины-указателя похожа на машину Тьюринга.
-
Модели машин-указателей
- Атомистические модели включают SMM, KUM и другие, отличающиеся от моделей высокого уровня.
- SMM – это машина с изменяемым ориентированным графом, в котором каждый узел имеет исходящую стрелку.
- KUM отличается обратимыми указателями и неориентированным графом.
-
Применение и параллельные вычисления
- Модель SMM используется для демонстрации алгоритмов, таких как целочисленное умножение.
- Гуревич задается вопросом о сходстве параллельной KU-машины с человеческим мозгом.
- Существуют параллельные модели машин-указателей, такие как предложенная Куком и Даймондом.
-
Дополнительные сведения
- В статье упоминаются другие типы вычислительных машин, такие как регистровые машины и машины с хранимой программой.
- Ссылки и библиография доступны в системе регистрации статей.
Полный текст статьи: