Category: беларусь

Category was added automatically. Read all entries about "беларусь".

wall

Верхний пост

Всем привет.

Я мало френжу, простите.
У меня есть привычка читать всю ленту и ввязываться в дискуссии, из-за этого приходится держать количество друзей (особенно, активно пишуших друзей) в разумных пределах.

Я не пишу под замок. Сейчас "под глазиком" лежит n штук недописанных постов, под замком один пост с оффлайновыми контактами. И может быть ещё что-то случайное из давней древности.

Если хочется сказать что-то не по теме, это можно сделать тут.
Если что, писать можно на толстый-крокодил@yandex.ru -- как название журнала, но не подчёркивание а дефис.
wall

Машина Минского

Машина Минского aka регистровая машина aka машина со счётчиками -- модель абстрактной машины, позволяющая реализовать любой алгоритм. Типа машины Тьюринга, но другая. Автор -- Марвин Минский -- попытался сделать её немного ближе к реальным компьютерам :) Сильно ближе, конечно не получилось.

Регистровая машина имеет конечное количество регистров R1, .., Rn каждый из которых может содержать произвольно большое натуральное число. Машина выполняет программу, состоящую из конечного числа инструкций снабжённых метками S1, .., Sm.

Инструкции бывают трёх типов:
  • Sk: Rl++; Si -- увеличить значение в регистре Rl на 1, перейти к команде с меткой Si

  • Sk: Rl--; Si; Sj -- если в регистре Rl не 0, уменьшить его значение на 1 и перейти к команде с меткой Si, иначе перейти к команде с меткой Sj

  • Sk: STOP -- конец работы

(с) более-менее по первому слайду завтрашней лекции

В книжке "Вычисления и автоматы" Минский вводит эти машины немного иначе. Но приведённый мною вариант более лаконичен и удобен, а вычислительная равносильность очевидна.

Что с ними можно делать:

Collapse )

Задачка: смоделировать на машине Минского машину Тьюринга. Т.е. описать алгоритм, позволяющий по заданной машине Тьюринга построить машину Минского, выполняющую ту же задачу.

Задачка №2: то же самое, но использовать не более трёх регистров.

Задачка №3: то же самое, но использовать не более двух регистров. Хинт: не нужно пытаться использовать тот же подход, что и с тремя. Вместо этого попробуйте эмулировать трёхрегистровую (точнее, n-регистровую) ММ на двух регистрах. Т.е. предлагается найти такой способ хранения трёх чисел в одном, что с ними возможны независимые операции ++ и --, после чего задача сводится к предыдущей.