teoría de automataleader
Esta teoría proporciona modelos matemáticos que formalizar o concepto de computadora ou algoritmo de forma suficientemente Simplificado e de xeito xeral para que as súas capacidades e limitacións sexan analizadas. Algúns destes modelos desempeñan un papel central en varias aplicacións de informática, incluíndo procesamento de texto, compiladores, deseño de hardware e intelixencia artificial.
Hai moitos outros tipos de autómatas como máquinas de acceso aleatorias, autómatas celulares, Abacus máquinas e máquinas de estado abstracto; Non obstante, en todos os casos demostrouse que estes modelos non son máis xerais que a máquina Turing, xa que a máquina Turing ten a capacidade de simular cada un destes automatos. Isto resulta na máquina de Turing como modelo de ordenador universal.
Teoría da computabilidadedit
Esta teoría explora os límites da posibilidade de resolver problemas a través de algoritmos. Gran parte das ciencias computacionais están dedicadas á resolución de problemas algorítmicos, de xeito que o descubrimento de problemas imposibles é unha gran sorpresa. A teoría da computabilidade é útil para non probar algorítmicamente estes problemas, aforrando así o tempo e esforzo.
Os problemas clasifícanse nesta teoría de acordo co seu grao de imposibilidade:
- Computables Son aqueles para os que hai un algoritmo que sempre os resolve cando hai unha solución e tamén é capaz de distinguir casos que non o teñen. Tamén son coñecidos como decisivos, resolubles ou recursivos.
- Os semicomputadores son aqueles para os que hai un algoritmo capaz de atopar unha solución se existe, pero ningún algoritmo que determina cando a solución non existe (Caso en que o algoritmo para atopar a solución entraría nun loop infinito). O exemplo clásico por excelencia é o problema da parada. Estes problemas tamén son coñecidos como listados, recursivamente enumerables ou recoñecibles, porque se todos os casos posibles do problema están listados, é posible recoñecer a aqueles que teñen solución.
- A Incomputable son aqueles para os que hai Ningún algoritmo que poida resolvelos, sen importar o que teñen ou ningunha solución. O exemplo clásico por excelencia é o problema da implicación lóxica, que é determinar cando unha proposta lóxica é un teorema; Para este problema, non hai algoritmo que, en todos os casos, pode distinguir se unha proposición ou negación é un teorema.
Hai unha versión máis xeral desta clasificación, onde os problemas incribles están subdivididos problemas máis difíciles que outros. A ferramenta principal para acadar estas clasificacións é o concepto de redialidade: un problema a {\ displaystyle a}
redúcese a un problema B {\ Displaystyl b}
Se está baixo a suposición de que se sabe que se sabe que resolve o problema b {\ displaysty b}
é posible resolver o problema a {\ displaystyle a}
; Isto é denotado por un ≤ t b {\ displaystyle a \ leq t} b
e informalmente significa que o problema a {\ displaystyle a }
non é máis difícil de resolver que o problema b {\ displaystyle b}
. Por exemplo, baixo a suposición de que unha persoa sabe como engadir, é moi fácil ensinarlle a multiplicar facendo varias cantidades, polo que se reduce a multiplicación para engadir.
Teoría da complexidade computacionalEditar
Mesmo cando un problema é computable, pode que non sexa é posible resolvelo na práctica se é necesaria unha gran cantidade de memoria ou tempo de execución. A teoría da complexidade computacional estuda as necesidades de memoria, tempo e outros recursos computacionais para resolver problemas; Deste xeito, é posible explicar por que algúns problemas son máis difíciles de resolver que outros. Un dos maiores logros desta rama é a clasificación de problemas, similar á táboa periódica, segundo a súa dificultade. Nesta clasificación, os problemas están separados por clases complexas.
Esta teoría ten aplicación en case todas as áreas de coñecemento onde desexa resolver un problema computacionalmente, porque os investigadores non só queren usar un método para resolver un problema, senón que use o máis rápido. A teoría da complexidade computacional tamén ten aplicacións en áreas como a criptografía, onde se espera que descifrar un código secreto é un problema moi difícil a menos que o contrasinal estea dispoñible, caso en que o problema faise fácil.