számításelmélet

Számításelmélet a számítógépes tudomány elméleti ága, amely a problémák számíthatóságát, ezek határait és a futási erőforrások igényét vizsgálja. Fő területei közé tartozik az automataelmélet (automataik és formális nyelvek), a számíthatóságtan és a komplexitáselmélet. A központi modellek közé tartoznak a véges automata, a pushdown automata, a Turing-gép és a lambda-kalkulus; ezek segítségével osztályozhatók a nyelvek és a számítási problémák.

A Chomsky-hierarchia szerint a formális nyelvek négy szintre tagolhatók: reguláris nyelvek, kontextusfüggetlen nyelvek, kontextuálisan függő nyelvek és rekurzívan felsorolható nyelvek. A számíthatóságtan a decidabilitás kérdését vizsgálja: vannak olyan problémák, amelyeket nem lehet általánosan megoldani algoritmikus módon, például a megállási probléma. A Church–Turing hipotézis szerint minden effektív számítás leírható Turing-géppel vagy equivalens modelllel.

A komplexitáselmélet a számítási erőforrások (idő, memória) alapján osztályozza a problémákat; legismertebb osztályok közé tartozik a P, az NP és a PSPACE, továbbá az NP-complete és más redukciókkal megfogalmazott nehézségek. A terület hatással van a programozási nyelvek elméletére, a formális verifikációra, kriptográfiára és az algoritmus-tervezés elméletére.