АЛЕКСЕЙ ВТОРНИКОВ, ведущий программист, ЗАО КБ «Ростовский Универсальный», pdp8dec@gmail.com
Странная формула Часть 4. Абак – простейший вычислитель
Все, о чем мы говорили в первых трех теоретических частях цикла, само по себе и интересно, и важно, но настало время спуститься с небес на землю и перейти к практике. И начнем мы с рассмотрения очень простого компьютера
Шедевр – это убожество, доведенное до совершенства.
Борис Кригер
Постановка задачи
Мы хотим реализовать вычисление максимально возможного количества математических функций (хотелось бы всех, но это, увы, невыполнимо, т.к. еще в 1936 году А. Черч дал пример алгоритмически неразрешимой функции, в дальнейшем аналогичные результаты были получены П.С.Новиковым и другими математиками). К таким функциям относятся сложение, вычитание, умножение и т.д.
Казалось бы, в чем проблема? Берем любой из языков программирования, чуточку поколдуем, и задача решена. Все верно, но нам нужен простейший из возможных инструментов, а не современные языки с их развитыми типами данных, мощной поддержкой и инфраструктурой. Проще говоря, нам необходим более деликатный зонд, позволяющий «заглянуть» внутрь происходящего, внутрь того, как вычисления выполняются: нам нужно тщательно разобраться в самых элементарных актах, составляющих понятие «вычисление».
Вообще под понятием «вычисление» мы будем подразумевать не просто набор арифметических операций, а способ получения значения функции (всюду или частично определенной).
Функция вычислима, если существует алгоритм, предписание, позволяющее за конечное время (пусть даже очень большое, но главное – конечное) получить значение функции при заданных аргументах, входящих в ее область определения.
Скажем, программа, реализующая функцию сложения двух чисел, отработает быстро, а вот программа, реализующая функцию разложения большого числа на простые множители (т.н. проблема факторизации), может работать много-много лет. Это не строгое определение, но нам достаточно и такого.
Современные языки (точнее, те, кто их реализовал) тщательно прячут свою внутреннюю «кухню», и вследствие этого подавляющее большинство программистов смутно представляют себе, что именно лежит в основе, казалось бы, хорошо знакомых процессов; как ни странно, математики осведомлены об этом лучше. В этом, в общем-то, нет ничего страшного (и в обычных условиях совершенно оправдано), но для наших целей этот способ, увы, не подходит.
Для этого мы введем очень простой компьютер, реализуем для него интерпретатор и попробуем составить несколько программ. В качестве языка реализации интерпретатора мы выбрали Java (версии 1.7 и выше). Назовем компьютер «абаком» (от лат. abacus – древнеримское устройство для облегчения арифметических расчетов, аналог известных бухгалтерских русских счетов с костяшками, нанизанными на спицы).
Статью целиком читайте в журнале «Системный администратор», №5 за 2014 г. на страницах 76-81.
Facebook
Мой мир
Вконтакте
Одноклассники
Google+
|