Напомним, что означают все эти теоремы и принципы. Закон исключенного третьего: из двух высказываний — «А» или «не А» — одно обязательно является истинным

Закон исключенного третьего: из двух высказываний — «А» или «не А» — одно обязательно является истинным, то есть два суждения, одно из которых является отрицанием другого, не могут быть одновременно истинными, одно из них необходимо истинно (либо ложно).

Закон двойного отрицания: Ø Ø А ®А.

Принцип Маркова: Пусть для некоторого свойства имеется алгоритм , выясняющий для всякого натурального числа N, обладает ли N свойством . Если опровергнуто предположение о том, что ни одно натуральное число не обладает свойством , то имеется натуральное число со свойством .

Те́зис Чёрча — Тью́ринга — фундаментальное эвристическое утверждение, существенное для многих областей науки, в том числе, для математической логики, теории доказательств, информатики, кибернетики, дающее интуитивное понятие о вычислимости. Это утверждение было высказано Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов.

В терминах теории рекурсии, это утверждение формулируется как совпадение классов вычислимых и частично рекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча.

Другие практические варианты утверждения:

Физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга;

Сильный тезис Чёрча — Тьюринга (тезис Чёрча — Тьюринга — Дойча): любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством.

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

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

В 1945 году С. К. Клини предложил новый вариант интуиционистского понимания арифметических суждений, основанный на развитой в 1930-е годы теории алгоритмов. Дальнейшая разработка этого понимания и связанных с ним идей в научной школе А. А. Маркова привела к возникновению современной конструктивной математики.

Date: 2015-11-13; view: 345; Нарушение авторских прав