Back نظرية الحوسبة Arabic Teoría de la computación AST Alqoritmlər nəzəriyyəsi Azerbaijani Teorija računanja BS Teoria de la computació Catalan Θεωρία υπολογισμού Greek Theory of computation English Teoría de la computación Spanish Konputazioaren teoria Basque نظریه محاسبات Persian
La teorio de komputado estas la branĉo de komputado, kiu traktas, ĉu kaj kiel komputaj taskoj povas esti kompetente solvitaj per komputilo. La kampo estas dividita en du ĉefajn branĉojn: teorio de komputebleco kaj komplikteorio, sed ambaŭ branĉoj formaligas modelojn de komputado.
Por efektivigi rigoran studadon de komputado, komputosciencistoj laboras kun matematikaj abstraktigoj de komputiloj nomataj modeloj de komputado. Kelkaj tipoj de tiaj modeloj estas uzataj, sed la plej kutimaj estas diversaj specoj de maŝino de Turing. Maŝino de Turing estas konceptebla kiel persona komputilo kun nelimigita memor-kapacito, kvankam ĉiupaŝe ĝi povas atingi nur etan diskretan porcion de de sia memoro. Fakuloj studas la maŝinon de Turing, ĉar ĝi estas simple formulebla, analizebla kaj kutime eblas pruvi la rezultojn, kaj ĉar ĝi prezentas tion, kion multaj konsideras adekvata modelo de la teorie plej pova komputo-kapablo. Dum la nelimigita memor-kapacito povus esti konsiderata nefizika atributo, por ajna problemo reale solvata per maŝino de Turing la memoro uzata ĉiam estas finia, do ajna problemo, kiu povas esti solvita per maŝino de Turing, principe povas esti solvita per kutima reala komputilo, kiu havas sufiĉan memoron.