Архив публикаций

Тезисы

XIX-ая конференция

Комбинаторная абстрактная машина как модель аппликативного вычислителя

Мажирин И.В.

КИФФ, Россия, 121151, Москва, Кутузовский пр. 24/1, +74957291442, allo10@yandex.ru

Как известно, по схеме машины Тьюринга построены все массово используемые на сегодняшний день архитектуры компьютеров. Машина Тьюринга является расширением модели конечного автомата, абстрактной моделью некоего вычислителя, который за конечное число выполненных команд должен достигнуть результата, т. е. выполнить некий алгоритм: перейти из одного дискретного состояния в другое (остановиться). Предлагается к рассмотрению модифицированная машина Тьюринга - комбинаторная абстрактная машина для редукции (экспансии) комбинаторных термов в выбранном комбинаторном базисе {K, S}. Существенным отличием предлагаемой схемы машины является наличие (по определению) сильной взаимосвязи между ячейками ленты: аппликации. Ячейки апплицированы друг к другу. Т. е. символы из конечного алфавита машины A, B, C, D, записанные в ячейках ленты, будут взаимосвязаны между собой аппликацией «•» по ассоциации влево.

A B C D = A•B•C•D = (((AB)C)D) = ABCD. (1)

Как известно, большинство современных массово используемых компьютеров имеют архитектуру Фон-Неймана и построены на основе машины Тьюринга и состоят из трех основных компонентов: память, процессор и канал обмена между ними. В памяти находятся слова выполняемой программы. Очередное слово выбирается из памяти, передается в процессор и там выполняется. Затем, результат из процессора передается по каналу обмена обратно в память. Т. о. имеем проблему «Горлышка бутылки Фон-Неймана». Элементарная операция: «Сложение». Основная задача: выполнение арифметических задач. Скорость исчисляется количеством операций с плавающей точкой в секунду.

При использовании в архитектуре компьютеров аппликативного вычислителя с комбинаторным базисом {K, S} исчезает проблема «Горлышка бутылки Фон-Неймана», т. к. при редукции результат из процессора не передается обратно в память. Элементарная операция: «Аппликация». Основная задача: обработка символьной информации и логический вывод. Скорость может быть выражена количеством аппликаций в секунду.

• открыть в PDF формате (на русском языке) (PDF)