пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Принцип Чёрча. Гипотеза Ворфа. Гипотеза Сапира-Ворфа. Формальные модели вычислений (модели Чёрча, Поста, Маркова, Тьюринга, Клини и другие).

Принцип Чёрча: Любое вычисление, для которого существует эффективная процедура, может быть реализовано на машине Тьюринга

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

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


19.06.2014; 15:14
хиты: 86
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2024. All Rights Reserved. помощь