Иван
Ученик
(130)
10 лет назад
Это существующие формулировки, уточняющие понятие алгоритма. Наиболее известны следующие.
1) С точки зрения А.Черча и С. Клини, в алгоритмическом процессе
вычисляется значение некоторой функции, определенной
на множестве натуральных чисел.
Строгое определение алгоритма, предложенное Черчем и Клини, осно-
вано на понятии частично рекурсивной функции. Они предложили отож-
дествить интуитивное понятие «алгоритм» со строгим математическим
понятием «частично рекурсивная функция».
2) С точки зрения английского математика А.Тьюринга алгоритми-
ческий процесс—это работа некоторой воображаемой вычислительной
машины—машины Тьюринга. Он предложил отождествить интуитивное
понятие «алгоритм» с точным понятием «машина Тьюринга». В качестве
вычислительной машины будет также рассмотрена машина с неограни-
ченными регистрами (МНР). Это абстрактная машина, более сходная с
реальным компьютером по сравнению с машиной Тьюринга.
3) Третий вариант определения алгоритма предложил в 1947 г. россий-
ский математик А.А.Марков. С его точки зрения, алгоритмический про-
цесс – это переработка слов некоторого алфавита с помощью точно опи-
санных правил переработки. Вместо интуитивного понятия «алгоритм»
А.А.Марков вводит строгое понятие «нормальный алгорифм».
Источник: А.П. Ильиных ТЕОРИЯ АЛГОРИТМОВ