Teoría dela computación

Teoria De La Computacion Segunda parte:Reducibilidad
Introduccion:
en el tema anterior estudiamos la decibilidad haora nos adentraremos en la investigacion sobre la reducibilidad que ha su vezcobra importacia en la teoria de la computacion, pero antes necesitamos una definicion para poder adentrarnos de lleno en el tema

Reducibilidad:

• Se dice que un problema L1 se reduce en tiempopolinomial determinístico a otro problema L2, si asumiendo que existe un algoritmo A2 en P que resuelve L2 es posible construir un algoritmo A1 en P que resuelva L1.

• Escribiremos L1 W L2 parasignificar que L1 se reduce a L2.

Intuitiva: Una problema P1 se reduce polinomialmente a otro problema P2, si existe un algoritmo que transforme una instancia del problema P1 en una instancia del problemaP2 en tiempo polinomial determinístico.

como podemos apreciar la reducibilidad no es mas que utilisar dos problemas uniendolos para asi poder optimizar polinomialmente el rendimiento de los mismosDesarrollo:

ya teniendo una idea mas clara a lo que se refiere la reducibilidad podemos adentrarnos en lo que son los problemas insolubles ya que al tener un problema insoluble podremos aplicarla reducibilidad para convertirlo en soluble.

Problemas insolubles
como sera logico para algunos al decir que un problema es insoluble se infiere que es un problema que nuestro automata no puederesolver, veamos unos ejemplos para que esta idea se concrete

ejemplo 1:
De las siguiente imágenes, cual es la más llamativa?

nuestro automata no puede saber cual es la imagen mas llamativa yaque para cada usuario la respuesta puede variar convirtiendo en este problema insoluble.

ejemplo 2:
Un peluquero afeita a todas las personas que no se afeitan a si mismas. El peluquero: ¿se afeitaasí mismo? (insoluble).

Funciones computables:

Las funciones computables son una formalización de la noción intuitiva de algoritmo y según la tesis Church-Turing son exactamente las funciones...