Теорема Чёрча — Тьюринга
Теоре́ма Чёрча — Тью́ринга — утверждение об отсутствии алгоритма, решающего проблему разрешения. Используется при доказательстве неразрешимости арифметики натуральных чисел[1]. Впервые была сформулирована и доказана в 1936 году Алонзо Чёрчем[2][3] (вместе с тезисом Чёрча); в том же году, но несколько позже этот результат независимо получил Алан Тьюринг[4][5].
Предикат [уточнить] неразрешим, то есть функция:
