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

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

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

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