WikiDer > Характеристики алгоритмов - Википедия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эта секция не цитировать любой источники. Пожалуйста помоги улучшить этот раздел к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удаленный. (Сентябрь 2018 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1943 г. "Диссертация I", 1952 г. "Диссертация"

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры:

«Функции»: включают «обычное вычитание. м − п"и" дополнение м + п"

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

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

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

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

"Определение 2.5. п-арная функция ж(Икс₁, ..., Икс_п) является частично вычислимый если существует машина Тьюринга Z такая, что

ж(Икс₁, ..., Икс_п) = Ψ_Z^(п)(Икс₁, ..., [Икс_п)

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

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

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

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

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

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

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

Обычное вычитание (определяется, только если Икс ≥ у). Таким образом "Икс − у"является примером частично вычислимой функции.

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

Функция идентичности: для каждого я, функция U_Z^п = Ψ_Z^п(Икс₁, ..., Икс_п) существует, что щипает Икс_я из набора аргументов (Икс₁, ..., Икс_п)

Умножение

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

Удвоение: 2п

Паритет

Добавление

Умножение

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

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

Добавление

Умножение

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

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

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

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

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

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

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

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

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

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

Определение «частично рекурсивной функции»: «Частичная функция φ является частично рекурсивной в [частичных функциях] ψ₁, ... ψ_п если существует система уравнений E, рекурсивно определяющая φ из [частных функций] ψ₁, ... ψ_п"(стр. 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 квадратов от одного из ранее наблюдаемых квадратов »(Turing (1936), стр. 136 в Davis ed. Неразрешимый)

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

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

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

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

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

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

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

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

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

"Что касается предыдущих эквивалентных определений вычислимости, которые, однако, гораздо менее подходят для нашей цели, см. Церковь Алонсо, Являюсь. J. Math., Т. 58 (1936) [появляется в Неразрешимый С. 100-102]).

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

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

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

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

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

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

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

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

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

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

"Мы будем использовать последний термин [an эффективная процедура] впоследствии.Эти термины примерно синонимичны, но в разных контекстах используется ряд значений, особенно для слова «алгоритм» »(курсив в оригинале, стр. 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 Характеристика Кнута

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

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

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

Кнут признает, что, хотя его описание алгоритма может быть интуитивно ясным, ему не хватает формальной строгости, поскольку не совсем ясно, что означает «точно определенный», или «строго и однозначно определенный» означает, или «достаточно простой», и т. вперед. Он делает попытку в этом направлении в своем первом томе, где он определяет в деталях то, что он называет "машинный язык"для своего" мифического СМЕШИВАНИЕ... первый в мире полиненасыщенный компьютер »(стр. 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» авторы ссылаются на диалог между «Quisani» («Q») и «авторами» (A), используя Янниса Мошовакиса в качестве фольги, где они выходят прямо и категорически заявляют:

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

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

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

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

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

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

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Июнь 2008 г.)

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

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

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

Вышеупомянутая фраза вычисление как эволюция состояния заметно отличается от определения Кнута и Стоуна - «алгоритм» как программа машины Тьюринга. Скорее, это соответствует тому, что Тьюринг назвал полная конфигурация (см. определение Тьюринга в Undecidable, p. 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-разрядной функции от положительных целых чисел до положительных целых чисел следующие:

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

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

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

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

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

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

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

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

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

Пример: B_п11111 или B11_п111 или B11111_п

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

(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) нецелесообразно, потому что оно экспоненциально больше, чем действительно разумные кодировки, такие как base k обозначение для любого k ≥ 2. "(стр. 259)

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

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

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

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

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

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

Примечания

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

• Дэвид Берлински (2000), Появление алгоритма: 300-летний путь от идеи до компьютера, Harcourt, Inc., Сан-Диего, ISBN 0-15-601391-6 (pbk.)
• Джордж Булос, Джон П. Берджесс, Ричард Джеффри (2002), Вычислимость и логика: четвертое издание, Издательство Кембриджского университета, Кембридж, Великобритания. 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, №1. 54 (1): 41–73. Дои:10.2307/1990131. JSTOR 1990131. Перепечатано в Неразрешимый, п. 255ff. Клини уточнил свое определение «общей рекурсии» и продолжил в своей главе «12. Алгоритмические теории» постулировать «Тезис I» (стр. 274); Позже он повторил этот тезис (в Kleene 1952: 300) и назвал его «Тезисом Чёрча» (Kleene 1952: 317) (т.е. Церковный тезис).
• Клини, Стивен С. (1991) [1952]. Введение в метаматематику (Десятое изд.). Издательская компания Северной Голландии. Отличный - доступный, читаемый - справочник по математическим «основам».
• Кнут, Дональд Э .. (1973) [1968]. Искусство программирования, второе издание, том 1 / Основные алгоритмы (2-е изд.). Издательство Эддисон-Уэсли. Первый из трех знаменитых текстов Кнута.
• Льюис, Х. и Пападимитриу, C.H. Элементы теории вычислений, Прентис-Холл, Аппре-Сэдл-Ривер, штат Нью-Джерси, 1998 г.
• Марков А.А. (1954) Теория алгоритмов. [Перевод Жака Шорр-Кона и сотрудников PST] Выходные данные Москва, Академия наук СССР, 1954 [т.е. Иерусалим, Израильская программа научных переводов, 1961 г .; можно получить в Управлении технических служб Министерства торговли США, Вашингтон] Описание 444 стр. 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.CS1 maint: ref = harv (связь)
• Роберт Соаре, (1995, чтобы появиться в Материалы 10-го Международного конгресса логики, методологии и философии науки, 19–25 августа 1995 г., Флоренция, Италия), Вычислимость и рекурсия), в Интернете по адресу ??.
• Майкл Сипсер, (2006), Введение в теорию вычислений: второе издание, Thompson Course Technology div. из Thompson Learning, Inc. Бостон, Массачусетс. ISBN 978-0-534-95097-2.
• Ян Стюарт, Алгоритм, Британская энциклопедия 2006.
• Стоун, Гарольд С. Введение в компьютерную организацию и структуры данных (Изд. 1972 г.). Макгроу-Хилл, Нью-Йорк. См., В частности, первую главу, озаглавленную: Алгоритмы, машины Тьюринга и программы. Его краткое неформальное определение: «... любая последовательность инструкций, которую может выполнить робот, называется алгоритм"(стр. 4).
• Питер ван Эмде Боас (1990), "Machine Models and Simulations", стр. 3–66, в Ян ван Леувен (1990), Справочник по теоретической информатике. Том A: алгоритмы и сложность, MIT Press / Elsevier, 1990, ISBN 0-444-88071-2 (Том А)