АЛГОРИТМалгоритмическая неразрешимость

АЛГОРИТМ, алгорифм

Найдено 1 определение:

АЛГОРИТМ, алгорифм

от лат. algorithmi, algorismus, n имени арабского ученого 9 в. ал-Хорезми)—точное предписание, задающее потенциально осуществимый (см. Абстракция потенциальной осуществимости) вычислительный процесс (процесс исполнения алгоритма), ведущий от исходных данных, которые могут варьировать, к конечному результату. Овладение общим методом решения точно поставленной задачи по сути дела означает знание алгоритма. Так, умение складывать два числа означает владение алгоритмом сложения чисел (напр., сложением столбиком, которому учат в школе). Необходимо различать алгоритм и алгоритмическое предписание, имеющее внешнюю форму алгоритма, но включающее не до конца определенные шаги. Так, для перевода текста с одного естественного языка на другой нельзя дать алгоритм, поскольку придется апеллировать к таким неточным понятиям, как смысл и контекст. При попытке же применения точного алгоритма получается то, что в более откровенной форме выдают машинные переводчики и в более мягкой, но от этого не менее вредной—профессиональные переводчики в тот момент, когда выходят за рамки полностью освоенных ими понятий и действий. Поскольку процесс исполнения потенциально осуществим, в теоретическом определении алгоритма отвлекаются от реальных ограничений на ресурсы и следят лишь за тем, чтобы в любой момент вычисления требуемая информация и другие ресурсы были конечными. При создании практических алгоритмов проблемы сложности выходят на первый план.

Хотя неформально математики все время занимались поиском алгоритмов, данное понятие было уточнено лишь в 30-х гг. 20 в. Первыми уточнениями были абстрактные определения частично-рекурсивных и представимых функций в формальной теории чисел, появившиеся в связи с задачами доказательств теории. В 1936 Э. Пост и А. Тьюринг независимо друг от друга предложили понятия абстрактных вычислительных машин и подметили, что любой алгоритм в интуитивном смысле слова может быть реализован на данных машинах, несмотря на кажущуюся примитивность их элементарных действий. Так, памятью машины Тьюринга является потенциально бесконечная лента, в каждой клетке которой записан символ из заранее заданного конечного алфавита. Более того, достаточно рассматривать ленту, каждая клетка которой содержит один бит информации, т. е. либо пуста, либо содержит символ |. Процессор машины Тьюринга состоит из головки, которая в любой момент обозревает одну клетку, и программы, состоящей из конечного числа команд, обычно нумеруемых натуральными числами. Каждая команда представляет собой условное действие, зависящее от символа, записанного в клетке. Это действие имеет вид совокупности элементарных инструкций формы ab(L, R, S)i, в которой присутствует лишь одна из букв L, R, S. — приказ сдвинуться на следующем такте на одну клетку влево, R—враво, S— остаться на месте. Элементарная инструкция означает следующее: если машина видит а, записать в клетку Ь, передвинуться в соответствии с командой и перейти к исполнению команды /. Такая элементарность действий машины явилась результатом проведенного Тьюрингом методологического анализа элементарных действий человека по исполнению алгоритмов. Команды машины Поста предвосхитили систему команд современных вычислительных машин. В машине имеются регистры, содержащие натуральные числа, элементарные операции увеличения и уменьшения числа на 1 и условный переход, если число в регистре равно 0. Одновременно А. Черч и X. Б, Карри создали одно из самых абстрактных понятий алгоритма: gamma-определимость, выразимость с помощью терма комбинаторной логика.

И ранее созданные теоретические понятия, и самые элементарные, и самые абстрактные из вновь появившихся уточнений алгоритма оказались эквивалентны. Этот факт, подтвержденный в дальнейшем для всех вновь появлявшихся точных определений алгоритма, послужил основой утверждения, скромно называемого в математике тезисом Черча, хотя степень его подтвержденности ныне выше, чем у любого физического «закона». Содержательное понятие алгоритма эквивалентно по объему любому из имеющихся в данный момент математических уточнений этого понятия, в частности вычислимости на машине Тьюринга.

Одним из последних появилось уточнение алгоритма, наиболее близкое к современным языкам программирования, — рекурсивные схемы Скотта. Это — совокупность определений вида /(5c)

Оцените определение:
↑ Отличное определение
Неполное определение ↓

Источник: Новая философская энциклопедия

Найдено схем по теме АЛГОРИТМ, алгорифм — 0

Найдено научныех статей по теме АЛГОРИТМ, алгорифм — 0

Найдено книг по теме АЛГОРИТМ, алгорифм — 0

Найдено презентаций по теме АЛГОРИТМ, алгорифм — 0

Найдено рефератов по теме АЛГОРИТМ, алгорифм — 0