Гіперобчислення

Моделі більш потужні, ніж машина Тюрінга, були введені Аланом Тюрінгом в його роботі 1939 року Системи логік, засновані на ординалах[2]. Ця робота досліджувала математичні системи, в яких існував оракул, який міг вирахувати одну довільну нерекурсивну функцію на множині натуральних чисел. Він використав цю модель для того, щоб показати, що навіть у такій, більш потужній системі, все одно присутні необчислювані функції. У своїй роботі Тюрінг ясно дав зрозуміти, що така модель є не більш ніж математичною абстракцією і не може бути реалізована в реальному світі[3].

• Машина Тюрінга, яка може виконати нескінченну кількість кроків за кінцевий час (просто можливість роботи машини Тюрінга протягом нескінченного часу (тобто потенційна нескінченність) недостатня). Один з передбачуваних способів досягти такого результату — використовувати уповільнення часу для того, щоб дозволити комп'ютеру зробити нескінченну кількість циклів за кінцевий по годинах для зовнішнього спостерігача час (таке обчислення потребують нескінченної енергії — див. простір-час Маламета — Хогарта). Ще одним, чисто математичним, способом є так звана машина Зенона, заснована на парадоксі Зенона. Машина Зенона виконує свій перший крок обчислень за час, наприклад, 1 хвилину, другий за ½ хвилини, третій за ¼ хвилини і т. д. Підсумовуючи цю нескінченну геометричну прогресію, ми отримаємо, що машина виконує нескінченну кількість кроків протягом 2 хвилин. Однак, деякі стверджують, що, відповідно до міркуваннь в парадоксі Зенона, така машина не лише фізично, а й логічно неможлива.[4]
• Оригінальні оракул-машини Тюринга, що були ним винайдені у 1939.
• Дійсний комп'ютер (підвид ідеалізованого аналогового комп'ютера) здатний здійснювати гіперобчислення[5] за умови, що фізика припускає існування справжніх дійсних чисел. Це, ймовірно, вимагає існування якихось дуже дивних законів фізики (наприклад наявності вимірної фізичної константи, яка може бути використана як оракул — див., наприклад, константа Хайтина) та повинно, як мінімум, вимагати можливості вимірювання фізичних констант з довільною точністю, незважаючи на тепловий шум і квантовомеханічні ефекти.
• Вічна машина Тюрінга — це узагальнення машини Зенона, яка може виконати невизначено тривале обчислення, кроки в якому перенумеровані потенційно трансфінітно ординальними числами. Вона моделює звичайну у всіх інших сенсах машину Тюрінга, для якої незупинні обчислення завершуються шляхом досягнення спеціального стану, зарезервованого для досягнення граничного ординалу, і для якої доступні результати всіх попередніх нескінченних обчислень.[6]
• Квантовомеханічні системи, які якимось чином використовують, наприклад, нескінченну суперпозицію станів для обчислення необчислюваних функцій.[7] Це неможливо при використанні стандартного квантового комп'ютера, оскільки доведено, що звичайний квантовий комп'ютер PSPACE-зводимий (квантовий комп'ютер, що працює поліноміальний час, може бути змодельований на класичному комп'ютері, що використовує поліноміальний простір).[8]
• Техніка, відома як необмежений детермінізм, може дозволяти обчислення необчислюваних функцій. Це питання є предметом обговорення в літературі.
• Використання замкнених часоподібних кривих, всупереч поширеній думці, не дозволяє виконувати надтюрінгове обчислення, оскільки відсутній нескінченний об'єм пам'яті.
• На початку 1990-х Хава Сігельманн[9] запропонувала модель, засновану на нескінченній еволюції нейронних мереж, здатну проводити гіперобчислення.[10]

Надтюрингові обчислення мають багато пропозицій альтернативних способів, щоб прочитати оракул або консультативну функцію вбудовані в іншому випадку класичної машині. Інші надають доступ до деяких вищих рівнів арифметичної ієрархії. Наприклад, багатофунуціональна машини Тюрінга, при звичайних припущеннях, зможе обчислити будь-який предикат, який містить ${\displaystyle \Sigma _{1}^{0}}$ або ${\displaystyle \Pi _{1}^{0}}$. За допомогою обмеження рекурсії, навпаки, можна обчислити будь-який предикат або функцію у відповідному тюринговому ступені, який, як відомо, ${\displaystyle \Delta _{2}^{0}}$.

Модель	Обчислювані предикати	Примітки	Посилання
Баготофункціональність	tt(${\displaystyle \Sigma _{1}^{0},\Pi _{1}^{0}}$)	Залежно від зовнішнього спостерігача
Обмеження / проб і помилок	${\displaystyle \Delta _{2}^{0}}$
Повторне обмеження ( K разів)	${\displaystyle \Delta _{k+1}^{0}}$
Простір Маламента-Хогарта	HYP	Залежно від просторово-часової структури	[11]
Аналоговорецидивуюча нейронна мережа	${\displaystyle \Delta _{1}^{0}[f]}$		[12][13]
Недетермінована машина Тюрінга	${\displaystyle \geq T(\Sigma _{1}^{1})}$		[14]
Підвищення функції оракула	${\displaystyle \Delta _{1}^{1}}$	Для моделі з однією послідовності; ${\displaystyle \Pi _{1}^{1}}$

Мартін Девіс, у своїх працях по надтюринговому обчисленню[15][16] відноситься до цієї теми, як до «міфу» та пропонує контраргументи до фізичної реалізованості надтюрингових обчислень. Що стосується його теорії, він полемізує й стверджує, що це нове поле засноване в 1990-х. Ця точка зору ґрунтується на історії теорії обчислюваності (ступеня нерозв'зності, обчислюваності над функціями, дійсних чисел та порядкових).

• Теза Черча
• Пророча машина
• Машина Зенона
• Обчислення
• Апорії Зенона