Введение

Исследование вычислимых функций и степеней Тьюринга
концепция вычислимости

Теория вычислимости, также известная как теория рекурсии, является областью математической логики, информатики и теории вычислений, возникшей в 1930-х годах с изучения вычислимых функций и степеней Тьюринга. С тех пор область расширилась, включив в себя изучение обобщенной вычислимости и определимости. В этих областях теория вычислимости пересекается с теорией доказательств и эффективной дескриптивной теорией множеств. Основные вопросы, которые рассматривает теория вычислимости, включают: что значит, что функция на натуральных числах является вычислимой? Как можно классифицировать невычислимые функции в иерархию, основанную на степени их невычислимости? Несмотря на значительное совпадение в знаниях и методах, математические теоретики вычислимости изучают теорию относительной вычислимости, понятия редуцируемости и структуры степеней, в то время как специалисты в области информатики сосредотачиваются на теории субрекурсивных иерархий, формальных методах и формальных языках.

Введение

{| class="wikitable floatright"
|
! n
! width="30px" | 2
! width="30px" | 3
! width="30px" | 4
! width="50px" | 5
! width="120px" | 6
! width="120px" | 7
! width="30px" |
|
! Σ(n)
| align="center" | 4
| align="center" | 6
| align="center" | 13
| align="center" | 4098
| align="center" | 3.5
| align="center" | 1010101018705353
| align="center" |
|
| colspan="8" Функция занятого бобра Σ(n) растёт быстрее, чем любая вычислимая функция. Следовательно, она не является вычислимой.