Комментарии 6
Самая простая доказано универсальная машина Тьюринга - это Wolfram's 2-state 3-symbol Turing machine. Интересно, насколько сложно выглядела бы симуляция процессора на ней и какое было бы сравнительное быстродействие? И какие есть возможности для симуляции на ленте ограниченной длины? (может быть, на какой-нибудь замкнутой кольцевой ленте?). По идее, это было бы универсальное вычислительное устройство, на основе самых простых принципов (проще уже быть не может).
Интересно, что получится ...
Очень интересная статья.
Не знаю, но возможно машина могла бы быть сильно понятнее и быстрее, если бы количество состяний раздуть в 2^bitDepth раз.
Так, например, вместо хождения туда-сюда и вычитания 1 из адреса при поиске ячейке с заданным индексом, можно было бы создать состояние "иди вправо K раз, и потом выполняй вот ту команду". Переходы там — перейти вправо один раз и попасть в состяние с K-1 или перейти в состояние для следующего действия.
Рассматривали ли вы такой вариант? Или это противоречит философии независимости от битности в дизайне машины?
Это не противоречит философии, поскольку такие состояния можно было бы сгенерировать один раз при инициализации заданным числом бит, но хотелось получить МТ с как можно меньшим числом как состояний, так и алфавитом. Впрочем, её всё ещё можно сократить в некоторых местах.
Введение дополнительных состояний для переходов на k позиций несомненно ускорило бы работу с памятью и командами переходов. Если опустить переходы, то можно оправдывать принятое решение тем, что операции с памятью медленные в реальных процессорах, но это несерьёзно.
Если делать полноценный аналог x86, в котором только байты, то да, это было бы отличным решением. Если однажды решусь на такое, думаю, использую Вашу идею, спасибо!
Вопрос: может ли это, в теории, быть адаптировано под архитектуру декатронной МЭВМ конструкции т-ща Кашканова? Насколько я понял, сама по себе его конструкция предельно приближена к машине Тьюринга, и такой эксперимент по «совмещению двух миров» мог бы быть интересным (абсолютно непрактичным, но, всё же...). Если это, конечно, возможно.
Симулятор x86 подобного процессора на машине Тьюринга