Обчислювальні на машині Поста функції. Теза Поста

Функція називається обчислювальною на машині Поста (або обчислювальною за Постом) якщо існує програма машини Поста, що обчислює функцію , тобто що має наступні властивості:

1) якщо , то програма , що застосовується до вхідного набору даних , закінчує роботу результативною зупинкою, після чого на стрічці залишається число .

2) якщо не визначене, то застосування програми до вхідного набору не приведе до результативної зупинки.

Теза Поста.

Практичні дослідження вчених показали, що кожну функцію, для обчислення значень якої існує алгоритм, можна обчислити за допомогою деякої машини Поста. Цей факт дав підстави Емілю Посту висунути гіпотезу, яку назвали тезою Поста.

Для знаходження значень функції тоді і тільки тоді існує алгоритм, коли вона є обчислювальною за Постом, тобто коли вона може обчислюватись на відповідній машині Поста.

Дана теза не може бути доведена математично, так як одна із сторін тези, а саме поняття алгоритму не є математично точним поняттям.

Теоретично функція, для обчислення якої існує алгоритм, а для обчислення її значень машину Поста побудувати не можливо може існувати. Але досі такої функції не побудували.

Лекція № 6.