Энциклопедия эпистемологии и философии науки - алгоритм
Алгоритм
Иногда к А. относят процедуры, имеющие дело с объектами, не являющимися конструктивными. Таковы, напр., геометрические процедуры нахождения середины отрезка с помощью циркуля и линейки, нахождения наибольшей общей меры двух отрезков и т.п. Возможны и другие ослабления требований, напр., отказ от детерминированности.
Каждый А. определяет вычислимую функцию (функцию, вычислимую данным А.): аргумент функции принимает значения из совокупности возможных исходных данных, а значениями являются соответствующие результаты работы А. Одна вычислимая функция может определяться разными А.
Начиная с 30-х гг. 20 в. математики выработали многочисленные формальные аналоги понятия А. и вычислимой функции: машина Поста; машина Тьюринга; нормальный алгорифм Маркова; частично рекурсивная функция; А.-определимая функция и др. В дальнейшем были предложены и другие формализации; в частности, программы, написанные на любом языке программирования из применяемых на практике, задают А. Все предложенные до сих пор формализации понятия А. оказались эквивалентными: классы определяемых ими функций совпадают. Это подтверждает так называемый тезис Черча: класс вычислимых функций, задаваемых (неформальными) А., совпадает с вычислимыми функциями, задаваемыми А., описанными в одной (любой) из указанных формализации. Поскольку А., заданный в фиксированной формализации, является точно описанным математическим объектом, тезис Черча позволил создать математическую теорию алгоритмов.
А.В. Чагров
Лит.: Катленд Н. Вычислимость: Введение в теорию рек у р с и в н ы х функций. М., 1983; Мальцев А.И. Алгоритмы и рекурсивные функции. М., 1986; Марков А.А., Нагорный Н.М. Теория алгорифмов. М., 1996; Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М., 1972.
Энциклопедия эпистемологии и философии науки. М.: «Канон+», РООИ «Реабилитация»
И.Т. Касавин
2009
Вопрос-ответ:
Похожие слова
Самые популярные термины
1 | 813 | |
2 | 528 | |
3 | 417 | |
4 | 380 | |
5 | 379 | |
6 | 375 | |
7 | 369 | |
8 | 368 | |
9 | 362 | |
10 | 354 | |
11 | 341 | |
12 | 337 | |
13 | 336 | |
14 | 334 | |
15 | 332 | |
16 | 329 | |
17 | 320 | |
18 | 318 | |
19 | 312 | |
20 | 312 |