«Теза М»
Важливо розрізняти теза Тюрінга і твердження про те, що все, що може бути розраховано обчислювальним пристроєм, може бути розраховано його машиною. У другого варіанта є своє власне визначення. Ганді називає друге речення «Тезою М». Він звучить так: «Незалежно від того, що може бути обчислено пристроєм, можна обчислити машиною Тьюрінга». У вузькому розумінні тези, він є емпіричним пропозицією, истинностное значення якого невідоме. Теза Тюрінга і “Теза М” іноді плутають. Версія другого в широкому сенсі невірна. Були описані різні умовні машини, які можуть обчислювати функції, які не є вычислимыми по Тьюрингу. Важливо звернути увагу, що перша теза не тягне за собою другий, але узгоджується з його ложностью.
Зворотне имплицирование тези
В теорії обчислюваності теза Черча використовується як опис поняття обчислюваності класом общерекурсивных функцій. Американський Стівен Кліні дав більш загальне формулювання. Він назвав частково рекурсивними всі часткові функції, вычислимые за допомогою алгоритмів.
Зворотне имплицирование зазвичай називається зворотним тезою Черча. Він полягає в тому, що кожна рекурсивна функція позитивних цілих чисел ефективно обчислюється. У вузькому сенсі теза просто позначає таку можливість. А в широкому – абстрагується від питання про те, чи може існувати в ньому ця умовна машина.
