✖


Jump to content

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

    Add links
    Данная статья является дополнением к статье Алгоритм .

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

    Проблема определения [ править ]

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

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

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

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

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

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

    Иерархия Хомского [ править ]

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

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

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

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

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

    Особенности хорошего алгоритма [ править ]

    Ниже приведены желательные характеристики четко определенного алгоритма, как обсуждалось в работе Шайдера и Герстинг (1995):

    • Однозначные операции: алгоритм должен иметь конкретные, обозначенные шаги. Шаги должны быть достаточно точными, чтобы точно указать, что делать на каждом этапе.
    • Хорошо упорядоченный: точный порядок операций, выполняемых в алгоритме, должен быть конкретно определен.
    • Осуществимость: все шаги алгоритма должны быть возможными (также известными как эффективно вычислимые ).
    • Входные данные: алгоритм должен иметь возможность принимать четко определенный набор входных данных.
    • Выход: алгоритм должен выдать некоторый результат на выходе, чтобы можно было оценить его правильность.
    • Конечность: алгоритм должен завершиться после конечного числа инструкций. [2]

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

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

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

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

    (1) «Есть, во-первых, изложение наших данных точным логическим языком»,
    (2) «Во-вторых, мы должны привести эти утверждения в форму, с которой мог бы работать двигатель – в данном случае сведение каждого предложения к его элементарным отрицаниям»,
    (3) «В-третьих, после такого сокращения происходит объединение или дальнейшая обработка наших помещений»,
    (4) «Наконец, результаты необходимо интерпретировать или считывать. Последнее обычно открывает большие возможности для умения и проницательности».

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

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

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

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

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

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

    Церкви » 1943 «Тезис I», 1952 « Тезис

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

    Определение: «Частичная функция φ является вычислимой , если существует машина M, которая ее вычисляет» (Клин (1952), стр. 360).
    «Определение 2.5. n- арная функция f ( x1 существует ,..., xn ) если частично вычислима, машина Тьюринга Z такая, что
    ж ( Икс 1 , ..., Икс п ) знак равно Ψ Z ( н ) ( х 1 , ..., [ х п )
    В этом случае мы говорим, что [машина] Z вычисляет f . Если, кроме того, f ( x1 » ( ,..., xn ) — полная функция, то она называется вычислимой Дэвис (1958) с. 10)

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

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

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

    Вычислимо на машине Тьюринга:
    Сложение (также является функцией константы, если один операнд равен 0)
    Приращение (функция преемника)
    Обычное вычитание (определяется только в том случае, если x ≥ y ). Таким образом, « x − y » является примером частично вычислимой функции.
    Правильное вычитание x ┴ y (как определено выше)
    Функция идентичности: для каждого i функция U Z н = Ψ Z н ( x 1 , ..., x n ) существует, который извлекает x i из набора аргументов ( x 1 , ..., x n )
    Умножение

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

    Удвоение: 2 п.
    Паритет
    Добавление
    Умножение

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

    Примеры, вычислимые на машине Abacus (см. Булос-Берджесс-Джеффри (2002))
    Добавление
    Умножение
    Возведение в степень: (описание блок-схемы/блок-схемы алгоритма)

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

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

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

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

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

    Чёрча – Тьюринга, Диссертация 1952 г.

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

    ТЕОРЕМА XXX. Следующие классы частичных функций... имеют одни и те же члены: (а) частично рекурсивные функции, (б) вычислимые функции...» (стр. 376).
    Определение «частично-рекурсивной функции»: «Частичная функция φ частично рекурсивна в [частичных функциях] ψ 1 , ... ψ n, если существует система уравнений E, которая определяет φ рекурсивно из [частичных функций] ψ 1 , ... ψ н » (с. 326)

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

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

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

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

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

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

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

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

    "1. Отдельные элементарные шаги, каждый из которых будет выполняться по одному из правил [замены]... [правил, приведенных в начале]
    "2. ... шаги локального характера... [Таким образом, алгоритм не будет изменять более определенного количества символов слева или справа от наблюдаемого слова/символа]
    «3. Правила формул замены... [перечень этих он назвал «схемой» алгоритма]
    «4. ...средство различения «завершающей замены» [т.е. различимого «конечного/конечного» состояния или состояний]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    «Теперь мы определяем понятие... эффективно вычислимой функции положительных целых чисел, отождествляя его с понятием рекурсивной функции натуральных чисел. 18 (или λ-определимой функции натуральных чисел.
    «Уже указывалось, что для каждой функции натуральных чисел, которая эффективно вычислима в только что определенном смысле, существует алгоритм вычисления ее значения.
    «И наоборот…» (с. 100, Неразрешимое).

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

    («Заметим, что вопрос о том, существуют ли конечные немеханические процедуры**, не эквивалентные никакому алгоритму, не имеет никакого отношения к адекватности определений «формальной системы» и «механической процедуры».) (с. 72, цит.).
    «(Для теорий и процедур в более общем смысле, указанном в сноске **, ситуация может быть иной. Заметим, что результаты, упомянутые в приписке, устанавливают не какие-либо границы для возможностей человеческого разума, а скорее для возможностей чистого формализма. по математике.) (стр. 73, цит.)
    Сноска **: «То есть такие, которые предполагают использование абстрактных терминов исходя из их значения. См. мою статью в Dial. 12 (1958), стр. 280». (эта сноска имеется на стр. 72, см. выше).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    5 «очевидных»:

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

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

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

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

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

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

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

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

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


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

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

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

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

    Но авторы здесь колеблются, говоря: «Давайте придерживаться «алгоритма» и «машины», и читатель снова остается в замешательстве. Нам придется подождать до Dershowitz and Gurevich 2007, чтобы получить следующий комментарий в сноске:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    машины Тьюринга расчета 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) [ Успешное вычисление — положение головки в положении «Остановка»: ] В этом случае [c] машина прекратит сканирование крайней левой единицы на ленте…
    Пример: 3+2, 1 н 1111
    «(e) [ Неудачное вычисление — отказ от остановки или остановки с нестандартным форматом чисел: ] Если функция, которую нужно вычислить, не присваивает значения аргументам, которые изначально представлены на ленте, то машина либо никогда не остановится, или остановится в какой-то нестандартной конфигурации...» (там же)
    Пример: B n 11111 или B11 n 111 или B11111 n

    Эта спецификация является неполной: она требует места размещения инструкций и их формата в машине.

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

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

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

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

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

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

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

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

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

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

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

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

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

    2011: Янофски [ править ]

    В Яновском (2011) [3] алгоритм определяется как набор программ, реализующих этот алгоритм: набор всех программ разделен на классы эквивалентности. Хотя набор программ не образует категорию, набор алгоритмов образует категорию с дополнительной структурой. Условия, описывающие эквивалентность двух программ, оказываются отношениями связности, которые придают дополнительную структуру категории алгоритмов.

    Примечания [ править ]

    1. ^ cf [164] Андреас Бласс и Юрий Гуревич «Алгоритмы: поиск абсолютных определений», Бюллетень Европейской ассоциации теоретической информатики, номер 81 (октябрь 2003 г.), страницы 195–225. Перепечатано в главе «Логика в информатике. Текущие тенденции в теоретической информатике». World Scientific, 2004, стр. 283–311. Перепечатано в диссертации Чёрча спустя 70 лет. Ontos Verlag, 2006, 24–57, или http://math.ucsd.edu/. ~sbuss/ResearchWeb/FutureOfLogic/paper.pdf (цитируется в статье Дершовица–Гуревича 2007 г.): Сэмюэл Р. Басс, Александр С. Кекрис , Ананд Пиллэй и Ричард А. Шор, «Перспективы математической логики в двадцатом веке». первый век».
    2. ^ Шнайдер, Г. Майкл; Герстинг, Джудит (1995). Приглашение в информатику . Нью-Йорк, штат Нью-Йорк: West Publishing Company. п. 9. ISBN  0314043756 .
    3. ^ Янофски, Носон С. (10 июня 2010 г.). «К определению алгоритма». arXiv : математика/0602053 .

    Ссылки [ править ]

    Retrieved from "https://en.wikipedia.org/w/index.php?title=Algorithm_characterizations&oldid=1194513002"
    Arc.Ask3.Ru: конец переведенного документа.
    Arc.Ask3.Ru
    Номер скриншота №: c245185f0a715937e88dd1381811f8fa__1704784140
    URL1:https://arc.ask3.ru/arc/aa/c2/fa/c245185f0a715937e88dd1381811f8fa.html
    Заголовок, (Title) документа по адресу, URL1:
    Algorithm characterizations - Wikipedia
    Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)