Back نظرية الحسوبية Arabic কম্পিউটেবিলিটি থিয়ৰী Assamese Teoría de la computabilidá AST Hesablama nəzəriyyəsi Azerbaijani Изчислителна теория Bulgarian পরিগণনীয়তা তত্ত্ব (কম্পিউটার বিজ্ঞান) Bengali/Bangla Teorie vyčíslitelnosti Czech Шутланаяслăх теорийĕ CV Beregnelighed Danish Berechenbarkeitstheorie German
La teoria de la computabilitat és la part de la computació que estudia els problemes de decisió que poden ser resolts amb un algorisme o equivalentment amb una màquina de Turing.[1][2][3] La teoria de la computabilitat s'interessa per quatre preguntes:
- Quins problemes pot resoldre una màquina de Turing?
- Quins altres formalismes equivalen a les màquines de Turing?
- Quins problemes requereixen màquines més poderoses?
- Quins problemes requereixen màquines menys poderoses?
La teoria de la complexitat computacional classifica les funcions computables segons l'ús que fan de diversos recursos en diversos tipus de màquina.
- ↑ Brainerd, Walter S.. Theory of computation. Nova York,: Wiley, [1974]. ISBN 0-471-09585-0.
- ↑ Turing, A. M. «On Computable Numbers, with an Application to the Entscheidungsproblem» (en anglès). Proceedings of the London Mathematical Society, s2-42, 1, 1937, pàg. 230–265. Arxivat de l'original el 2019-06-27. DOI: 10.1112/plms/s2-42.1.230. ISSN: 1460-244X [Consulta: 15 març 2020].
- ↑ The universal Turing machine : a half-century survey. 2a edició. Wien: Springer-Verlag, 1995. ISBN 3-211-82637-8.