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

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

Содержание

• 1 Проблема определения
• 2 Иерархия Хомского
• 3 Особенности хорошего алгоритма
• 4 1881 г. Отрицательная реакция Джона Венна на логическую машину У. Стэнли Джевонса 1870 г.
• 5 1943 г., 1952 Характеристика Стивена Клини
  • 5.1 1943 "Тезис I", 1952 "Тезис Черча"
  • 5.2 1952 "Тезис Тьюринга"
  • 5.3 1952 Тезис Черча – Тьюринга
  • 5.4 Несогласие: "Есть еще алгоритму... »Бласс и Гуревич (2003)
• 6 1954 Характеристика А. А. Маркова-младшего
• 7 1936, 1963, 1964 Характеристика Гёделя
• 8 Характеристика Мински 1967
• 9 Характеристика Роджерса 1967 года
• 10 1968, 1973 Характеристика Кнута
• 11 1972 Характеристика Стоуна
• 12 1995 Характеристика Соара
• 13 2000 Характеристика Берлински
• 14 2000, 2002 Характеристика Гуревича
• 15 2003 Характеристика Бласса и Гуревича
• 16 1995 - Дэниел Деннет: эволюция как алгоритмический процесс
• 17 2002 Джон Сирл добавляет проясняющую оговорку к персонажу Деннета ization
• 18 2002: Спецификация Булоса-Берджесса-Джеффри вычисления машины Тьюринга
• 19 2006: Утверждение Сипсера и его три уровня описания
• 20 Примечания
• 21 Ссылки

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

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

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

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

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

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

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

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

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

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

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

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

См. Также Взаимосвязь между классами сложности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1943 «Тезис I», 1952 «Тезис Черча»

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

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

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

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

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

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

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

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

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

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

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

1952 г. «Тезис Тьюринга»

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

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

Примеры:

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

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

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

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

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

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

f (x 1,..., x n) = Ψ Z(x1,..., [x n)

В этом случае мы говорим, что [машина] Z вычисляет f. Если, кроме того, f (x 1,..., x n) является полной функцией, тогда она называется вычислимой "(Davis (1958) p. 10)

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

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

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

, вычисляемых машиной Тьюринга:

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

Приращение (функция-последователь)

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

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

Функция идентичности: для каждого i функция U Z = Ψ Z(x1,..., x n) существует, что извлекает x i из набора аргументов (x 1,..., x n)

Умножение

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

Удвоение: 2p

Четность

Сложение

Умножение

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

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

Дополнение

Multiplication

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

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

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

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

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

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

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

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

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

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

Определение« частично рекурсивной функции »:« Частичная функция φ является частично рекурсивной в [частичных функциях] ψ 1,... ψ n, если существует система уравнений E, которая рекурсивно определяет φ из [частичных функций] ψ 1,... ψ 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 в издании Дэвиса. Undecidable)

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

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

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

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

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

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

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

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

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

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

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

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

«Уже отмечалось, что для каждой функции положительные целые числа, которые эффективно вычисляются в только что что

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

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

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

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

Сноска **: «То есть, например, подразумевают использование абстрактных терминов на основе их значения. См. Мою статью в Циферблат. 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). 5 из которых он утверждает, что «практически все математики согласятся [с]» (стр. 2) он представляет собой понятие в приблизительных и интуитивных терминах как имеющее 10 «характеристик». Остальные 5, как он утверждает, «менее очевидны, чем от * 1 до * 5, и в отношении которых мы могли бы найти менее существующее» (стр. 3)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

« 1. Алфавит ленты

"2. Форма, в которой параметры [input] представляют на ленте

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

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

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

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

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

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

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

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

", выражающегося голосом логика:

«алгоритм - это

.

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

, записанная в фиксированном символическом способе,

управляемыми точными инструкциями,

перемещающаяся дискретными шагами, 1, 2, 3,...,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры применения этого метода-спецификации к алгоритму сложения "m + n" см.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эта спецификация неполна : он требует расположения команд и их формата в машине -

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

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

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

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

См. Примеры этого метода-спецификации, примененного к алгоритму сложения "m + n".

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

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

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

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

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

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

"... [T] здесь вряд ли существует такая вещь, как «невинное» расширение стандартной модели RAM в единых временных показателях; либо есть только аддитивная арифметика, либо можно также включать все разумные мультипликативные и / или побитовые логические инструкции для малых операндов ». (Van Emde Boas, 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 ссылок.
• Бургин, М. Суперрекурсивные алгоритмы, Монографии по информатике, Spring эр, 2005. ISBN 0-387-95569-0
• Дэвис, Мартин (1958). Вычислимость и неразрешимость. Нью-Йорк: McGraw-Hill Book Company, Inc.. Источник важных определений и некоторых основанных на машине Тьюринга алгоритмов для нескольких рекурсивных функций.
• Дэвис, Мартин (1965). Неразрешаемое: Основные статьи о неразрешимых предложениях, неразрешимых задачах и вычислимых функциях. Нью-Йорк: Raven Press. Дэвис дает комментарий перед каждой статьей. Документы Гёделя, Алонсо Черча, Тьюринга, Россера, Клини и Эмиля Поста.
• Деннет, Дэниел (1995). Опасная идея Дарвина. Нью-Йорк: Touchstone / Simon Schuster.
• Робин Ганди, Тезис Черча и принципы механизмов, в J. Барвайз, Х. Дж. Кейслер и К. Кунен, ред., Симпозиум Клини, издательство North-Holland Publishing Company, 1980 г., стр. 123–148. Знаменитые «4 принципа [вычислительных] механизмов» Ганди включают «Принцип IV - Принцип локальной причинности».
• Юрий Гуревич, Последовательные абстрактные конечные машины захватывают последовательные алгоритмы, транзакции ACM на Вычислительная логика, Том 1, № 1 (июль 2000 г.), страницы 77–111. Включает библиографию из 33 источников.
• Kleene C., Stephen (1943). «Рекурсивные предикаты и квантификаторы». Труды Американского математического общества. Труды Американского математического общества, Vol. 53, № 1. 54 (1): 41–73. DOI : 10.2307 / 1990131. JSTOR 1990131.Перепечатано в The Undecidable, стр. 255ff. Клини уточнил свое определение «общей рекурсии» и продолжил в своей главе «12. Алгоритмические теории» постулировать «Тезис I» (стр. 274); Позже он повторил этот тезис (в Kleene 1952: 300) и назвал его «Тезисом Черча» (Kleene 1952: 317) (т. е.).
• Kleene, Stephen C. (1991) [1952]. Введение в метаматематику (десятое изд.). Издательство North-Holland Publishing Company. Отличный - доступный, читаемый - справочный источник по математическим «основам».
• Кнут, Дональд Э.. (1973) [1968]. Искусство программирования, второе издание, том 1 / Основные алгоритмы (2-е изд.). Addison-Wesley Publishing Company. Первый из трех известных текстов Кнута.
• Льюис, HR и Пападимитриу, CH Элементы теории вычислений, Прентис- Холл, Уппре-Сэдл-Ривер, Нью-Джерси, 1998
• А. А. Марков (1954) Теория алгоритмов. [Перевод Жака Шорр-Кона и сотрудников PST] Выходные данные Москва, Академия наук СССР, 1954 [т.е. Иерусалим, Израильская программа научных переводов, 1961 г.; можно получить в Управлении технических служб Министерства торговли США, Вашингтон] Описание 444 стр. 28 см. Добавлен т.п. в русском переводе трудов Математического института АН СССР, т. 42. Первоначальное название: Теория алгерифмов. [QA248.M2943 Библиотека Дартмутского колледжа. Министерство торговли США, Управление технических услуг, номер OTS 60-51085.]
• Мински, Марвин (1967). Вычисления: конечные и бесконечные машины (Первое изд.). Прентис-Холл, Энглвуд Клиффс, Нью-Джерси. Мински расширяет свою «... идею алгоритма - эффективной процедуры...» в главе 5.1 «Вычислимость, эффективные процедуры и алгоритмы». Бесконечные машины.
• Хартли Роджерс младший, (1967), Теория рекурсивных функций и эффективная вычислимость, MIT Press (1987), Cambridge MA, ISBN 0- 262-68052-1 (pbk.)
• Сирл, Джон (2002). Сознание и язык. Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-59744-7. CS1 maint: ref = harv (link )
• Robert Soare, (1995, чтобы появиться в Proceedings 10-го Международного конгресса по логике, методологии и философии науки, 19-25 августа 1995 г., Флоренция, Италия), Computability and Recursion), в Интернете по адресу ??.
• Michael Sipser, (2006), Введение в теорию вычислений: второе издание, Технология курса Томпсона, див. из Thompson Learning, Inc. Бостон, Массачусетс. ISBN 978-0-534-95097-2.
• Ян Стюарт, Алгоритм, Британская энциклопедия 2006.
• Стоун, Гарольд С. Введение в компьютерную организацию и Структуры данных (изд. 1972 г.). Макгроу-Хилл, Нью-Йорк. См., В частности, первую главу, озаглавленную: «Алгоритмы, машины Тьюринга и программы». Его краткое неформальное определение: «... любая последовательность инструкций, которой может подчиняться робот, называется алгоритмом» (стр. 4).
• Питер ван Эмде Боас (1990), «Модели машин и Симуляторы », стр. 3–66, появившиеся в Ян ван Левен (1990), Справочник по теоретической информатике. Том A: Алгоритмы и сложность, MIT Press / Elsevier, 1990, ISBN 0-444-88071-2 (Volume A)