Машина Минского
Машина Минского aka регистровая машина aka машина со счётчиками -- модель абстрактной машины, позволяющая реализовать любой алгоритм. Типа машины Тьюринга, но другая. Автор -- Марвин Минский -- попытался сделать её немного ближе к реальным компьютерам :) Сильно ближе, конечно не получилось.
Регистровая машина имеет конечное количество регистров R1, .., Rn каждый из которых может содержать произвольно большое натуральное число. Машина выполняет программу, состоящую из конечного числа инструкций снабжённых метками S1, .., Sm.
Инструкции бывают трёх типов:
В книжке "Вычисления и автоматы" Минский вводит эти машины немного иначе. Но приведённый мною вариант более лаконичен и удобен, а вычислительная равносильность очевидна.
Что с ними можно делать:
Задачка: смоделировать на машине Минского машину Тьюринга. Т.е. описать алгоритм, позволяющий по заданной машине Тьюринга построить машину Минского, выполняющую ту же задачу.
Задачка №2: то же самое, но использовать не более трёх регистров.
Задачка №3: то же самое, но использовать не более двух регистров. Хинт: не нужно пытаться использовать тот же подход, что и с тремя. Вместо этого попробуйте эмулировать трёхрегистровую (точнее, n-регистровую) ММ на двух регистрах. Т.е. предлагается найти такой способ хранения трёх чисел в одном, что с ними возможны независимые операции ++ и --, после чего задача сводится к предыдущей.
Регистровая машина имеет конечное количество регистров R1, .., Rn каждый из которых может содержать произвольно большое натуральное число. Машина выполняет программу, состоящую из конечного числа инструкций снабжённых метками S1, .., Sm.
Инструкции бывают трёх типов:
- Sk: Rl++; Si -- увеличить значение в регистре Rl на 1, перейти к команде с меткой Si
- Sk: Rl--; Si; Sj -- если в регистре Rl не 0, уменьшить его значение на 1 и перейти к команде с меткой Si, иначе перейти к команде с меткой Sj
- Sk: STOP -- конец работы
В книжке "Вычисления и автоматы" Минский вводит эти машины немного иначе. Но приведённый мною вариант более лаконичен и удобен, а вычислительная равносильность очевидна.
Что с ними можно делать:
- Сделать 0 в выбранном регистре.
Si-1: ...
Si: Rl--; Si; Si+1
Si+1: ... - Прибавить к одному регистру другой
Si-1: ...
Si: Rl--; Si+1; Si+2
Si+1: Rk++; Si
Si+2: ... - Но при этом мы потеряли значение в Rl. Чтобы его сохранить, нужно уже три регистра.
Si-1: ...
// сначала очистим Rt
Si: Rt--; Si; Si+1
// Теперь прибавим Rl к Rk и к Rt
Si+1: Rl--; Si+2; Si+4
Si+2: Rk++; Si+3
Si+3: Rt++; Si+1
// Здесь Rl == 0
// Теперь прибавим к Rl Rt
Si+4: Rt--; Si+5; Si+6
Si+5: Rl++; Si+4
Si+6: ...
Задачка: смоделировать на машине Минского машину Тьюринга. Т.е. описать алгоритм, позволяющий по заданной машине Тьюринга построить машину Минского, выполняющую ту же задачу.
Задачка №2: то же самое, но использовать не более трёх регистров.
Задачка №3: то же самое, но использовать не более двух регистров. Хинт: не нужно пытаться использовать тот же подход, что и с тремя. Вместо этого попробуйте эмулировать трёхрегистровую (точнее, n-регистровую) ММ на двух регистрах. Т.е. предлагается найти такой способ хранения трёх чисел в одном, что с ними возможны независимые операции ++ и --, после чего задача сводится к предыдущей.