2
Computabilidad
Modelo de Cómputo : MAQUINA DE TURING
• Nos otorga el marco formal , teórico . Independiente de la máquina, el lenguaje y el compilador
• Define los límites de la computabilidad
• Tesis de Turing : Si una Máquina de Turing no resuelve un problema entonces ninguna computadora
puede hacerlo.
• Tesis de Church: las funciones parciales son la clase de funciones que cualquier sistema computacional
puede calcular
• Tesis de Church Turing: las funciones parciales son aquellas funciones que pueden computarse por
Máquinas de Turing y vicerversa.
Computabilidad : Funciones Parciales y Máquina de Turing
MÁQUINA DE TURING
COMPUTA
FUNCIONESRECONOCE
LENGUAJES
PUEDE
NO
PARARFUNCIONES
PARCIALES
LENGUAJES
RECUSIVAMENTE
ENUMERABLES
LENGUAJES
RECURSIVOS
O
DECIDIBLES
SIEMPRE
PARA
PUEDE
NO
PARAR
FUNCIONES
RECURSIVAS
PRIMITIVASSIEMPRE
PARA
Computabilidad
Teorema Para toda función parcial existe un programa en un lenguaje
esencial para computar dicha función
Cualquier otro lenguaje que tenga las propiedades del lenguaje esencial es un lenguajeTuring Completo.
Hay una equivalencia entre :
Funciones Parciales
Máquina de Turing
Lenguaje Esencial
Computabilidad
Problemas DecidiblesALGORITMO
Lenguajes Recursivos y
Funciones S-computables totales
Halting Problem
Teselación del Plano
Problemas Indecidibles
Funciones parciales ,Leng. Recursivos Enumerables
y Funciones S-computables parciales
Lenguaje MT
Universal
Siempre podemos hacer un programa (proceso)
para un lenguaje computable
Si lo implementamos y no para → indecidible
Si lo implementamos y para → decidible
En este último caso el programa es un ALGORITMO
Problemas No Computables
Computabilidad
Practica 7 -Ej 1 : f(x) = 3x
[A] IF X ≠ 0 GOTO BZ Z + 1IF Z ≠ 0 GOTO E
[B] X X – 1Y Y +1Y Y +1Y Y +1Z Z +1IF Z ≠ 0 GOTO A
6
Solo se pueden hacer operaciones básicas y las comparaciones son contra cero
Practica 7 -Ej 2 : Macro x1+x2
Y X1Z X2
[B] IF Z ≠ 0 GOTO AGOTO E
[A] Z Z -1Y Y + 1GOTO B
Las macros las desarrollamos para poder utilizarlas en otros programasEn este ejemplo hay dos macros que son Y X1y la macro GOTO
Computabilidad
Practica 7 -Ej 5 : f(x1,x2) 1 si x1=x2
0 cc
Z1 X1Z2 X2 uso la macro x2 X1
[A] IF Z1 ≠ 0 GOTO BIF Z2 ≠ 0 GOTO CY Y + 1GOTO E Y queda en 1
[C] GOTO E Y queda en cero[B] IF Z2 ≠ 0 GOTO D
GOTO E Y queda en cero[D] Z1 Z1 -1
Z2 Z2 -1GOTO A
7
Esta es una función TOTAL porque está definida para todo el dominio
Los resultados van a Y
TestingX1 X2 Z1 Z2 Y1 2 0 0 0
1 2 0 1
TestingX1 X2 Z1 Z2 Y2 2 0 0 1
2 2 1 10 0
Computabilidad
Practica 7 -Ej 8 : f(x) √ x si x es un cuadrado perfecto
cc
[A] Z1 Z1 +1Z2 Z1*Z1 uso macro X1*X2IF Z2 = X GOTO B uso macro X1=X2GOTO A
[B] Y Z1
8
Esta es una función PARCIAL porque no está definida para todo el dominio (los x que no son cuadrados perfectos)
Testing
X Y Z1 Z24 0 0 0
1 12 42
Testing
X Y Z1 Z25 0 0 0
1 12 4
3 9 entra en loop
Complejidad
9
Nos enfocamos en los problemas decidiblesdonde los procesos se detiene siempre dando unarespuesta de decisión SI o NO. Estos procesos selos denominan ALGORITMOS
Problemas
Decidibles
ALGORITMO
Otra vez nuestro modelo de cómputo es laMáquina de Turing que se va a detener en unestado de aceptación SI o en un estado de rechazoNO.
Un algoritmo es un proceso para resolver unproblema, con una secuencia finita de pasos y quetermina en un tiempo finito.Siempre debe dar una respuesta
Complejidad
10
Nos interesa estudiar la complejidad de unalgoritmo para medir su eficiencia frente a otroalgoritmo sobre todo cuando estamos frente aentradas de tamaño considerablemente grandes.
La complejidad de un algoritmo es una funciónque representa el tiempo de ejecución en funcióndel tamaño de su entrada.Entonces queremos tener una estimación de comocrece el tiempo de ejecución de un algoritmocuando crece el tamaño de las instancias de laentrada.Lo importante es la cantidad de operacioneselementales ejecutadas y no el tiempo que seemplea en cada una de ellas.
El modelo de Turing representa la función en lospasos que realiza la máquina para un entradadeterminada
El tamaño de una instancia corresponde alnúmero de bits necesarios para representar lainstancia en una computadora . Va a depender delalfabeto y de la base utilizada.Ej. Para almacenar n se necesita la longitud den = |log2 (n) | + 1 dígitos binarios.Para almacenar una lista de m enteros, senecesitan long(m) + m long(N) dígitos binariosdonde N es el valor máximo de la lista.
Complejidad
11
Para expresar el comportamiento dela función para valores grandesusamos la cota superior llamada Ogrande o Big O
Un algoritmo es eficiente si su comportamiento es polinomial.Entonces un problema está bien resuelto si existe un algoritmo decomplejidad polinomial para resolverloHay problemas para los cuales no se conocen algoritmos polinomialesque los resuelvan
i= 1 1 pasowhile i <=n n+1 pasos comparación (n veces + 1
comparación más del n+1 Ej : de i=1 a 3 son n pasos + la comparación cuando n es 4)
s= s+ i……. 2 pasosi = i +1 2 pasos n veces
goto while 1 paso
Total For : 1+ (n +1) + 5 n =6n+2
Complejidad
12
Practica 8 -Ej 3 : Definir la función de pasos
int sumatorio (int n){ int s, i;s = 0; // 1 paso
for (i=1; i<=n; i++) // 6n+2 pasoss = s + i;
return s; / 1 paso
}
T(n) = 6n + 4 El algoritmo sumatorio tiene una complejidad lineal del orden (n)
Los ciclos pueden estar en alto nivel o ser un for, entonces siempre lollevamos a un ciclo while
Complejidad
13
Practica 8 -Ej 6 : Doble ciclo
#define M 10#define N 20void suma_matrices(double a[M] [N], double b[M] [N], double c[M] [N]){int i,j;for (i=0; i<N; i++)
for (j=0; j<M; j++)c[i][j] = a[i][j] + b[i][j];
i=0 1 operación
while (i N) N+1 comparaciones
j=0 1 operación
while (j M) M+1 comparaciones
cij = aij + bij suma y asigna 2 operaciones
j= j+1 suma y asigna 2 operaciones M veces N veces
goto whilej 1 operación
i=i+1 suma y asigna 2 operaciones
goto whilei 1 operación
Ciclo interno : (M+1) + 5 M 6M+1
Ciclo externo : 1+ (N+1) + [1 + (6M+1) + 3] * N = 1+N+1+N+6 (M*N)+N+3N = 6 (M*N) + 6N + 2
T(n) = 6 (M*N) + 6N + 2
El algoritmo doble ciclo tiene una complejidad lineal del orden (n2)
Complejidad
14
Practica 8 -Ej 9 : For especial
FOR Variable IS RANGE n {STEP cte} NEXT Variable
Ejemplo: FOR a1 IS RANGE n {STEP 2} … NEXT a1
a1=0 1 paso
while (a1 menor n) itera n/2 veces (n/2 + 1 comparaciones)
a1= a1 + 2 suma y asigna 2 operaciones que se hacen (n/2) veces
goto while 1 operacion n/2 veces
Total : 1 + (n/2) + 1 + 3 (n/2) = 2 + 2n
T(n) = 2n + 2El algoritmo sumatorio tiene una complejidad lineal del orden (n)
Los ciclos pueden estar en alto nivel o ser un for, entonces siempre lollevamos a un ciclo while