Teoria calculabilității
studiul funcțiilor calculabile și al gradelor Turing / From Wikipedia, the free encyclopedia
Teoria calculabilității este o ramură a logicii matematice, a informaticii și a teoriei computației, care își are originea în anii 1930, cu studiul funcțiilor calculabile(d) și al gradelor Turing(d). Domeniul s-a extins, incluzând studiul calculabilității și definibilității generalizate. În aceste domenii, teoria calculabilității se suprapune cu teoria demonstrațiilor(d) și teoria descriptivă a mulțimilor(d).
Chestiunile de bază abordate de teoria calculabilității sunt „ce înseamnă că o funcție de numere naturale este calculabilă?” și „cum pot fi clasificate funcțiile necalculabile într-o ierarhie în funcție de nivelul lor de necalculabilitate?”. Răspunsurile la aceste întrebări au condus la o bogată teorie care este încă activ cercetată.
Teoreticienii calculabilității din logica matematică studiază adesea teoria calculabilității relative, noțiunile de reductibilitate structurile pe grade descrise în acest articol. Acest lucru contrastează cu teoria ierarhiilor subrecursive, cu metodele formale(d) și cu limbajele formale, care sunt comune în studiul de teoriei calculabilității în informatică. Există însă o suprapunere considerabilă de cunoștințe și metode între aceste două comunități de cercetare și nu se poate trasa o linie fermă de demarcație între ele.