Teoría da computación: Diferenzas entre revisións

A teoría da computabilidade estuda principalmente que alcance dun problema é resoluble cunha computadora. A afirmación de que o [[problema da parada]] non pode ser resolto por unha máquina de Turing<ref>{{Cita publicación periódica |last=[[Alan Turing]] |first= |last2= |first2= |date=1937 |title=On computable numbers, with an application to the Entscheidungsproblem |url=http://www.turingarchive.org/browse.php/B/12 |journal= Proceedings of the [[London Mathematical Society]] |publisher=IEEE |volume=2 |issue=42 |pages=230–265 |doi=10.1112/plms/s2-42.1.230 |accessdate=6 January 2015 }}{{Ligazón morta|data=decembro de 2021 }}</ref> é un dos máis importantes resultados da teoría da computabilidade, xa que é un exemplo dun problema concreto que é simple de formular e imposible de resolver cunha máquina de Turing.