Que es computacion
Páginas: 2 (445 palabras)
Publicado: 4 de octubre de 2010
Teoría de la computación
La teoría de la computación es una rama de la matemática y la computación que centra su interés en las limitaciones y capacidades fundamentales de las computadoras.Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo (cuenta o cálculo) y la clasificación de problemas
Teoría de la computabilidad
Artículo principal:Teoría de la computabilidad
Véase también: Indecidibilidad
Esta teoría explora los límites de la posibilidad de solucionar problemas mediante algoritmos. Gran parte de las ciencias computacionalesestán dedicadas a resolver problemas de forma algorítmica, de manera que el descubrimiento de problemas imposibles es una gran sorpresa. La teoría de la computabilidad es útil para no tratar de resolveralgoritmicamente estos problemas, ahorrando así tiempo y esfuerzo.
Los problemas se clasifican en esta teoría de acuerdo a su grado de imposibilidad:
Los computables son aquellos para los cualessí 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.
Lossemicomputables 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 elalgoritmo para encontrar la solución entraría a un bucle infinito). El ejemplo clásico por excelencia es el problema de la parada. A estos problemas también se les conoce como listables, recursivamenteenumerables o reconocibles, porque si se enlistan todos los casos posibles del problema, es posible reconocer a aquellos que sí tienen solución.
Los incomputables son aquellos para los cuales no hayningún algoritmo que los pueda resolver, no importando que tengan o no solución. El ejemplo clásico por excelencia es el problema de la implicación lógica, que consiste en determinar cuándo una...
La teoría de la computación es una rama de la matemática y la computación que centra su interés en las limitaciones y capacidades fundamentales de las computadoras.Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo (cuenta o cálculo) y la clasificación de problemas
Teoría de la computabilidad
Artículo principal:Teoría de la computabilidad
Véase también: Indecidibilidad
Esta teoría explora los límites de la posibilidad de solucionar problemas mediante algoritmos. Gran parte de las ciencias computacionalesestán dedicadas a resolver problemas de forma algorítmica, de manera que el descubrimiento de problemas imposibles es una gran sorpresa. La teoría de la computabilidad es útil para no tratar de resolveralgoritmicamente estos problemas, ahorrando así tiempo y esfuerzo.
Los problemas se clasifican en esta teoría de acuerdo a su grado de imposibilidad:
Los computables son aquellos para los cualessí 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.
Lossemicomputables 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 elalgoritmo para encontrar la solución entraría a un bucle infinito). El ejemplo clásico por excelencia es el problema de la parada. A estos problemas también se les conoce como listables, recursivamenteenumerables o reconocibles, porque si se enlistan todos los casos posibles del problema, es posible reconocer a aquellos que sí tienen solución.
Los incomputables son aquellos para los cuales no hayningún algoritmo que los pueda resolver, no importando que tengan o no solución. El ejemplo clásico por excelencia es el problema de la implicación lógica, que consiste en determinar cuándo una...
Leer documento completo
Regístrate para leer el documento completo.