Diferencia entre revisiones de «Teoría de la computación»
Contenido eliminado Contenido añadido
Deshecha la edición 34706685 de 190.149.11.206 (disc.) |
|||
Línea 18:
Los problemas se clasifican en esta teoría de acuerdo a su grado de ''imposibilidad'':
*Los '''computables''' son aquellos para los cuales sí existe un algoritmo que siempre los resuelve cuando hay una solución y además es capás de distinguir los casos que no la tienen. También se les conoce como ''decidibles'', ''resolubles'' o ''recursivos''.
*Los '''semicomputables''' son aquellos para los cuales hay un algoritmo que es capaz encontrar una solución si es que existe, pero ningún algoritmo que determine cuando la solución no existe (en cuyo caso el algoritmo para buscar la solución entraría en un [[bucle infinito]]). El ejemplo clásico por excelencia es el [[problema de la parada]]. A estos problemas también se les conoce
*Los '''incomputables''' son aquellos para los cuales no hay ningún algoritmo que los pueda resolver, no importando que tengan o no solución. El ejemplo clásico por excelencia es el [[Entscheidungsproblem|problema de la implicación lógica]], que consiste en determinar cuándo una proposición lógica es un [[teorema]]; para este problema no hay ningún algoritmo que en todos los casos pueda distinguir si una proposición o su negación es un teorema.
| |||