Пример обобщения концепции машины Тьюринга

Актуальность темы
1936г. Тьюринг
МТ абстрактное вычислительное устройство для мат. модели описания алгоритмов
1936г. Черч
Любой процесс, который естественным образом мог бы быть назван процедурой, реализуем МТ. В этом смысле МТ считается эквивалентом любого ВУ
2005г. 40 лет закону Мура
Число транзисторов на одной интегральной микросхеме удваивается каждые 18 мес.
Через несколько лет размер элементарной ячейки компьютера составит 100-200 ангстрем
Новый вид носителей информации требует новых математических оснований

Существующие подходы
Создание “СБИС” по все более высокоскоростной технологии
Использование квантовых компьютеров для быстрого решения сложных задач с данными большой размерности

Классическая МТ
MT =
Программа для пары
однозначно задает
Алгоритм работы: в любой момент времени
если машина останавливается, иначе выбираем
и полагаем

Нестандартная МТ
НМТ =
Структура НМТ расширена двумя компонентами:
- множество задания программы (где
- множество всевозможных наборов )
т.е. ,причем и
- оператор эволюции состояний и памяти
Алгоритм работы: в любой момент времени
если , то машина останавливается;
если , то происходит “естественная” эволюция
если ,то в работу машины вмешивается внешнее воздействие:
Здесь – время необходимое для перевода состояния и памяти машины из .

Набор моделей
Пусть – это множество НМТ (набор моделей), т.е. каждая ячейка памяти представляет собой отдельное устройство
Изменение состояния памяти может происходить непрерывно и параллельно во всех ячейках
Такая система позволяет переосмыслить понятие “такт”, момент достижения определенного множества

Алгоритм решения диофантова уравнения

Результаты моделирования
X-20=0
T=86
X+20=0
T=50