ЧЁРЧА ТЕЗИС

ЧЁРЧА ТЕЗИС

- принцип, согласно к-рому класс функций, вычислимых с помощью алгоритмов в широком интуитивном смысле, совпадает с классом частично рекурсивных функций. Ч. т.- это естественнонаучный факт, подтверждаемый опытом, накопленным в математике за всю ее историю. Все известные в математике примеры алгоритмов удовлетворяют ему. Ч. т. впервые был высказан А. Чёрчем (A. Church, 1936). Различным уточнениям интуитивного понятия алгоритма соответствуют свои формулировки Ч. т. Тезис Тьюринга заключается в том, что всякая вычислимая в интуитивном смысле функция вычислима с помощью нек-рой Тьюринга машины, апринцип нормализации Маркова - в том, что всякая вычислимая в интуитивном смысле функция вычислима с помощью нек-рого нормального алгорифма. Из эквивалентности известных уточнений понятия алгоритма следует эквивалентность соответствующих вариантов Ч. т. Этот факт является еще одним подтверждением Ч. т. Тезис Чёрча не может быть строго доказан, так как в его формулировке участвует неточное понятие лалгоритм в интуитивном смысле


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Игры ⚽ Поможем написать реферат

Смотреть что такое "ЧЁРЧА ТЕЗИС" в других словарях:

  • ТЕЗИС — (греч. thesis положение, утверждение) 1) в логике Т. называется утверждение, подлежащее доказательству; 2) в теории аргументации Т. положение, которое доказывающая сторона находит нужным внушить аудитории, сделать составной частью ее убеждений;… …   Философская энциклопедия

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

  • Тезис Чёрча — Тезис Чёрча  Тьюринга  Дойча, в информатике и квантовой физике, известный также как CTD принцип (по аббревиатуре от англ. Church, Turing, Deutsch), или как сильный тезис Чёрча  Тьюринга  более строгая в физическом смысле… …   Википедия

  • Тезис Чёрча-Тьюринга — …   Википедия

  • Тезис Чёрча—Тьюринга — …   Википедия

  • Алгоритм — У этого термина существуют и другие значения, см. Алгоритм (значения). Для улучшения этой статьи желательно?: Переработать оформление в соответствии с правил …   Википедия

  • МАССОВАЯ ПРОБЛЕМА — бесконечный класс (научных) проблем (задач), охарактеризованный (или могущий быть охарактеризованным) при помощи нек рого единого эффективно распознаваемого условия. На фигурирующее в этом пояснении понятие проблемы следует смотреть как на… …   Философская энциклопедия

  • АССОЦИАТИВНОЕ ИСЧИСЛЕНИЕ — название, установившееся за исчислениями нек рого точно охарактеризованного типа, хорошо приспособленными для задания конечно определенных ассоциативных систем ( полугрупп). Термин А. и. введен А. А. Марковым. Им же было осуществлено построение… …   Математическая энциклопедия

  • ГРУППОВОЕ ИСЧИСЛЕНИЕ — ассоциативное исчисление, в к ром эффективным образом выполнено естественное групповое требование существования обратной операции. Именно, ассоциативное исчисление наз. Г. и. (см. [1], с. 341), если для него может быть построен инвертирующий… …   Математическая энциклопедия

  • ДИОФАНТОВЫ УРАВНЕНИЯ — алгебраич. уравнения или системы алгебраич. уравнений с рациональными коэффициентами, решения к рых отыскиваются в целых или рациональных числах. Обычно предполагается, что Д. у. имеют число неизвестных, превосходящее число уравнений, в связи с… …   Математическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»