Обчисленна множина

Обчисленна множина (також рекурсивна множина) - множина натуральних чисел, для якої існує алгоритм, що отримує на вхід будь-яке натуральне число і після скінченної кількості кроків (можливо залежної від цього числа) дає відповідь, чи належить це число даній множині, чи ні. Іншими словами, множина є обчисленною, якщо її характеристична функція обчисленна . Множина, яка не є обчисленною, називається необчисленною. Також можна говорити про обчисленну множину, що складається з будь-яких конструктивних об'єктів, що кодуються натуральними числами. Будь-яка обчисливана множина є перераховною і арифметичною . Дозволені множини відповідають рівню $\Delta _{1}^{0}$ арифметичної ієрархії .

У загальному випадку, підмножина ${\mathfrak {M}}_{1}$ множини ${\mathfrak {M}}_{2}$ конструктивних елементів називається обчисленною щодо ${\mathfrak {M}}_{2}$, якщо існує алгоритм, застосовний до об'єктів з ${\mathfrak {M}}_{2}$ та у разі застосування до деякого об'єкту ${\mathfrak {M}}_{2}$ цей алгоритм дає відповідь на запитання, чи належить цей об'єкт ${\mathfrak {M}}_{1}$ .

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

Сукупність всіх обчисленних підмножин $\mathbb {N}$ це зліченна множина, а сукупність всіх необчисленних підмножин $\mathbb {N}$ це незліченна множина, так як множина всіх підмножин позитивних цілих чисел $2^{P}$ незліченна.

Існує взаємно однозначна відповідність між обчисленними підмножинами $S\subset P$ та обчисленними дійсними числами $x\in [0,1]$ .

Приклади

• Порожня множина є обчисленною.
• Будь-яка скінченна множина та її доповнення є обчисленними множинами.
• Існують нескінченні обчисленні множини з нескінченним доповненням. Наприклад, множина всіх парних чисел і множина простих чисел обчисленні.
• Доповнення обчисленної множини є обчисленним.
• Об'єднання та перетин скінченного числа обчисленних множин також обчисленні.
• Будь-яка перераховна множина, доповнення якої також перераховне, є обчисленною (теорема Посту).
• Множина раціональних чисел, менших числа $\pi$ є обчисленною.
• Множина, єдиний елемент якої дорівнює одиниці, якщо гіпотеза Рімана вірна, і нулю в іншому випадку, є обчисленною (бо вона скінченна).
• Множина номерів нетривіальних нулів ζ-функції, для котрих порушується гіпотеза Рімана, є обчисленною (хоча невідомо, чи вона порожня, скінченна чи нескінченна).
• Множина рядків, які є правильними доведеннями ZFC, є обчисленною. Її проєкція — множина тверджень, що доводяться в ZFC — перераховна, але, за умови несуперечності ZFC — необчисленна.

Література

• Эббинхауз Г.Д., Якобс К., Ман Ф.К., Хермес Г. Машины Тьюринга и рекурсивные функции. — М. : Мир, 1972. — 262 с.