Характеристики алгоритмов - Algorithm characterizations

Характеристики алгоритмов - это попытки формализовать алгоритм слова . Алгоритм не имеет общепринятого формального определения. Исследователи активно работают над этой проблемой. В этой статье более подробно будут представлены некоторые «характеристики» понятия «алгоритм».

Проблема определения

За последние 200 лет определение алгоритма стало более сложным и подробным, поскольку исследователи пытались определить этот термин. В самом деле, может быть более одного типа «алгоритма». Но большинство согласны с тем, что алгоритм имеет какое-то отношение к определению обобщенных процессов для создания «выходных» целых чисел из других «входных» целых чисел - «входных параметров» произвольных и бесконечных по протяженности или ограниченных по протяженности, но все же изменчивых - путем манипулирования различимые символы (подсчет чисел) с конечным набором правил, которые человек может выполнять с бумагой и карандашом.

Наиболее распространенными схемами манипулирования числами - как в формальной математике, так и в повседневной жизни - являются: (1) рекурсивные функции, вычисляемые человеком с помощью бумаги и карандаша, и (2) машина Тьюринга или ее эквиваленты - примитивный регистр. модель машины или «контр-машины», модель машины с произвольным доступом (RAM), модель машины с хранимой программой с произвольным доступом (RASP) и ее функциональный эквивалент « компьютер ».

Когда мы делаем «арифметику», мы на самом деле вычисляем, используя «рекурсивные функции» в сокращенных алгоритмах, которые мы изучили в начальной школе, например, сложение и вычитание.

Доказательства того, что каждую «рекурсивную функцию», которую мы можем вычислить вручную, мы можем вычислить машиной, и наоборот - обратите внимание на использование слов « вычислить» по сравнению с « вычислить», - замечательны. Но эта эквивалентность вместе с тезисом (недоказанным утверждением) о том, что сюда входят все вычисления / вычисления, указывает на то, почему так много внимания было уделено использованию машин, эквивалентных Тьюрингу, при определении конкретных алгоритмов и почему определение самого «алгоритма» часто ссылается на « машину Тьюринга ». Это обсуждается более подробно в описании Стивена Клини .

Ниже приводится краткое изложение наиболее известных характеристик (Клини, Марков, Кнут) вместе с теми, которые вводят новые элементы - элементы, которые дополнительно расширяют определение или способствуют более точному определению.

[ Математическую задачу и ее результат можно рассматривать как две точки в пространстве, а решение состоит из последовательности шагов или пути, связывающего их. Качество решения зависит от пути. Для пути может быть определено несколько атрибутов, например длина, сложность формы, простота обобщения, сложность и так далее . ]

Иерархия Хомского

Существует больше консенсуса относительно «характеристики» понятия «простой алгоритм».

Все алгоритмы должны быть описаны на формальном языке, а «понятие простоты» возникает из простоты языка. Иерархия Хомского (1956) является сдерживание иерархии классов формальных грамматик , порождающих формальные языки . Он используется для классификации из языков программирования и абстрактных машин .

С точки зрения иерархии Хомского , если алгоритм может быть определен на более простом языке (чем неограниченный), он может быть охарактеризован таким языком, иначе это будет типичный «неограниченный алгоритм».

Примеры: макроязык «общего назначения», такой как M4, не ограничен ( полный по Тьюрингу ), а макроязык препроцессора C - нет, поэтому любой алгоритм, выраженный в препроцессоре C, является «простым алгоритмом».

См. Также Отношения между классами сложности .

Особенности хорошего алгоритма

Ниже приведены особенности хорошего алгоритма;

• Точность: хороший алгоритм должен иметь определенные намеченные шаги. Шаги должны быть достаточно точными и не меняющимися.

• Уникальность: каждый шаг, сделанный в алгоритме, должен давать определенный результат, заявленный автором алгоритма. Результаты ни в коем случае не должны колебаться.
• Осуществимость: алгоритм должен быть возможным и практичным в реальной жизни. Он не должен быть абстрактным или воображаемым.
• Вход: хороший алгоритм должен уметь принимать набор определенных входных данных.
• Выходные данные: хороший алгоритм должен давать результаты на выходе, предпочтительно решения.
• Конечность: алгоритм должен останавливаться после определенного количества инструкций.
• Общность: алгоритм должен применяться к набору определенных входов.

1881 г. Отрицательная реакция Джона Венна на логическую машину У. Стэнли Джевонса 1870 г.

В начале 1870 года У. Стэнли Джевонс представил «Логическую машину» (Jevons 1880: 200) для анализа силлогизма или другой логической формы, например, аргумента, сведенного к булеву уравнению . Посредством того, что Кутура (1914) называл «своего рода логическим пианино [,] ... равенства, которые представляют предпосылки ...," проигрываются "на клавиатуре, как на пишущей машинке ... Когда все предпосылки были "воспроизведены", панель показывает только те составляющие, сумма которых равна 1, то есть ... его логическое целое. Этот механический метод имеет преимущество перед геометрическим методом Венна ... "(Couturat 1914: 75).

Со своей стороны, Джон Венн , логик, современник Джевонса, был менее чем взволнован, полагая, что «мне не кажется, что какие-либо устройства, известные в настоящее время или которые могут быть обнаружены, действительно заслуживают названия логических машин» (курсив добавлен, Венн 1881: 120). Но исторически полезное значение для развивающегося понятия «алгоритм» имеет его объяснение его негативной реакции по отношению к машине, которая «может служить действительно ценной цели, позволяя нам избежать неизбежного труда»:

(1) «Это, во-первых, изложение наших данных точным логическим языком»,

(2) «Затем, во-вторых, мы должны придать этим утверждениям форму, пригодную для работы двигателя - в данном случае приведение каждого предложения к его элементарным отрицаниям»,

(3) «В-третьих, происходит объединение или дальнейшая обработка наших помещений после такого сокращения»,

(4) «Наконец, результаты должны интерпретироваться или считываться. Последнее обычно дает много возможностей для развития навыков и проницательности».

Он заключает, что «Я не вижу, чтобы какая-либо машина могла надеяться помочь нам, кроме как на третьем из этих шагов; поэтому очень сомнительно, что что-то в этом роде действительно заслуживает названия логической машины» (Venn 1881: 119 –121).

1943, 1952 Характеристика Стивена Клини

Этот раздел длиннее и более подробен, чем другие, из-за его важности для темы: Клини был первым, кто предложил, что все вычисления / вычисления - любого вида, совокупность - могут быть эквивалентно (i) вычислены с использованием пяти ». примитивные рекурсивные операторы "плюс один специальный оператор, называемый мю-оператором , или (ii) вычисляться посредством действий машины Тьюринга или эквивалентной модели.

Кроме того, он полагал, что любой из них будет служить определением алгоритма .

Читатель, впервые столкнувшийся с последующими словами, вполне может запутаться, поэтому краткое объяснение будет уместным. Вычисления выполняются вручную, вычисления выполняются машиной Тьюринга (или ее эквивалентом). (Иногда автор оговаривается и меняет местами слова). «Функцию» можно рассматривать как «поле ввода-вывода», в которое человек помещает натуральные числа, называемые «аргументами» или «параметрами» (но только счетные числа, включая 0 - неотрицательные целые числа), и получает одно неотрицательное число. целое число (условно называется «ответ»). Думайте о «функциональном блоке» как о маленьком человечке, который либо вычисляет вручную, используя «общую рекурсию», либо вычисляет машину Тьюринга (или эквивалентную машину).

«Эффективно вычислимый / вычислимый» является более общим и означает «вычислимый / вычислимый некоторой процедурой, методом, техникой… чем угодно…». «Общая рекурсия» была способом Клини написать то, что сегодня называют просто «рекурсией»; однако «примитивная рекурсия» - вычисление с использованием пяти рекурсивных операторов - представляет собой меньшую форму рекурсии, в которой отсутствует доступ к шестому, дополнительному, мю-оператору, который требуется только в редких случаях. Таким образом, большая часть жизни требует только «примитивных рекурсивных функций».

1943 г. "Тезис I", 1952 г. "Тезис Чёрча"

В 1943 году Клини выдвинул то, что стало известно как тезис Черча :

« Тезис I. Каждая эффективно вычислимая функция (эффективно разрешимый предикат) является общерекурсивной» (впервые высказано Клини в 1943 году (перепечатанная страница 274 в Дэвисе, изд. Неразрешимая ; также дословно появляется в Kleene (1952), стр. 300))

В двух словах: для вычисления любой функции единственные операции, которые нужны человеку (технически, формально), - это 6 примитивных операторов «общей» рекурсии (в настоящее время называемые операторами рекурсивных функций mu ).

Первое заявление Клини об этом было под заголовком раздела « 12. Алгоритмические теории ». Позже он расширит это в своем тексте (1952) следующим образом:

«Тезис I и его обратное дают точное определение понятия процедуры или алгоритма вычисления (решения) для случая функции (предиката) натуральных чисел» (стр. 301, жирный шрифт добавлен для выделения)

(Его использование слов «решение» и «предикат» расширяет понятие вычислимости до более общих манипуляций с символами, таких как математические «доказательства».)

Это не так страшно, как может показаться - «общая» рекурсия - это всего лишь способ выполнения наших повседневных арифметических операций из пяти «операторов» примитивных рекурсивных функций вместе с дополнительным оператором mu по мере необходимости. Действительно, Клини приводит 13 примеров примитивных рекурсивных функций, а Булос – Берджесс – Джеффри добавляет еще несколько, большинство из которых будут знакомы читателю - например, сложение, вычитание, умножение и деление, возведение в степень, функция CASE, конкатенация и т. Д. так далее.; список см. в разделе Некоторые общие примитивно-рекурсивные функции .

Почему общерекурсивные функции, а не примитивно-рекурсивные?

Kleene et al. (см. §55 Общие рекурсивные функции, стр. 270 в Клини, 1952) пришлось добавить шестой оператор рекурсии, названный оператором минимизации (записанный как μ-оператор или mu-оператор ), потому что Аккерманн (1925) произвел чрезвычайно растущую функцию - функцию Аккермана. функция - и Рожа Петер (1935) разработал общий метод создания рекурсивных функций с использованием диагонального аргумента Кантора , ни один из которых не может быть описан пятью операторами примитивно-рекурсивной функции. Что касается функции Аккермана:

«... в определенном смысле длина алгоритма вычисления рекурсивной функции, которая также не является примитивной рекурсивной, растет с аргументами быстрее, чем значение любой примитивной рекурсивной функции» (Клини (1935) перепечатал стр. 246 в The Нерешимо , плюс сноска 13 о необходимости дополнительного оператора, выделена жирным шрифтом).

Но необходимость в мю-операторе - большая редкость. Как указано выше в списке общих вычислений Клини, человек живет своей жизнью, счастливо вычисляя примитивные рекурсивные функции, не опасаясь столкнуться с чудовищными числами, созданными функцией Аккермана (например, супер-возведение в степень ).

1952 "Диссертация Тьюринга"

Тезис Тьюринга выдвигает гипотезу о вычислимости «всех вычислимых функций» с помощью модели машины Тьюринга и ее эквивалентов.

Чтобы сделать это эффективным образом, Клини расширил понятие «вычислимый», расширив сеть - включив в понятие «функции» как «полные функции», так и «частичные функции». Полная функция является тот , который определен для всех натуральных чисел (положительные целые числа , включающие 0). Частичная функция определена для некоторых натуральных чисел, но не для всех - спецификация «некоторые» должна идти «впереди». Таким образом, включение «частичной функции» расширяет понятие функции на «менее совершенные» функции. Общие и частичные функции могут быть вычислены вручную или на машине.

Примеры:

«Функции»: включают «обычное вычитание m  -  n » и «сложение m  +  n ».

«Частичная функция»: «Обычное вычитание» m  -  n не определено, когда в качестве входных допускаются только натуральные числа (положительные целые числа и ноль) - например, 6-7 не определено.

Итоговая функция: «Сложение» m  +  n определено для всех положительных целых чисел и нуля.

Теперь рассмотрим определение «вычислимого», данное Клини в формальном смысле:

Определение: «Частичная функция φ вычислима , если существует машина M, которая ее вычисляет» (Клини (1952) стр. 360)

«Определение 2.5. N- мерная функция f ( x ₁ , ..., x _n ) частично вычислима, если существует машина Тьюринга Z такая, что

f ( x ₁ , ..., x _n ) = Ψ _Z ^{( n )} ( x ₁ , ..., [ x _n )

В этом случае мы говорим, что [машина] Z вычисляет f . Если, кроме того, f ( x ₁ , ..., x _n ) является полной функцией, то она называется вычислимой »(Дэвис (1958), стр. 10).

Таким образом, мы пришли к тезису Тьюринга :

«Каждая функция, которую естественно рассматривать как вычислимую, вычислима ... на одной из его машин ...» (Kleene (1952) p.376)

Хотя Клини не привел примеров «вычислимых функций», которые есть у других. Например, Дэвис (1958) дает таблицы Тьюринга для функций константы, преемника и идентичности, трех из пяти операторов примитивных рекурсивных функций :

Вычислим на машине Тьюринга:

Сложение (также является постоянной функцией, если один операнд равен 0)

Приращение (функция-преемник)

Обычное вычитание (определяется, только если x ≥ y ). Таким образом, « x  -  y » является примером частично вычислимой функции.

Правильное вычитание x ┴ y (как определено выше)

Функция идентичности: для каждого i существует функция U _Z ⁿ = Ψ _Z ⁿ ( x ₁ , ..., x _n ), которая извлекает x _i из набора аргументов ( x ₁ , ..., x _n )

Умножение

Булос-Берджесс-Джеффри (2002) дают следующие прозаические описания машин Тьюринга для:

Удвоение: 2 р

Паритет

Добавление

Умножение

Что касается счетной машины , абстрактная модель машины, эквивалентная машине Тьюринга:

Примеры, вычисляемые машиной Abacus (см. Boolos – Burgess – Jeffrey (2002))

Добавление

Умножение

Exponention: (описание блок-схемы / блок-схемы алгоритма)

Демонстрация вычислимости на счетной машине (Булос – Берджесс – Джеффри (2002)) и счетной машине (Минский, 1967):

Шесть рекурсивных функциональных операторов:

1. Нулевая функция
2. Функция преемника
3. Функция идентичности
4. Функция композиции
5. Примитивная рекурсия (индукция)
6. Минимизация

Тот факт, что модели счетчиков / счетчиков могут имитировать рекурсивные функции, обеспечивает доказательство того, что: Если функция "вычислима на машине", то она "вычисляется вручную с помощью частичной рекурсии". Теорема Клини XXIX:

« Теорема XXIX:« Всякая вычислимая частичная функция φ частично рекурсивна ... »(курсив в оригинале, с. 374).

Обратное выглядит как его Теорема XXVIII. Вместе они составляют доказательство их эквивалентности - теорему Клини XXX.

1952 г. Тезис Черча – Тьюринга

С его теоремой XXX Клини доказывает на эквивалентности два «Тезисы» -The церковь Thesis и Thesis Тьюринга. (Клини может только предположить (предположить) истинность обоих тезисов - он их не доказал ):

ТЕОРЕМА XXX: Следующие классы частичных функций ... имеют одни и те же члены: (а) частично рекурсивные функции, (б) вычислимые функции ... " (стр. 376)

Определение «частично рекурсивной функции»: «Частичная функция φ является частично рекурсивной в [частичных функциях] ψ ₁ , ... ψ _n, если существует система уравнений E, которая рекурсивно определяет φ из [частичных функций] ψ ₁ , ... ψ _n "(стр. 326)

Таким образом, согласно теореме XXX Клини: любой метод создания чисел из входных чисел - рекурсивные функции, вычисляемые вручную или вычисляемые машиной Тьюринга, или эквивалентные - приводит к « эффективно вычислимой / вычислимой функции». Если мы принимаем гипотезу о том, что каждое вычисление / вычисление может быть выполнено любым из методов эквивалентно, мы принимаем как теорему Клини XXX (эквивалентность), так и тезис Черча – Тьюринга (гипотеза «каждого»).

Несогласие: «Алгоритм - это еще не все ...» Бласс и Гуревич (2003)

Идея отделения тезисов Чёрча и Тьюринга от «тезиса Чёрча-Тьюринга» появляется не только у Клини (1952), но и у Бласса-Гуревича (2003). Но пока есть договоренности, есть и разногласия:

«... мы не согласны с Клини в том, что понятие алгоритма так хорошо изучено. На самом деле понятие алгоритма богаче в наши дни, чем во времена Тьюринга. Анализ Тьюринга, например, алгоритмы, которые взаимодействуют со своим окружением, алгоритмы, входные данные которых являются абстрактными структурами, и геометрические или, в более общем смысле, недискретные алгоритмы »(Бласс-Гуревич (2003) стр. 8, жирный шрифт добавлен)

1954 Характеристика А.А. Маркова-младшего.

Андрей Марков-младший (1954) дал следующее определение алгоритма:

«1. В математике« алгоритм »обычно понимается как точный рецепт, определяющий вычислительный процесс, ведущий от различных исходных данных к желаемому результату ....»

«Следующие три особенности характерны для алгоритмов и определяют их роль в математике:

«а) точность рецепта, не допускающая произвола, и его универсальная понятность - определенность алгоритма;

б) возможность начать с исходных данных, которые могут варьироваться в заданных пределах - общность алгоритма;

«в) ориентация алгоритма на получение желаемого результата, который действительно получается в конце с правильными исходными данными - убедительность алгоритма». (стр.1)

Он признал, что это определение «не претендует на математическую точность» (стр. 1). Его монография 1954 года была его попыткой более точно определить алгоритм; он видел свое получившееся определение - свой «нормальный» алгоритм - как «эквивалент концепции рекурсивной функции » (стр. 3). Его определение включало четыре основных компонента (Глава II.3, стр. 63 и далее):

«1. Отдельные элементарные шаги, каждый из которых будет выполняться в соответствии с одним из [правил замены] ... [правил, данных вначале]

«2. ... шаги локального характера ... [Таким образом, алгоритм не изменит больше, чем определенное количество символов слева или справа от наблюдаемого слова / символа]

«3. Правила формул подстановки ... [список этих формул он назвал« схемой »алгоритма]

«4. ... средство различения« заключительной замены »[т.е. различимое« конечное / конечное »состояние или состояния]

Во введении Марков заметил, что «все значение для математики» попыток более точно определить алгоритм будет «в связи с проблемой конструктивного основания математики» (стр. 2). Ян Стюарт (см. Encyclopædia Britannica) разделяет аналогичное убеждение: «... конструктивный анализ во многом находится в том же алгоритмическом духе, что и информатика ...». Для получения дополнительной информации см. Конструктивную математику и интуиционизм .

Отличимость и локальность : оба понятия впервые появились у Тьюринга (1936–1937) -

«Новые наблюдаемые квадраты должны быть немедленно распознаваемы компьютером [ sic : компьютер был человеком в 1936 году]. Я считаю разумным предположить, что они могут быть только квадратами, расстояние от которых до ближайшего из наблюдаемых квадратов не превышает определенное фиксированное количество. Будем считать, что каждый из новых наблюдаемых квадратов находится в пределах L квадратов от одного из ранее наблюдаемых квадратов ». (Тьюринг (1936), стр. 136 в издании Дэвиса, неразрешимый )

Местность занимает видное место в работе Гуревича и Ганди (1980) (цитируемых Гуревичем). «Четвертый принцип механизмов» Ганди - это «принцип локальной причинности»:

«Теперь мы подошли к наиболее важным из наших принципов. В анализе Тьюринга требование, чтобы действие зависело только от ограниченной части записи, было основано на человеческом ограничении. Мы заменяем это физическим ограничением, которое мы называем принципом локального причинность. Ее оправдание заключается в конечной скорости распространения эффектов и сигналов: современная физика отвергает возможность мгновенного действия на расстоянии ». (Ганди (1980) стр. 135 в J. Barwise et al.)

1936, 1963, 1964 Характеристика Гёделя

1936 : Довольно известная цитата Курта Гёделя появляется в «Замечании, добавленном в доказательство [оригинальной немецкой публикации] в его статье« О длине доказательств », переведенной Мартином Дэвисом, которая появляется на стр. 82–83 книги « Неразрешимое » . ряд авторов - Клини, Гуревич, Ганди и др. - цитировали следующее:

«Таким образом, понятие« вычислимое »в определенном смысле является« абсолютным », в то время как практически все другие известные метаматематические понятия (например, доказуемое, определяемое и т. Д.) Весьма существенно зависят от системы, относительно которой они определены». (стр.83)

1963 : В «Примечании» от 28 августа 1963 года, добавленном к его знаменитой статье « О формально неразрешимых суждениях» (1931), Гёдель заявляет (в сноске) свою веру в то, что « формальные системы » обладают «характерным свойством, заключающимся в том, что рассуждения в них, в принципе, могут быть полностью заменены механическими устройствами »(с. 616 в van Heijenoort). «… благодаря« работе AM Тьюринга теперь может быть дано точное и, несомненно, адекватное определение общего понятия формальной системы [и] теперь возможна полностью общая версия теорем VI и XI »(стр. 616). В примечании 1964 года к другой работе он выражает то же мнение более решительно и более подробно.

1964 : В постскриптуме от 1964 года к докладу, представленному в Институт перспективных исследований весной 1934 года, Гёдель усилил свое убеждение в том, что «формальные системы» - это те, которые можно механизировать:

«Вследствие более поздних достижений, в частности того факта, что благодаря работе AM Тьюринга теперь может быть дано точное и, несомненно, адекватное определение общей концепции формальной системы ... Работа Тьюринга дает анализ концепции». механическая процедура »(псевдоним« алгоритм »,« вычислительная процедура »или« конечная комбинаторная процедура »). Показано, что эта концепция эквивалентна концепции« машины Тьюринга ». * Формальной системой можно просто определить любую механическую процедуру. для создания формул, называемых доказуемыми формулами ... ". (стр. 72 в издании Мартина Дэвиса . Неразрешимое : «Постскриптум» к «Неразрешимым предложениям формальных математических систем», появляющееся на стр. 39, loc. cit.)

* Указывает на сноску, в которой Гёдель цитирует работы Алана Тьюринга (1937) и Эмиля Поста (1936), а затем делает следующее интригующее заявление:

«Что касается предыдущих эквивалентных определений вычислимости, которые, однако, гораздо менее подходят для нашей цели, см. Alonzo Church , Am. J. Math., Том 58 (1936) [появившийся в The Undecidable pp. 100-102]).

Определения Черча охватывают так называемую « рекурсию » и « лямбда-исчисление » (т. Е. Λ-определяемые функции). В его сноске 18 говорится, что он обсуждал отношения «эффективной вычислимости» и «рекурсивности» с Гёделем, но независимо поставил под сомнение «эффективную вычислимость» и «λ-определимость»:

«Теперь мы определим понятие ... эффективно вычислимой функции положительных целых чисел, отождествляя его с понятием рекурсивной функции положительных целых чисел ¹⁸ (или λ-определяемой функции положительных целых чисел.

"Уже указывалось, что для каждой функции положительных целых чисел, которая эффективно вычисляется в только что определенном смысле, существует алгоритм вычисления ее значения.

"Наоборот, это правда ..." (стр. 100, «Неразрешимое»).

Из этого и следующего должно было заключаться, что для Гёделя машины Тьюринга было достаточно, а лямбда-исчисление было «гораздо менее подходящим». Далее он подчеркивает, что в отношении ограничений человеческого разума все еще не принято жюри:

(«Обратите внимание, что вопрос о том, существуют ли конечные немеханические процедуры **, не эквивалентные никакому алгоритму, не имеет никакого отношения к адекватности определения« формальной системы »и« механической процедуры ».) (Стр. 72, loc. Cit.)

"(Для теорий и процедур в более общем смысле, указанных в сноске **, ситуация может быть иной. Обратите внимание, что результаты, упомянутые в постскриптуме, устанавливают не какие-либо границы для возможностей человеческого разума, а, скорее, для возможностей чистого формализма. по математике) (стр. 73 loc. cit.)

Сноска **: «То есть, например, подразумевает использование абстрактных терминов на основе их значения. См. Мою статью в Dial. 12 (1958), стр. 280». (эта сноска появляется на стр. 72, loc. cit).

Характеристика Минского 1967 года

Мински (1967) открыто утверждает, что «алгоритм - это« эффективная процедура », и отказывается использовать слово« алгоритм »в дальнейшем в своем тексте; на самом деле, его индекс дает понять, что он думает об« алгоритме, синониме эффективной процедуры »( с. 311):

«В дальнейшем мы будем использовать последний термин [ эффективная процедура ]. Термины примерно синонимичны, но есть ряд оттенков значения, используемых в разных контекстах, особенно для« алгоритм »» (курсив в оригинале, стр. 105 )

Другие авторы (см. Кнут ниже) используют слово «эффективная процедура». Это заставляет задуматься: что Мински понимает под «эффективной процедурой»? Он начинает с:

«... свод правил, которые время от времени говорят нам, как именно вести себя» (стр. 106)

Но он признает, что это подлежит критике:

«... критика того, что интерпретация правил оставлена ​​на усмотрение какого-то человека или агента» (стр. 106)

Его изысканность? Чтобы «указать, наряду с формулировкой правил, детали механизма, который должен их интерпретировать ». Чтобы избежать «громоздкого» процесса «повторять это заново для каждой отдельной процедуры», он надеется определить «достаточно единообразное семейство механизмов подчинения правилам». Его «формулировка»:

"(1) язык, на котором должны быть изложены наборы правил поведения, и

«(2) единая машина, которая может интерпретировать операторы на языке и, таким образом, выполнять шаги каждого указанного процесса». (курсив в оригинале, все цитируют этот пункт, стр. 107)

В конце концов, однако, он по-прежнему обеспокоен тем, что «в этом вопросе остается субъективный аспект. Разные люди могут не согласиться с тем, следует ли назвать ту или иную процедуру эффективной» (стр. 107).

Но Мински это не смутило. Он сразу же вводит «Анализ вычислительного процесса Тьюринга» (его глава 5.2). Он цитирует то, что он называет « тезисом Тьюринга ».

«Любой процесс, который естественно можно назвать эффективной процедурой, может быть реализован машиной Тьюринга» (стр. 108. (Мински комментирует, что в более общей форме это называется « тезисом Черча »).

После анализа «Аргумента Тьюринга» (его глава 5.3) он замечает, что «эквивалентность многих интуитивных формулировок» Тьюринга, Чёрча, Клини, Поста и Смуллиана »... приводит нас к предположению, что здесь действительно существует« объективная цель ». 'или' абсолютное 'понятие. Как выразился Роджерс [1959]:

«В этом смысле понятие эффективно вычислимой функции является одним из немногих« абсолютных »концепций, порожденных современной работой по основам математики» (Мински, стр. 111, цитируя Роджерса, Хартли-младшего (1959) . вычислимость , J. SIAM 7, 114-130.)

1967 Характеристика Роджерса

В своей Теории рекурсивных функций и эффективной вычислимости 1967 года Хартли Роджерс характеризует «алгоритм» примерно как «канцелярскую (т. Е. Детерминированную, бухгалтерскую) процедуру ... применяемую к ... символическим входам и которая в конечном итоге дает результат для каждого такого входа. , соответствующий символьный выход »(стр. 1). Затем он описывает понятие «в приблизительных и интуитивных терминах» как имеющее 10 «особенностей», 5 из которых он утверждает, что «практически все математики согласятся [с]» (стр. 2). Остальные 5, как он утверждает, «менее очевидны, чем от * 1 до * 5, и в отношении которых мы могли бы найти менее общее согласие» (стр. 3).

Пять «очевидных»:

• 1 Алгоритм - это набор инструкций конечного размера,
• 2 Есть способный вычислительный агент,
• 3 «Есть средства для создания, хранения и извлечения шагов в вычислении»
• 4 Для данных №1 и №2 агент выполняет вычисления «дискретным пошаговым способом» без использования непрерывных методов или аналоговых устройств »,
• 5 Вычислительный агент выполняет вычисления «без использования случайных методов или устройств, например, игральных костей» (в сноске Роджерс задается вопросом, действительно ли №4 и №5 одинаковы)

Остальные 5, которые он открывает для обсуждения, это:

• 6 Нет фиксированных ограничений на размер входных данных,
• 7 Нет фиксированных ограничений на размер набора инструкций,
• 8 Нет фиксированных ограничений на объем доступной памяти,
• 9 Фиксированная конечная граница мощности или возможностей вычислительного агента (Роджерс иллюстрирует на примере простых механизмов, подобных машине Пост-Тьюринга или машине счетчика ),
• 10 Ограничение продолжительности вычислений - «должны ли мы иметь какое-то представление« заблаговременно », сколько времени займет вычисление?» (стр. 5). Роджерс требует, чтобы «вычисление завершалось только после некоторого конечного числа шагов; мы не настаиваем на априорной способности оценить это число». (стр. 5).

1968, 1973 Характеристика Кнута

Кнут (1968, 1973) привел список из пяти свойств, которые широко признаны в качестве требований к алгоритму:

1. Конечность : «Алгоритм всегда должен завершаться после конечного числа шагов ... очень конечного числа, разумного числа»
2. Определенность : «Каждый шаг алгоритма должен быть точно определен; выполняемые действия должны быть строго и однозначно определены для каждого случая»
3. Входные данные : «... количества, которые задаются ему изначально перед запуском алгоритма. Эти входные данные берутся из указанных наборов объектов»
4. Выход : «... количества, которые имеют указанное отношение к входам»
5. Эффективность : «... все операции, выполняемые в алгоритме, должны быть достаточно простыми, чтобы в принципе они могли быть выполнены точно и за конечный промежуток времени человеком, использующим бумагу и карандаш»

Кнут предлагает в качестве примера алгоритм Евклида для определения наибольшего общего делителя двух натуральных чисел (см. Knuth Vol. 1, p. 2).

Кнут признает, что, хотя его описание алгоритма может быть интуитивно ясным, ему не хватает формальной строгости, поскольку не совсем ясно, что означает «точно определенный», или «строго и однозначно определенный» означает, или «достаточно простой», и т. вперед. Он прилагает усилия в этом направлении в своем первом томе, где подробно определяет то, что он называет « машинным языком » для своего «мифического MIX ... первого в мире полиненасыщенного компьютера» (стр. 120 и далее). Многие алгоритмы в его книгах написаны на языке MIX. Он также использует древовидные диаграммы , блок-схемы и диаграммы состояний .

«Качество» алгоритма, «лучшие» алгоритмы : Кнут заявляет, что «на практике нам нужны не только алгоритмы, мы хотим хорошие алгоритмы ...» Он предлагает, чтобы некоторые критерии качества алгоритма - это количество шагов, которые необходимо выполнить. алгоритм, его «адаптируемость к компьютерам, его простота и элегантность и т. д.» Учитывая количество алгоритмов для выполнения одних и тех же вычислений, какой из них «лучший»? Он называет этот вид исследования «алгоритмическим анализом: задан алгоритм, чтобы определить его характеристики производительности» (все цитируют этот абзац: Knuth Vol. 1 p. 7)

1972 Характеристика Стоуна

Стоун (1972) и Кнут (1968, 1973) были профессорами Стэнфордского университета в одно и то же время, поэтому неудивительно, если есть сходства в их определениях (жирный шрифт добавлен для выделения):

«Подводя итог ... мы определяем алгоритм как набор правил, который точно определяет последовательность операций , так что каждое правило является эффективным и определенным, а последовательность завершается за конечное время». (жирный шрифт добавлен, стр. 8)

Стоун примечателен тем, что он подробно обсуждает, что составляет «эффективное» правило - его робот или человек, действующий как робот, должен иметь в себе некоторую информацию и способности , а если нет, то информация и способность должны быть предоставлены в «алгоритм»:

"Чтобы люди следовали правилам алгоритма, правила должны быть сформулированы так, чтобы им можно было следовать в манере роботов , то есть без необходимости думать ... однако, если инструкции [для решения квадратичной уравнение, его пример] должен подчиняться тому, кто знает, как выполнять арифметические операции, но не знает, как извлечь квадратный корень, тогда мы также должны предоставить набор правил для извлечения квадратного корня, чтобы удовлетворить определению алгоритм »(стр. 4-5)

Кроме того, «... не все инструкции приемлемы , потому что они могут требовать от робота возможностей, выходящих за рамки тех, которые мы считаем разумными ». Он приводит пример робота, который задается вопросом: «Генрих VIII - король Англии?» и вывести 1, если да, и 0, если нет, но робот не был ранее предоставлен с этой информацией. И что еще хуже, если робота спросят, был ли Аристотель королем Англии, и роботу было предоставлено только пять имен, он не знал бы, как ответить. Таким образом:

«Интуитивно понятное определение приемлемой последовательности инструкций - это такое, в котором каждая инструкция точно определена, так что робот гарантированно сможет ей подчиняться » (стр. 6)

Дав нам свое определение, Стоун вводит модель машины Тьюринга и заявляет, что набор из пяти кортежей, которые представляют собой инструкции машины, являются «алгоритмом ... известным как программа машины Тьюринга» (стр. 9). Сразу после этого он продолжает говорить, что « вычисление машины Тьюринга описывается следующим образом:

"1. Ленточный алфавит

«2. Форма, в которой [входные] параметры представлены на ленте.

"3. Начальное состояние машины Тьюринга.

«4. Форма, в которой ответы [вывод] будут представлены на ленте, когда машина Тьюринга остановится.

«5. Машинная программа» (курсив добавлен, с. 10)

Этот точный рецепт того, что требуется для «вычислений», находится в духе того, что последует в работах Бласса и Гуревича.

1995 Характеристика Соаре

" Вычисление - это процесс, при котором мы исходим из изначально заданных объектов, называемых входами , в соответствии с фиксированным набором правил, называемых программой, процедурой или алгоритмом , через серию шагов и достигаем конца этих шагов с окончательным результат, называемый выходом . Алгоритм как набор правил, идущих от входов к выходу, должен быть точным и определенным с четко определенным каждым последующим шагом.Понятие вычислимости касается тех объектов, которые могут быть определены в принципе с помощью вычислений. "(курсив в оригинале, жирный шрифт добавлен, стр. 3)

2000 Характеристика Берлински

Во время учебы в Принстоне в середине 1960-х Дэвид Берлински был учеником Алонзо Черча (см. Стр. 160). Его книга 2000 года «Пришествие алгоритма: 300-летнее путешествие от идеи к компьютеру» содержит следующее определение алгоритма :

" Голосом логика:

" алгоритм

конечная процедура,

написано фиксированным символическим словарем,

руководствуясь точными инструкциями,

двигаясь дискретными шагами, 1, 2, 3,. . .,

чье исполнение не требует проницательности, сообразительности,

интуиция, интеллект или проницательность,

и этому рано или поздно приходит конец. "(жирный шрифт и курсив в оригинале, стр. xviii)

2000, 2002 Характеристика Гуревича

Внимательное прочтение «Гуревича 2000» приводит к выводу (к выводу?), Что он считает, что «алгоритм» на самом деле является «машиной Тьюринга» или « машиной указателя », выполняющей вычисления. «Алгоритм» - это не просто таблица символов, которая управляет поведением машины, это не просто один экземпляр машины, выполняющей вычисления с заданным набором входных параметров, и не соответствующим образом запрограммированная машина с отключенным питанием. ; скорее алгоритм - это машина, фактически выполняющая любые вычисления, на которые она способна . Гуревич не сразу заявляет об этом, поэтому приведенный выше вывод (вывод?), Безусловно, вызывает споры:

«… каждый алгоритм может быть смоделирован машиной Тьюринга… программа может быть смоделирована, и, следовательно, ей можно придать точное значение». (стр. 1)

«Часто думают, что проблема формализации понятия последовательного алгоритма была решена Черчем [1936] и Тьюрингом [1936]. Например, согласно Сэвиджу [1987], алгоритм - это вычислительный процесс, определяемый машиной Тьюринга. Чёрч и Тьюринг не решили проблему формализации понятия последовательного алгоритма. Вместо этого они дали (разные, но эквивалентные) формализации понятия вычислимой функции, и алгоритм - это нечто большее, чем функция, которую он вычисляет (курсив добавлен, стр. 3)

«Конечно, понятия алгоритма и вычислимой функции тесно связаны: по определению вычислимая функция - это функция, вычисляемая алгоритмом ... (стр. 4)

В «Блассе и Гуревиче 2002» авторы вызывают диалог между «Кизани» («Q») и «Авторами» (A), используя Янниса Мошовакиса в качестве фольги, где они выходят прямо и категорически заявляют:

«О : Чтобы локализовать разногласия, давайте сначала упомянем два момента согласия. Во-первых, есть некоторые вещи, которые, очевидно, являются алгоритмами по любому определению - машины Тьюринга, ASM с последовательным временем (абстрактные конечные автоматы) и тому подобное ... Во-вторых, другая крайность - это спецификации, которые не могут рассматриваться как алгоритмы согласно чьему-либо определению, поскольку они не дают указаний на то, как что-либо вычислять ... Проблема в том, насколько подробной должна быть информация, чтобы считаться алгоритмом. ... Мошовакис допускает некоторые вещи, которые мы назвали бы только декларативными спецификациями, и он, вероятно, использовал бы слово «реализация» для вещей, которые мы называем алгоритмами ». (абзацы объединены для удобства чтения, 2002: 22)

Такое использование слова «реализация» напрямую затрагивает суть вопроса. В начале статьи Q заявляет о своем прочтении Мошовакиса:

«... [Он] он, вероятно, может подумать, что ваша практическая работа [Гуревич работает в Microsoft] заставляет вас думать о реализациях больше, чем об алгоритмах. Он вполне охотно отождествляет реализации с машинами, но он говорит, что алгоритмы - это нечто большее. Все сводится к тому, что вы говорите, что алгоритм - это машина, а Мощовакис говорит, что это не так ». (2002: 3)

Но авторы болтают здесь, говоря «[L] et придерживается« алгоритма »и« машины », и читатель снова остается в замешательстве. Нам нужно подождать до Дершовица и Гуревича 2007, чтобы получить следующий комментарий в сноске:

«... Тем не менее, если принять точку зрения Мошовакиса, то это« реализация »алгоритмов, которые мы намеревались охарактеризовать» (см. Сноску 9 2007: 6)

2003 Бласс и характеристика Гуревича

Бласс и Гуревич описывают свою работу как эволюцию машин Тьюринга и указательных машин , в частности машин Колмогорова-Успенского (машины KU), машин модификации хранилищ Шёнхаге (SMM) и связывающих автоматов, как это определил Кнут. Работы Ганди и Маркова также считаются влиятельными предшественниками.

Гуревич предлагает «строгое» определение алгоритма (выделено жирным шрифтом):

«... Неформальный аргумент Тьюринга в пользу его тезиса оправдывает более сильный тезис: любой алгоритм может быть смоделирован машиной Тьюринга ... На практике это было бы смешно ... [Тем не менее,] [c] одно обобщение Машины Тьюринга, так что любой алгоритм, неважно насколько абстрактный, можно смоделировать с помощью обобщенной машины? ... Но предположим, что такие обобщенные машины Тьюринга существуют. Какими были бы их состояния? ... структурой первого порядка ... небольшого набора команд достаточно во всех случаях ... вычисление как эволюция состояния ... может быть недетерминированным ... может взаимодействовать со своей средой ... [может быть] параллельным и мультиагентным ... [может иметь] динамическая семантика ... [две основы их работы:] тезис Тьюринга ... [и] понятие структуры (первого порядка) [Tarski 1933] »(Гуревич 2000, стр. 1-2)

Вышеупомянутое вычисление фразы как эволюция состояния заметно отличается от определения Кнута и Стоуна - «алгоритма» как программы машины Тьюринга. Скорее, он соответствует тому, что Тьюринг назвал полной конфигурацией (см. Определение Тьюринга в Undecidable, стр. 118) - и включает в себя как текущую инструкцию (состояние), так и состояние ленты. [см. Kleene (1952), стр. 375, где он показывает пример ленты с 6 символами на ней - все остальные квадраты пустые - и как Gödelize ее объединенный статус ленты-таблицы].

В примерах алгоритмов мы видим эволюцию состояния из первых рук.

1995 - Дэниел Деннет: эволюция как алгоритмический процесс

Философ Дэниел Деннет анализирует важность эволюции как алгоритмического процесса в своей книге 1995 года «Опасная идея Дарвина» . Деннет выделяет три ключевых особенности алгоритма:

• Нейтральность к субстрату : алгоритм полагается на свою логическую структуру. Таким образом, конкретная форма, в которой проявляется алгоритм, не важна (пример Деннета - длинное деление: он одинаково хорошо работает на бумаге, на пергаменте, на экране компьютера, при использовании неонового света или при написании текста на небе). (стр.51)
• В основе бездумности : каким бы сложным ни был конечный продукт алгоритмического процесса, каждый шаг в алгоритме достаточно прост, чтобы его могло выполнить неразумное механическое устройство. Алгоритм не требует «мозга» для его обслуживания или работы. «Стандартная аналогия с учебником отмечает, что алгоритмы - это своего рода рецепты , разработанные для начинающих поваров» (стр. 51).
• Гарантированные результаты : если алгоритм выполняется правильно, он всегда будет давать одни и те же результаты. «Алгоритм - это надежный рецепт». (стр.51)

Именно на основе этого анализа Деннет приходит к выводу, что «согласно Дарвину эволюция - это алгоритмический процесс». (стр. 60).

Однако на предыдущей странице он пошел еще дальше. В контексте своей главы «Процессы как алгоритмы» он заявляет:

«Но тогда ... есть ли вообще какие-то ограничения на то, что можно считать алгоритмическим процессом? Думаю, ответ - НЕТ; если вы хотите, вы можете рассматривать любой процесс на абстрактном уровне как алгоритмический процесс ... Если что Вас удивляет однородность песчинок [океанских] песчинок или прочность лезвия из [закаленной стали], алгоритмическое объяснение - вот что удовлетворит ваше любопытство - и это будет правдой ...

«Какими бы впечатляющими ни были продукты алгоритма, основной процесс всегда состоит из ничего, кроме набора индивидуальных [ sic ] бессмысленных шагов, следующих друг за другом без помощи какого-либо интеллектуального надзора; они« автоматические »по определению: работа автомат ". (стр.59)

Из вышесказанного неясно, утверждает ли Деннетт, что физический мир сам по себе и без наблюдателей является внутренне алгоритмическим (вычислительным), или же наблюдатель, обрабатывающий символы, добавляет «смысл» к наблюдениям.

2002 Джон Сирл добавляет уточняющую оговорку к характеристике Деннета.

Дэниел Деннетт - сторонник сильного искусственного интеллекта : идея о том, что логическая структура алгоритма достаточна для объяснения разума . Джон Сирл , создатель мысленного эксперимента « Китайская комната» , утверждает, что « синтаксис [то есть логическая структура] сам по себе недостаточен для семантического содержания [то есть значения]» ( Searle 2002 , стр. 16). Другими словами, «значение» символов зависит от ума, который их использует; алгоритм - логическая конструкция - сам по себе недостаточен для ума.

Серл предостерегает тех, кто утверждает, что алгоритмические (вычислительные) процессы присущи природе (например, космологи, физики, химики и т. Д.):

Вычисление [...] зависит от наблюдателя, и это потому, что вычисление определяется в терминах манипулирования символами, но понятие «символа» не является понятием физики или химии. Что-то является символом, только если оно используется, рассматривается или рассматривается как символ. Аргумент «китайская комната» показал, что семантика не является внутренне присущей синтаксису. Но это показывает, что синтаксис не присущ физике. [...] Что-то является символом только относительно некоторого наблюдателя, пользователя или агента, который придает ему символическую интерпретацию [...] вы можете назначить вычислительную интерпретацию чему угодно. Но если возникает вопрос: «Является ли сознание вычислительным по своей природе?» ответ: ничто не является вычислительным по своей сути [курсив добавлен для выделения]. Вычисления существуют только относительно некоторого агента или наблюдателя, который навязывает вычислительную интерпретацию какому-либо явлению. Это очевидный момент. Я должен был увидеть это десять лет назад, но не увидел.

-  Джон Сирл, Searle 2002 , стр. 17

2002: Спецификация Булоса-Берджесса-Джеффри расчета машины Тьюринга

Примеры применения этого метода спецификации к алгоритму сложения «m + n» см. В разделе « Примеры алгоритмов» .

Пример в Boolos-Burgess-Jeffrey (2002) (стр. 31–32) демонстрирует точность, необходимую для полной спецификации алгоритма, в данном случае для сложения двух чисел: m + n. Это похоже на требования к камню выше.

(i) Они обсудили роль «числового формата» в вычислениях и выбрали «подсчетную нотацию» для представления чисел:

«Конечно, вычисления могут быть сложнее на практике с некоторыми нотациями, чем с другими ... Но ... в принципе это возможно сделать в любых других нотациях, просто переводя данные ... В целях формирования строго определенного понятия вычислимости , удобно использовать монадическую или таллическую нотацию »(стр. 25-26)

(ii) В начале своего примера они указывают машину, которая будет использоваться в вычислениях, как машину Тьюринга . Ранее они указали (стр. 26), что машина Тьюринга будет четырехкортежной, а не пятикортежной. Подробнее об этом соглашении см. Машина Тьюринга .

(iii) Ранее авторы указали, что положение головки ленты будет обозначаться нижним индексом справа от отсканированного символа. Для получения дополнительной информации об этом соглашении см. Машину Тьюринга . (Далее жирный шрифт добавлен для выделения):

«Мы не дали официального определения того, что такое числовая функция, которая может быть вычислена машиной Тьюринга , указав, как входные данные или аргументы должны быть представлены на машине, и как представлены выходные или значения. Наши спецификации для k- Функция замены положительных целых чисел на положительные целые выглядит следующим образом:

"(a) [ Формат исходного числа: ] Аргументы m ₁ , ... m _k , ... будут представлены в монадической [унарной] нотации блоками с указанным числом штрихов, причем каждый блок отделен от следующего одним пустой, на пустой ленте.

Пример: 3 + 2, 111B11

"(b) [ Исходное положение головки, исходное состояние: ] Вначале машина будет сканировать крайний левый 1 на ленте и будет в своем исходном состоянии, состоянии 1.

Пример: 3 + 2, 1 ₁ 111B11

"(c) [ Успешное вычисление - числовой формат при остановке: ] Если вычисляемая функция присваивает значение n аргументам, которые изначально представлены на ленте, то машина в конечном итоге остановится на ленте, содержащей блок штрихов , а в противном случае пусто ...

Пример: 3 + 2, 11111

«(d) [ Успешное вычисление - положение головки в положении Halt: ] В этом случае [c] машина остановит сканирование самой левой единицы на ленте ...

Пример: 3 + 2, 1 _n 1111

"(e) [ Неудачное вычисление - неудачная остановка или остановка с нестандартным числовым форматом: ] Если функция, которая должна быть вычислена, не присваивает значения аргументам, которые изначально представлены на ленте, то машина либо никогда не будет остановится, или остановится в нестандартной конфигурации ... "(там же)

Пример: B _n 11111 или B11 _n 111 или B11111 _n.

Эта спецификация является неполной: она требует места, где должны быть размещены инструкции, и их формата на машине -

(iv) в ТАБЛИЦЕ конечного автомата или, в случае универсальной машины Тьюринга, на ленте, и

(v) Таблица инструкций в указанном формате

Этот более поздний момент важен. Булос-Берджесс-Джеффри продемонстрировали (стр. 36), что предсказуемость записей в таблице позволяет «сжать» таблицу, помещая записи в последовательность и опуская состояние ввода и символ. Действительно, для примера вычисления машины Тьюринга потребовались только 4 столбца, как показано в таблице ниже (но обратите внимание: они были представлены машине в строках ):

Состояние qk	Отсканированный символ	Действие	Следующее состояние qk		Состояние qn	Отсканированный символ	Действие	Следующее состояние qk		Состояние qk	B-действие	B-следующее состояние qkB	1 действие	1: следующее состояние qk1
1	B	р	ЧАС		1	1	р	2		1	р	ЧАС	р	2
2	B	п	3		2	1	р	2		2	п	3	р	2
3	B	L	4		3	1	р	3		3	L	4	р	3
4	B	L	5		4	1	E	4		4	L	5	E	4
5	B	р	ЧАС		5	1	L	5		5	р	ЧАС	L	5

2006: Утверждение Сипсера и его три уровня описания

Примеры применения этого метода спецификации к алгоритму сложения «m + n» см. В разделе « Примеры алгоритмов» .

Sipser начинает с определения «алгоритма» следующим образом:

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

«... с этого момента наше настоящее внимание сосредоточено на алгоритмах. То есть машина Тьюринга просто служит точной моделью для определения алгоритма ... нам нужно только достаточно хорошо разбираться в машинах Тьюринга, чтобы верить, что они захватывают все алгоритмы »(стр. 156)

Означает ли Сипсер, что «алгоритм» - это просто «инструкции» для машины Тьюринга, или это комбинация «инструкции + (конкретная разновидность) машины Тьюринга»? Например, он определяет два стандартных варианта (многопленочный и недетерминированный) своего конкретного варианта (не такого, как оригинал Тьюринга) и продолжает в своих Проблемах (страницы 160-161) описывать еще четыре варианта ( однократная запись, дважды бесконечная лента (т.е. бесконечная влево и вправо), сброс влево и «оставаться на месте вместо левой». Кроме того, он налагает некоторые ограничения. Во-первых, ввод должен быть закодирован как строка (стр. 157) и говорит о числовых кодировках в контексте теории сложности:

«Но обратите внимание, что унарная нотация для кодирования чисел (например, число 17, закодированное унарным числом 11111111111111111) нецелесообразно, потому что оно экспоненциально больше, чем действительно разумные кодировки, такие как нотация с основанием k для любого k ≥ 2». (стр.259)

Ван Эмде Боас комментирует аналогичную проблему в отношении абстрактной модели вычислений машины с произвольным доступом (ОЗУ), иногда используемой вместо машины Тьюринга при «анализе алгоритмов»: «Отсутствие или наличие мультипликативных и параллельных манипуляций с битами. операций имеет значение для правильного понимания некоторых результатов при анализе алгоритмов.

«... [T] здесь вряд ли существует такая вещь, как« невинное »расширение стандартной модели RAM в единообразных измерениях времени; либо имеется только аддитивная арифметика, либо можно также включать все разумные мультипликативные и / или побитовые Логические инструкции для малых операндов ". (Ван Эмде Боас, 1990: 26)

Что касается «языка описания» алгоритмов, Сипсер завершает работу, начатую Стоун и Булос-Берджесс-Джеффри (выделено жирным шрифтом). Он предлагает нам три уровня описания алгоритмов машины Тьюринга (с. 157):

Описание высокого уровня : «где мы используем ... прозу для описания алгоритма, игнорируя детали реализации. На этом уровне нам не нужно упоминать, как машина управляет своей лентой или головкой».

Описание реализации : «в котором мы используем ... прозу, чтобы описать способ, которым машина Тьюринга перемещает свою голову, и способ, которым она хранит данные на своей ленте. На этом уровне мы не даем подробностей о состояниях или функции перехода».

Формальное описание : «... самый низкий, самый подробный уровень описания ... который полностью описывает состояния машины Тьюринга, функцию перехода и так далее».

Заметки

Рекомендации

• Дэвид Берлински (2000), Пришествие алгоритма: 300-летний путь от идеи к компьютеру , Harcourt, Inc., Сан-Диего, ISBN   0-15-601391-6 (pbk.)
• Джордж Булос , Джон П. Берджесс , Ричард Джеффри (2002), Вычислимость и логика: четвертое издание , Cambridge University Press, Кембридж, Великобритания. ISBN   0-521-00758-5 (PBK).
• Андреас Бласс и Юрий Гуревич (2003), Алгоритмы: поиски абсолютных определений , Бюллетень Европейской ассоциации теоретической информатики 81, 2003. Включает прекрасную библиографию из 56 ссылок.
• Бургин, М. Суперрекурсивные алгоритмы , Монографии по информатике, Springer, 2005. ISBN   0-387-95569-0
• Дэвис, Мартин (1958). Вычислимость и неразрешимость . Нью-Йорк: McGraw-Hill Book Company, Inc. . Источник важных определений и некоторых алгоритмов на основе машины Тьюринга для нескольких рекурсивных функций.
• Дэвис, Мартин (1965). Неразрешимые: основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях . Нью-Йорк: Raven Press. Дэвис дает комментарий перед каждой статьей. Включены статьи Гёделя , Алонсо Чёрча , Тьюринга , Россера , Клини и Эмиля Поста .
• Деннет, Дэниел (1995). Опасная идея Дарвина . Нью-Йорк: Пробный камень / Саймон и Шустер.
• Робин Ганди , Тезис Черча и принципы механизмов , в Дж. Барвайз , Х. Дж. Кейслер и К. Кунен , ред., Симпозиум Клини , издательство North-Holland Publishing Company, 1980 г., стр. 123–148. Знаменитые «4 принципа [вычислительных] механизмов» Ганди включают «Принцип IV - Принцип локальной причинности».
• Юрий Гуревич , Последовательные абстрактные конечные автоматы захватывают последовательные алгоритмы , Транзакции ACM по вычислительной логике, Том 1, № 1 (июль 2000 г.), страницы 77–111. Включает библиографию из 33 источников.
• Клини К., Стивен (1943). «Рекурсивные предикаты и квантификаторы» . Труды Американского математического общества . Труды Американского математического общества, Vol. 53, No. 1. 54 (1): 41–73. DOI : 10.2307 / 1990131 . JSTOR   1990131 . Перепечатано в The Undecidable , p. 255ff. Клини уточнил свое определение «общей рекурсии» и продолжил в своей главе «12. Алгоритмические теории» постулировать «Тезис I» (стр. 274); Позже он повторил этот тезис (в Kleene 1952: 300) и назвал его «Тезисом Чёрча» (Kleene 1952: 317) (т. е. тезисом Чёрча ).
• Клини, Стивен С. (1991) [1952]. Введение в метаматематику (Десятое изд.). Издательская компания Северной Голландии. Отличный - доступный, читаемый - справочник по математическим "основам".
• Кнут, Дональд Э .. (1973) [1968]. Искусство программирования, второе издание, том 1 / Основные алгоритмы (2-е изд.). Издательство Эддисон-Уэсли. Первый из трех знаменитых текстов Кнута.
• Льюис, Х.Р. и Пападимитриу, С.Х. Элементы теории вычислений , Прентис-Холл, Аппре-Сэдл-Ривер, Нью-Джерси, 1998 г.
• Марков А.А. (1954) Теория алгоритмов . [Перевод Жака Шорр-Кона и сотрудников PST] Выходные данные Москва, Академия наук СССР, 1954 [т.е. Иерусалим, Израильская программа научных переводов, 1961; можно получить в Управлении технических служб Министерства торговли США, Вашингтон] Описание 444 p. 28 см. Добавлен тп в русскоязычном переводе трудов Математического института АН СССР, т. 42. Первоначальное название: Теория алгерифмов. [QA248.M2943 Библиотека Дартмутского колледжа. Министерство торговли США, Управление технических услуг, номер OTS 60-51085.]
• Минский, Марвин (1967). Вычисление: конечные и бесконечные машины (Первое изд.). Прентис-Холл, Энглвуд-Клиффс, Нью-Джерси. Мински расширяет свое «... представление об алгоритме - эффективной процедуре ...» в главе 5.1. Вычислимость, эффективные процедуры и алгоритмы. Бесконечные машины.
• Хартли Роджерс младший (1967), Теория рекурсивных функций и эффективная вычислимость , MIT Press (1987), Кембридж, Массачусетс, ISBN   0-262-68052-1 (pbk.)
• Сирл, Джон (2002). Сознание и язык . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN   0-521-59744-7 .
• Роберт Соаре , (1995, чтобы появиться в Трудах 10-го Международного конгресса логики, методологии и философии науки , 19-25 августа 1995, Флоренция, Италия), « Вычислимость и рекурсия» ), в Интернете по адресу ??.
• Майкл Сипсер , (2006), Введение в теорию вычислений: второе издание , Технология курса Томпсона, див. из Thompson Learning, Inc. Бостон, Массачусетс. ISBN   978-0-534-95097-2 .
• Ян Стюарт , Алгоритм , Британская энциклопедия 2006.
• Стоун, Гарольд С. Введение в компьютерную организацию и структуры данных (изд. 1972 г.). Макгроу-Хилл, Нью-Йорк. См., В частности, первую главу, озаглавленную: « Алгоритмы, машины Тьюринга и программы» . Его краткое неформальное определение: «... любая последовательность инструкций, которой может подчиняться робот, называется алгоритмом » (стр. 4).
• Питер ван Эмде Боас (1990), «Машинные модели и симуляции», стр. 3–66, опубликовано в Jan van Leeuwen (1990), Справочник по теоретической информатике. Том A: Алгоритмы и сложность , MIT Press / Elsevier, 1990, ISBN   0-444-88071-2 (Том A)