Ученик Алана Тьюринга Робин Ганди утверждал, что Чарльз Бэббидж не имел понятия об универсальной вычислительной машине?

10

Робин Ганди был учеником Алана Тьюринга .

Ганди сделал анализ Аналитического двигателя Бэббиджа (см. «Ганди - Слияние идей в 1936 году», цитируемый в «Херкен, Рольф - Универсальная машина Тьюринга - Обследование за полвека . Springer Verlag») - и сказал, что это сделал (ср. стр. 52–53):

  1. Арифметические функции +, -, ×, где - указывают «правильное» вычитание x - y = 0, если y ≥ x.
  2. Любая последовательность операций является операцией.
  3. Итерация операции (повторение n раз операции P).
  4. Условная итерация (повторение n раз операции P при условии «успеха» теста T).
  5. Условный перевод (т. Е. Условный переход).

Затем он заявляет

функции, которые можно вычислить с помощью (1), (2) и (4), являются в точности теми, которые вычислимы по Тьюрингу.

(стр. 53).

Затем он заявляет:

… Акцент делается на программировании фиксированной итерируемой последовательности арифметических операций. Фундаментальное значение условной итерации и условного переноса для общей теории вычислительных машин не признается…

Ганди р. 55

Я оцениваю объем претензий Ганди здесь. (Правильно это или нет). Похоже, он заявляет, что хотя Бэббидж, похоже, натолкнулся на понятие полноты Тьюринга (может выразить любую программу, используя (1), (2) и (4) - у него не было понятия вычислимой функции . (Возможно, Ганди говорил, что поскольку работа Бэббиджа была до работы Гильберта и Годеля , у него не было математических инструментов, чтобы связать определение универсальной вычислительной машины.)

Мой вопрос: утверждал ли ученик Алана Тьюринга Робин Ганди, что Чарльз Бэббидж не имел понятия об универсальной вычислительной машине?

Hawkeye
источник
2
Примечание есть также история науки и математика stackexchange hsm.stackexchange.com
усул
Я немного смущен ссылками на страницу. Если бы все номера страниц принадлежали Ганди, возможно, было бы более понятно сказать «(Ганди, с. 52-53)», (Ганди, с. 53) «и (Ганди, с. 55)». Для любых отрывков, которые цитируются в Rolf, атрибуция может быть расширена как (Gandy, p. 5x; как указано в Rolf, p. Xx) ". " Cf. " - сокращение от латинского confer / conferatur (" сравнить "), что означает «иди и посмотри еще эту вещь для сравнения или противопоставления», так что не имеет смысла говорить это за то, что ты цитируешь.
Джейкоб С. говорит: «Восстановите Монику

Ответы:

22

Нет, наоборот. Эта цитата Гэнди относится не к Бэббиджу, а к некоторым промежуточным предложениям по универсальным вычислениям между Бэббиджем и Тьюрингом. Гэнди говорит, что в этих предложениях не было признания Бэббиджа важности ветвления и итерации для универсальных вычислений.


В «Слиянии идей в 1936 году» Ганди, напечатанном в книге «Универсальная машина Тьюринга - обзор за полвека», раздел 2 - «Бэббидж и его последователи».

Здесь Гэнди подчеркивает, что Бэббидж понимал и уважал «условную итерацию» и «условный перенос», например, конец p53 и начало p54.

Хотя Бэббидж упоминает об условном переносе (67-68), он, с естественным уважением к хорошо структурированному программированию, использует только условную итерацию [....]. Он заявляет об условном переносе явным образом (240), позволяя инструкции «перейти к» возможно, придется казнить, звоня в колокольчик, чтобы вызвать служителя; он приводит пример его использования (241).

(Здесь Ганди ссылается на статью Менабреа 1842 года о двигателе Бэббиджа, но, похоже, приписывает идеи самому Бэббиджу.)

Ганди тогда цитирует Бэббиджа

Что все развитие и операции анализа теперь могут быть выполнены с помощью машин.

и пишет

Бэббидж в своей работе по общей алгебре и функциональным уравнениям показал свою способность мыслить абстрактно. Если бы тогда кто-то заставил его рассуждать (не сложно!) О том, что можно сделать с абстрактной машиной, свободной от ограничений на ее хранение, он, несомненно, согласился бы с версией (основанной на разделах 2.1. (1) - (5)) тезиса Черча.

Затем Ганди переходит к разделу 2.3 «Последующие разработки». Он написал

Другие авторы, занимающиеся более практичными машинами, ссылались на работы Бэббиджа. Примеры из Рэнделла 1982 года: М. О'Канье [1922], Л. Каффиньял [1933], В. Буш 1936, Х.Х. Айкен 11964] (который является неопубликованным меморандумом 1937 года). Но основной упор делается на программирование фиксированной итерируемой последовательности арифметических операций. Фундаментальное значение условной итерации и условного переноса для общей теории вычислительных машин не признается, хотя принципы могут использоваться в очень специфических контекстах [....]

Наконец, Ганди пишет:

Выводы. Бэббидж утверждал, что, по сути, была версия тезиса Черча. Его работы никогда не были полностью забыты, но его теоретическое значение - его, так сказать, важность как программного обеспечения - было мало признано [....]

усул
источник