Тезис Черча–Тьюринга

• Тезис Черча-Тьюринга

  • Тезис утверждает, что все вычислимые функции могут быть реализованы на машине Тьюринга. 
  • Математически эквивалентен понятию частичной рекурсии. 

• История и развитие

  • Черч и Тьюринг опубликовали свои работы в 1936 и 1937 годах соответственно. 
  • Тьюринг представил свою машину в 1936 году, а Черч описал рекурсивные функции в 1936 году. 
  • В 1939 году Тьюринг предложил идею универсальной машины Тьюринга. 

• Вариации и следствия

  • Существуют различные вариации тезиса, включая физический тезис и тезис осуществимости. 
  • Тезис об инвариантности утверждает, что “разумные” машины могут моделировать друг друга с полиномиальными затратами. 
  • Квантовый тезис утверждает, что квантовая машина Тьюринга может моделировать любую модель вычислений. 

• Философские и физические последствия

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