Lógica y Computación

Autómatas y Computabilidad

PRIMERA PARTE

AUTOMATAS Y COMPUTABILIDAD

Departamento de Lógica - Facultad de Psicología - UCM

1

Lógica y Computación

Autómatas y Computabilidad

ESPECIFICACIÓN FORMAL DE PROCESOS • La matemática nos proporciona lenguajes para especificar (= definir, hablar de) procesos • El concepto clave para la definición matemática de procesos es el de algoritmo • Definición intuitiva de algoritmo: • Secuencia de operaciones que, aplicada correctamente a un problema de una clase determinada, genera la solución a ese problema en un tiempo finito • Existen varias formas de definición matemática de algoritmo: • • • •

Funciones recursivas (Gödel) Funciones λ-definibles (Church, Kleene) Algoritmos de Markov Teoría de Autómatas (Máquinas de Turing)

Departamento de Lógica - Facultad de Psicología - UCM

2

Lógica y Computación

Autómatas y Computabilidad

AUTÓMATAS Y COMPUTABILIDAD • Para la especificación matemática de procesos estudiamos tres teorías distintas: • Teoría de Autómatas • Computabilidad y Decidibilidad • Teoría de la Complejidad Computacional • La Teoría de Autómatas nos proporciona el lenguaje para la especificación de procesos algorítmicos • La Teoría de la Computabilidad y la Decidibilidad nos proporciona información acerca de los límites de la resolución algorítmica de problemas • La Teoría de la Complejidad Computacional nos proporciona estrategias de medida de la complejidad de cada tipo de proceso algorítmico

Departamento de Lógica - Facultad de Psicología - UCM

3

Lógica y Computación

Autómatas y Computabilidad

TEORÍA DE AUTÓMATAS

Departamento de Lógica - Facultad de Psicología - UCM

4

Lógica y Computación

Autómatas y Computabilidad

AUTOMATAS

• Un autómata es: • Una máquina (mecanismo) de naturaleza formal (Sólo existe como un mecanismo matemático)

• que acepta una información de entrada (input), • la procesa, (La somete a transformaciones simbólicas que pueden adoptar la forma de un cálculo o computación) • y genera un resultado o salida (output). • Definir un autómata equivaldrá a definir el proceso de transformación del input en un output, lo que equivale a definir una función cuyos argumentos son el input y cuyo valor es el output

Departamento de Lógica - Facultad de Psicología - UCM

5

Lógica y Computación

Autómatas y Computabilidad

TIPOS DE AUTOMATAS • Hay muchos tipos de autómatas • Cada tipo de autómata se asocia a una potencia computacional determinada, es decir, a una capacidad dada de resolución de problemas • De hecho, podemos clasificar los problemas algorítmicamente solubles asociándolos al tipo de autómata que los resuelve • Estos tipos se ordenan en una jerarquía de menor a mayor potencia computacional • Jerarquía de automátas: • Autómatas finitos (Redes Lógicas) • Autómatas intermedios: • Autómatas de memoria de pila • Autómatas de memoria linealmente limitada • Máquinas de Turing

Departamento de Lógica - Facultad de Psicología - UCM

6

Lógica y Computación

Autómatas y Computabilidad

TIPOS DE AUTOMATAS (2) • Además, podemos clasificar los autómatas: • Por el tipo de proceso que ejecutan: • Aceptación o reconocimiento • Generación • Por su tipo de causalidad: • Determinista • No-Determinista • Por el tipo de su almacenamiento de información: • De tamaño fijo • De tamaño creciente • De tamaño infinito • Por el tipo de la información que manejan • Discreta • Continua

Departamento de Lógica - Facultad de Psicología - UCM

7

Lógica y Computación

Autómatas y Computabilidad

TIPOS DE AUTOMATAS (3) • Autómatas aceptadores o reconocedores: • Resuelven problemas con respuesta si/no, que se modeliza normalmente como la identificación de dos estados finales, uno de aceptación y otro de rechazo • Autómatas generadores o transductores: • Construyen una respuesta específica (una salida) para el problema planteado • Autómatas deterministas: • La solución del problema viene unívocamente determinada por las entradas y los estados internos del autómata • Autómatas no-deterministas: • La respuesta no está unívocamente determinada

Departamento de Lógica - Facultad de Psicología - UCM

8

Lógica y Computación

Autómatas y Computabilidad

DESARROLLO DE LA TEORÍA DE AUTÓMATAS • • • • • • • • • • • • • •

Turing (1936) McCulloch, Pitts (1943) Kleene (1956) Shannon (1956) Moore (1956) Minsky (1956) Wang (1957) Sepherdson (1959) Rabin, D. Scott (1959) McNaughton, Yamada (1960) Rabin (1963) Chomsky (1963) McCarthy (1963) Hartmanis, Stearns (1965)

Departamento de Lógica - Facultad de Psicología - UCM

9

Lógica y Computación

Autómatas y Computabilidad

AUTÓMATAS FINITOS • Un autómata finito es un mecanismo cuya memoria es siempre finita. • Suponemos que la memoria del autómata está compuesta por un conjunto de unidades de retardación: entrada

salida

• En cualquier instante ti del proceso, posterior a t0: • salida(t) = entrada(ti-1), o, lo que es lo mismo: • entrada(t) = salida(ti+1). ( t : un instante de tiempo discreto) • Cada unidad de retardación almacena una unidad de información durante una unidad de tiempo. • El número de estos dispositivos es finito Definición: El estado interno en t de un autómata finito que ejecuta un proceso es el conjunto de los contenidos de la memoria del autómata finito en el instante t de ese proceso • Cada uno de los m estados internos distintos: q0, ..., qi, ..., qn • El conjunto de los estados internos: Q • q0 es el estado inicial y qn es un estado final • El número de estados internos es finito

Departamento de Lógica - Facultad de Psicología - UCM

10

Lógica y Computación

Autómatas y Computabilidad

AUTÓMATAS FINITOS (2) • A lo largo del proceso los contenidos de memoria del autómata van cambiando • Describiremos cómo se produce el cambio de estado a lo largo del tiempo definiendo una función de transición de estados, que nos dice cuál será el estado del autómata en el instante de tiempo siguiente • La función de transición de estados puede ser determinista (AFD) o no determinista (AFND) • En algunos casos desearemos describir la respuesta del autómata como una función de sus estados internos, y eventualmente, también de los estímulos que recibe: función de salida • Además, tenemos que especificar: • Su repertorio de símbolos, Σ, es decir, el conjunto de símbolos que podrán formar parte de sus entradas (y, eventualmente, de sus salidas) • El conjunto Q de sus estados internos posibles • Su estado inicial q0 • El conjunto F de sus estados finales, que es un subconjunto del conjunto de estados internos • Cada entrada (y salida) posible del autómata es una secuencia o cadena finita de símbolos de Σ • Σ* : el conjunto de cadenas finitas de símbolos de Σ • Σ* es un conjunto potencialmente infinito

Departamento de Lógica - Facultad de Psicología - UCM

11

Lógica y Computación

Autómatas y Computabilidad

AUTOMATAS FINITOS DETERMINISTICOS RECONOCEDORES O ACEPTADORES • Estructura: Dispositivo de lectura Cinta de entrada

Autómata Finito

• La cinta se mueve de izquierda a derecha • La cinta tiene escrito un símbolo en cada casilla • El conjunto de los símbolos de la cinta forma una secuencia de símbolos • El último símbolo de la cinta es un símbolo delimitador (*) • En cada instante t, el autómata lee un símbolo. • Cuando el autómata encuentre el símbolo *, se detendrá, terminando el proceso. • Conoceremos el resultado del proceso ejecutado inspeccionando el estado interno en que queda el autómata al final del proceso

Departamento de Lógica - Facultad de Psicología - UCM

12

Lógica y Computación

Autómatas y Computabilidad

AUTOMATAS FINITOS DETERMINISTICOS RECONOCEDORES O ACEPTADORES (2) Definición. Un autómata finito (determinístico) reconocedor es una estructura: AF = < Σ, Q, q0,ττ, F > tal que: • • • • •

Σ es el alfabeto de entrada Q es el conjunto de los estados q0 es el estado inicial τ es la función de transición de estados F es el conjunto de los estados finales [F ⊆Q]

• función de transición de estados τ:

τ:Q× Σ→Q • Esta función nos dice cuál será el estado del autómata en el instante de tiempo siguiente, en términos de su estado actual y su entrada actual: qt+1 = τ(qt, it)

Departamento de Lógica - Facultad de Psicología - UCM

13

Lógica y Computación

Autómatas y Computabilidad

AUTOMATAS FINITOS DETERMINISTICOS RECONOCEDORES O ACEPTADORES (3) • Puesto que tanto Q como I son finitos, podemos definir la función de transición de estados mediante una tabla de transición de estados: Estados en t q1 ... qm

Entradas en t i1 ... ik

Estados en t+1 q1 ... qm

• Para definir (el comportamiento de) un autómata concreto, especificaremos precisamente su función de transición de estados • Tendremos así un conjunto de instrucciones de la forma: • Estado: el estado en el que se está • Entrada: símbolo que se lee • NuevoEstado: el nuevo estado generado por la función de transición • Para cada estado interno, determinaremos, para cada símbolo de entrada posible, a qué otro estado interno pasa. • Si este nuevo estado es un estado final, el proceso se detiene. • El proceso comienza por el estado inicial

Departamento de Lógica - Facultad de Psicología - UCM

14

Lógica y Computación

Autómatas y Computabilidad

EJEMPLO 1 Especificación de un AFD que reconoce secuencias finitas no vacías de símbolos del alfabeto Σ = {0,1,*} que acaban en 1. El símbolo * se utiliza exclusivamente como símbolo de final de secuencia.Es decir, como estados finales tendremos: • un estado de aceptación ( qA), en el que ha de quedar el autómata si el último símbolo leído es un 1 • un estado de rechazo (qR). • Por tanto, en este caso, F = {qA,qR} • La secuencia de instrucciones que define este autómata consiste en una definición de la correspondiente tabla de transición de estados: q0,0,q1 q0,1,q2 q1,0,q1 q1,1,q2 q1,*,qR q2,0,q1 q2,1,q2 q2,*,qA • q1: el último símbolo leído es un 0 • q2: el último símbolo leído es un 1

Departamento de Lógica - Facultad de Psicología - UCM

15

Lógica y Computación

Autómatas y Computabilidad

EJEMPLO 1 (2) • El proceso puede representarse asimismo mediante un grafo cuyos nodos representan estados y cuyos arcos representan transiciones entre estados. • Cada arco se etiqueta con el símbolo leído que provoca la transición. • El inicio del proceso se marca mediante un arco de entrada al estado inicial. • De los estados finales no parte ningún arco.

0

qR

q1 * 0

0

1

q0 1

*

q2

qA

1

• Normalmente, utilizaremos el lenguaje de grafos.

Departamento de Lógica - Facultad de Psicología - UCM

16

Lógica y Computación

Autómatas y Computabilidad

EJEMPLO 2 • Autómata finito reconocedor que acepta secuencias finitas no vacías de símbolos del alfabeto Σ = {0,1,*} tales que contienen al menos una subsecuencia de la forma “010” (* = delimitador) • El grafo correspondiente es:

1

0

q0

0

0 q1

q2

qA

1

1 * *

* qR

• El estado q2 significa que los dos últimos símbolos leídos son “01” • No es necesario esperar al final de la secuencia para entrar en el estado de aceptación • q1 significa que el último símbolo leído es un 0. Por tanto, si se lee un 0, nos quedamos en el mismo estado.

Departamento de Lógica - Facultad de Psicología - UCM

17

Lógica y Computación

Autómatas y Computabilidad

EJEMPLO 3 • AFD que reconoce si el número de “1”s en la secuencia de entrada (finita y no vacía) es divisible por 3:

1

1

q0

1

q1

q2

1

q

1

qA

1

1

1 qR

Departamento de Lógica - Facultad de Psicología - UCM

18

Lógica y Computación

Autómatas y Computabilidad

AFD RECONOCEDORES CON MAS DE UNA CINTA DE ENTRADA • Los autómatas finitos reconocedores pueden manejar problemas en los que haya más de una secuencia de entrada. • Además, los estados finales de los autómatas reconocedores no necesariamente está limitado a dos • Ejemplo: especificar un AFD reconocedor, que, dadas dos secuencias de entrada, nos diga si ambas tienen la misma longitud, si la primera es más larga que segunda, o si la segunda es más larga que la primera. Supondremos que nuestro autómata, en cada instante del proceso, puede leer un símbolo de cada secuencia. Sea Σ = {1,*} (* delimitador)

• Alineamos las dos secuencias sobre la entrada del autómata, de forma que en el instante inicial del proceso t, el autómata recibe el primer símbolo de cada secuencia. Sea F = {q1,q2, q=}. Entonces: *1 q0

1* **

11

q1 q2 q=

Departamento de Lógica - Facultad de Psicología - UCM

19

Lógica y Computación

Autómatas y Computabilidad

AFDs TRANSDUCTORES O GENERADORES • En los autómatas transductores tenemos una salida explícita: Dispositivo de lectura Cinta de entrada Cinta de salida Dispositivo de escritura • Conocemos el resultado examinando la salida • Función de salida: caracteriza la salida de un autómata finito de una de dos formas: • En términos de sus estados internos y sus entradas: autómata de Mealy • En términos simplemente de sus estados internos: autómata de Moore • Normalmente, describiremos los AFDs transductores como autómatas de Mealy. • Tabla de salida de un autómata de Mealy: Entrada i1 ... in

Estado q1 ... qn

Departamento de Lógica - Facultad de Psicología - UCM

Salida o1 ... on

20

Lógica y Computación

Autómatas y Computabilidad

EJEMPLO 1 • Especificación de un AFD que, dada una secuencia finita no vacía de símbolos de {0, 1,*}, la convierte en otra en la que sustituye cada 1 por 0, y viceversa (* delimitador): • Etiquetamos cada arco con el par : Init 1/0

0/1 q0 */* qStop

• Existe un autómata de Moore correspondiente: cada nodo se etiqueta con el par , y la etiqueta del arco (entrada) es la que causa la transición Init 0 q0/0

q1/1 1

T. Por cada autómata de Mealy, existe otro de Moore que ejecuta la misma tarea, y viceversa.

Departamento de Lógica - Facultad de Psicología - UCM

21

Lógica y Computación

Autómatas y Computabilidad

Ejemplos de Autómatas Finitos (6) 4. Especificar un autómata que sume dos números en base 2. Ayuda: • Se trata de aplicar la tabla de la suma binaria: 0+0 = 0 0+1 = 1+0 = 1 1+1 = 10 • Suponemos que los dos números tienen igual número de dígitos (el más corto se iguala con el más largo añadiéndole 0’s por la izquierda) • Suponemos que en cada instante t el autómata lee el siguiente dígito más a la izquierda de cada número • En cada paso: • Los dos dígitos se suman de acuerdo con la tabla • Si hay arrastre previo, se suma también • Se toma nota del arrastre si lo hay • Cada salida depende de la entrada actual y del resultado anterior • En cada paso puede haber arrastre o no (dos estados) • Hay dos salidas posibles y cuatro entradas posibles 00/0

01/0 11/0

01/1

q1

q2

10/0

00/1 10/1

Departamento de Lógica - Facultad de Psicología - UCM

11/1

22

Lógica y Computación

Autómatas y Computabilidad

Autómatas Finitos no-determinísticos (AFND) • Son idénticos a los determinísticos, excepto en la forma de su función de transición de estados: τ : Q × Σ → ℘(Q) • A cada combinación estado/entrada no le corresponde unívocamente un estado sino uno de los posibles conjuntos de estados T. Para todo AFND, podemos construir un AFD que ejecuta la misma tarea Autómatas estocásticos o probabilistas • Función de transición probabilista:

τ = Σ*×Q → Q×[0,1] • Es una función que, para cada par , nos dice qué probabilidad hay de pasar a otro estado. • Para cada estado qj, hay una función:

τj = pj(i,qk) para todo k ≠ j donde: 0 ≤ pj(i,qk) ≤ 1 ∑i=1,n p(i,q) = 1

Departamento de Lógica - Facultad de Psicología - UCM

23

Lógica y Computación

Autómatas y Computabilidad

Autómata estocástico de estructura variable • Podemos añadir a la especificación del autómata probabilístico un algoritmo de actualización o refuerzo ρ que: • Toma como entrada: • La última probabilidad de transición aplicada • La última entrada • La última salida • Genera como salida una nueva probabilidad de transición • El cambio de las probabilidades de transición a lo largo del tiempo modeliza la “adaptación” o “aprendizaje adaptativo” del sistema: • “capacidad para mejorar la probabilidad de emitir una respuesta correcta como resultado de su interacción con el entorno”

Departamento de Lógica - Facultad de Psicología - UCM

24

Lógica y Computación

Autómatas y Computabilidad

Autómatas Intermedios • Son autómatas cuya potencia computacional es mayor que la de los autómatas finitos, pero menor que la de las Máquinas de Turing Autómatas linealmente limitados • Autómatas finitos que pueden utilizar como espacio de memoria intermedia un espacio como máximo igual al ocupado por la(s) cadena(s) de entrada (De hecho, es el mismo espacio) Autómatas de memoria de pila • “Pila” (Stack): Estructura de almacenamiento de datos que funciona según el principio LIFO (“Last Input, First Output”) • Los autómatas de memoria de pila son autómatas finitos con una memoria de pila potencialmente infinita, que utiliza para almacenar resultados intermedios

Departamento de Lógica - Facultad de Psicología - UCM

25

Lógica y Computación

Autómatas y Computabilidad

Máquinas de Turing I/O I

d i m b

Autómata Finito de Control • Cinta potencialmente infinita, que se utiliza para almacenar: • Los datos de entrada • Los datos de salida • Los resultados intermedios • Cada casilla de la cinta contiene cada uno de los símbolos del alfabeto Σ del problema (Supondremos que Σ = {1, 0}) • Al comienzo del proceso, la Máquina de Turing se encuentra situada sobre la primera casilla a la izquierda de la parte no-vacía de la cinta • El autómata finito de control tiene una entrada (I) y cuatro salidas (d, i, m, b) • La entrada I recibe en cada instante t el símbolo contenido en la casilla que se está examinando en ese instante

Departamento de Lógica - Facultad de Psicología - UCM

26

Lógica y Computación

Autómatas y Computabilidad

Máquinas de Turing (2) • En respuesta a esa información de entrada, el autómata finito de control genera una instrucción de actuación sobre la cinta: • Cuando activa la salida “d”, la Máquina de Turing se mueve a la derecha una casilla • Cuando activa “i”, se mueve una casilla a la izquierda • Cuando activa “m” (“marcar”), escribe un símbolo “1” en la casilla actual • Cuando activa “b” (“borrar”), escribe un “0” en la casilla actual • La definición puede variar en sus términos: • Alfabeto variado • Movimiento de la cinta, y no de la máquina • ... • (Def. )La Máquina de Turing se detiene en un instante t si, a partir t, la Máquina de Turing sigue examinando la misma casilla, sin producir ningún cambio en ella, y sin cambios de estado en el autómata finito de control • En cada instante t, la Máquina de Turing está en un estado dado (el de su autómata finito de control) • Cada operación de cambio de estado y de salida de la Máquina de Turing está determinada por una combinación

Departamento de Lógica - Facultad de Psicología - UCM

27

Lógica y Computación

Autómatas y Computabilidad

Máquina de Turing (3) • Resolver un problema equivale a computar una función cuyo valor es la solución del problema • (Def.) Una Máquina de Turing T computa una función f(a1, an) = v sii, representados en su cinta, en un instante t0, los argumentos a1, ..., an, se detiene en un instante ti ≥ t0, con v representado sobre su cinta • T es una Máquina de Turing “concreta”: sólo resuelve el problema para el que está diseñada • Si T computa una función f, decimos que f es Turingcomputable • Si un problema es Turing-computable, entonces es algorítmicamente soluble • A es un algoritmo sii el problema que A resuelve es resoluble mediante una Máquina de Turing • Tesis de Turing: La clase de las funciones efectivamente computables (funciones algorítmicas o algoritmos) puede identificarse con la clase de las funciones Turingcomputables

Departamento de Lógica - Facultad de Psicología - UCM

28

Lógica y Computación

Autómatas y Computabilidad

Especificación de Máquinas de Turing • Las Máquinas de Turing se definen en términos de quíntuplas: • Ejemplo: Especificación de una Máquina de Turing sumadora tal que: • cada número se representa mediante n+1 “1”s • los “0”s actúan como delimitadores • los dos sumandos están separados por un espacio en blanco (un “0”) • al final del proceso sólo debe quedar el resultado escrito sobre la cinta, con la cabeza de I/O posicionada sobre la casilla más a la izquierda de la parte no vacía de la cinta • Especificación en términos de quíntuplas: q110q2d q211q2d q201q3i q311q3i q300q4d q410q5d

Departamento de Lógica - Facultad de Psicología - UCM

29

Lógica y Computación

Autómatas y Computabilidad

Especificación de Máquinas de Turing (2) • Especificación de una Máquina de Turing que averigua si una secuencia cualquiera de “0”s y “1”s representada en su cinta es capicúa. • Se trata de un autómata reconocedor • Se supone que existe un tercer símbolo delimitador (“*”) • Deberá tener en cuenta si la secuencia tiene, o no, un número par de elementos • Si la secuencia es capicúa, al final del proceso la cinta estará vacía • Supongamos que la secuencia es par • Especificaremos el autómata mediante un grafo: 11d 00d

**i q2

q4

11d

1*i 1*d

q1

**d q7

11i q6

0*d

00i

00d

0*i q3

11d

q5 **i

00d • ¿Qué habría que hacer para tener en cuenta, además, el caso de las secuencias impares?

Departamento de Lógica - Facultad de Psicología - UCM

30

Lógica y Computación

Autómatas y Computabilidad

Máquina de Turing Universal • Una Máquina de Turing Universal (U) es una Máquina de Turing tal que: • Si, en t=0, representamos en su cinta: • una Máquina de Turing concreta • los datos de entrada a esa MT concreta • Entonces, en algún t > 0, se detendrá con la solución de la MT concreta representada en la cinta • La Máquina de Turing Universal imita o reproduce el comportamiento de cualquier Máquina de Turing concreta • Existen métodos de codificación (Por ej., la numeración de Gödel) que permiten representar una Máquina de Turing mediante: • Una codificación de las quíntuplas que definen su funcionamiento • Una codificación del estado en que se encuentra la Máquina de Turing • La Máquina de Turing Universal: Lee el estado en que se encuentra la MTuring concreta. Mientras no es el estado final: Lee el símbolo siguiente de la cadena de entrada Identifica cuál es la instrucción aplicable de la MTuring concreta Aplica la instrucción: Cambiando el estado de la MTuring concreta Generando la salida correspondiente Si lee el estado final, termina.

Departamento de Lógica - Facultad de Psicología - UCM

31

Lógica y Computación

Autómatas y Computabilidad

ESPECIFICACION DE MAQUINAS DE TURING MEDIANTE PROGRAMAS • El lenguaje de quintuplas nos da, para cada MT: • Una especificación de la función de transición de estados • Una especificación de la función de salida • Podemos hacer más explícita esa especificación transformando el lenguaje de quíntuplas en un programa, es decir, en una secuencia de instrucciones de actuación sobre la cinta. • Construiremos el programa como una secuencia de instrucciones formulada en términos de un lenguaje de programación L0 • Las instrucciones de nuestro lenguaje programación L0 tienen que ser suficientes para reproducir las instrucciones formuladas en el lenguaje de quíntuplas. • En general, cada instrucción de este lenguaje (qi,sl,se,qj,m) equivale a afirmar que: Si se está en qi, y se lee sl, entonces se realiza la siguiente secuencia de instrucciones: Escribir se Hacer el movimiento m Pasar al estado qj

Departamento de Lógica - Facultad de Psicología - UCM

32

Lógica y Computación

Autómatas y Computabilidad

MAQUINAS DE TURING COMO PROGRAMAS • Eliminaremos toda mención del estado interno del autómata finito de la siguiente forma: • Asignaremos a cada instrucción del programa un número de línea • Reformularemos la anterior expresión condicional de la siguiente forma: n n+1 n+2 . . . m m+1 m+2

Leer sl Si sl tiene el valor v, ir a la línea número m

Escribir se Hacer el movimiento m Ir a la línea número j (j será = n si no hay cambio de estado)

• De esta forma: • “Estar en un estado qi” significa ahora “Se va a ejecutar la instrucción número n” • “Pasar al estado qj” significa ahora “Ir a la instrucción número m y ejecutarla” • Puesto que la noción de “estado interno” desaparece, habrá que tener en cuenta que, ahora, tendremos que formular todos los autómatas aceptadores como transductores o generadores (es decir, la respuesta tendrá que reconocerse dejando escrito algo sobre la cinta). (Ejemplos más adelante)

Departamento de Lógica - Facultad de Psicología - UCM

33

Lógica y Computación

Autómatas y Computabilidad

MAQUINAS DE TURING COMO PROGRAMAS • Supondremos que: • La primera instrucción que se ejecuta es la primera instrucción del programa • Si no se cumple la condición, se ejecuta la siguiente instrucción n+1 • Todas las instrucciones se ejecutan en la secuencia en que aparecen en el programa, excepto si hay saltos (por una instrucción condicional o por una instrucción de salto explícito (como la de la línea m+2) • El programa contiene una línea de terminación. • La sintaxis de nuestro lenguaje de programación será la siguiente: LEER(s): Leer el símbolo s: s toma el valor del símbolo escrito en la casilla que se lee ESCRIBIR(s): Escribir el símbolo s: escribe el símbolo s en la casilla en la que la MT está colocada MOVERD: Moverse a la siguiente casilla a la derecha MOVERI: Moverse a la siguiente casilla a la izquierda SI s=v IR A n: Si el símbolo s tiene el valor v, ir a la instrucción número n. En otro caso, pasar a la instrucción siguiente IR A n: Saltar a la línea n PARAR: Línea de terminación del programa

• Equivalencia de las dos especificaciones alternativas de Máquinas de Turing:

• Cada instrucción básica de L0 es definible en términos de una secuencia de quíntuplas • Si P es un programa que especifica una MT, entonces existe una MT especificada en términos de quíntuplas que ejecuta P

Departamento de Lógica - Facultad de Psicología - UCM

34

Lógica y Computación

Autómatas y Computabilidad

EJEMPLOS DE ESPECIFICACION DE MTs MEDIANTE PROGRAMAS • Suponemos, como siempre, que al principio del proceso, la MT está posicionada sobre la casilla más a la izquierda de la parte no vacía de la cinta Ejemplo1: Sea S = {1,0,*}. Dada una secuencia cualquiera (no vacía) de símbolos {0,1}, delimitada por el símbolo “ * ”, especificar una MT generadora que cambie cada 0 por 1, y a la inversa: 1. LEER(s) 2. SI s = * IR A 9 3. SI s = 0 IR A 6 3. ESCRIBIR 0 4. MOVERD 5. IR A 1 6. ESCRIBIR 1 7. MOVERD 8. IR A 1 9. PARAR • Llamamos “bucle” una subsecuencia de instrucciones que se ejecutan reiteradamente • En el programa del Ejemplo 1 tenemos dos bucles: • De 1 a 5 • De 1 a 8 • Decimos que estos dos bucles están “anidados”: el primero se encuentra dentro del segundo Ejemplo 2: Sea S = {1,0,*}. Dada una secuencia cualquiera (no vacía) de símbolos {0,1}, delimitada por el símbolo “ * ”, especificar una MT reconocedora que averigüe si la secuencia es un palíndrome o no. Supondremos que la secuencia tiene un número par de símbolos. Si lo es, al final del proceso, la cinta contendrá un 1, y si no lo es, contendrá un 0:

Departamento de Lógica - Facultad de Psicología - UCM

35

Lógica y Computación

Autómatas y Computabilidad

1. LEER(s) 2. ESCRIBIR(*) 3. SI s = * IR A 36 (La cinta se ha quedado vacía. Es palíndrome) 4. SI s = 1 IR A 11 (Se ha leído un 1 en el extremo de la izquierda) 5. MOVERD (Se ha leído un 0 en el extremo de la izquierda. Empieza a moverse hasta llegar al extremo de la derecha) 6. SI s = * IR A 8 7. IR A 5 8. MOVERI 9. LEER(s) 10. IR A 19 11. MOVERD (Se ha leído un 1 en el extremo de la izquierda. Empieza a moverse hasta llegar al extremo de la derecha) 12. SI s = * IR A 14 13. IR A 11 14. MOVERI 15. LEER(s) 16. SI s = 0 IR A 27 (En el extremo de la derecha hay un 0. No es palíndrome) 17. ESCRIBIR(*) (En el extremo de la derecha hay también un 1. Se borra) 18. IR A 21 (Hay que volver al extremo de la izquierda) 19. SI s = 1 IR A 27 (En el extremo de la derecha hay un 1. No es palíndrome) 20. ESCRIBIR(*) (En el extremo de la derecha hay también un 0. Se borra) 21. MOVERI (Empieza a volver hacia la izquierda) 22. LEER(s) 23. SI s = * IR A 25 24. IR a 21 25. MOVERD (Ha llegado de nuevo al extremo de la izquierda) 26. IR A 1 27. ESCRIBIR(*) (No era palíndrome. Hay que borrar todo y escribir un 0) 28. MOVERI 29. LEER(s) 30. SI s = * IR A 33 31. ESCRIBIR(*) 32. IR A 28 33. ESCRIBIR(0) 34. IR A 36 35. ESCRIBIR(1) (Era un palíndrome) 36. PARAR

Departamento de Lógica - Facultad de Psicología - UCM

36

Lógica y Computación

Autómatas y Computabilidad

SUBRUTINAS • La instrucción “IR A n” (salto incondicional a la línea n) es, en realidad, una abreviatura de la siguiente secuencia de instrucciones: SI s = * IR A n SI s = 0 IR A n SI s = 1 IR A n • Para simplificar la programación, los fragmentos de programa que se repiten, realizando funciones idénticas, se pueden formular como un programa independiente, al que se llama “subprograma” o “subrutina” del programa principal. • Las subrutinas se llaman o invocan por su nombre cada vez que es necesario. • Ejemplo: en el programa anterior, las líneas siguientes se repiten, con idéntica estructura y función (Ir hasta el extremo derecho): • De la línea 5 a la 9 • De la línea 11 a la 15 • Escribiremos un nuevo programa: IR-EXTREMO-DERECHA 1. MOVERD 2. SI s = * IR A 14 3. IR A 11 4. MOVERI 5. LEER(s) • Cuando en el programa principal lleguemos al punto en que se requiere realizar estas acciones, simplemente crearemos una nueva línea en la que introduciremos el nombre de la subrutina. • La ejecución de esta línea equivale a la ejecución de toda la subrutina • Al final de la ejecución, se retorna a la línea siguiente del programa que ha invocado a la subrutina. • Podemos suponer que el anidamiento de programas y subrutinas es ilimitado

Departamento de Lógica - Facultad de Psicología - UCM

37

Lógica y Computación

Autómatas y Computabilidad

MAQUINA DE TURING UNIVERSAL • Una Máquina de Turing Universal (U) es una Máquina de Turing tal que: • Si, en t=0, representamos en su cinta: • una Máquina de Turing concreta • los datos de entrada a esa MT concreta • Entonces, en algún t > 0, se detendrá con la solución de la MT concreta representada en la cinta • La Máquina de Turing Universal imita o reproduce el comportamiento de cualquier Máquina de Turing concreta • Para construir una Máquina de Turing Universal necesitamos: • Una codificación o representación del programa que define la Máquina de Turing concreta • Una codificación o representación de los datos de entrada de la Máquina de Turing concreta • Un algoritmo, especificado como un programa, que, para cada instrucción del programa de la MT concreta, la ejecute sobre los datos correspondientes • Una codificación del número de instrucción que hay que ejecutar, y un contador que vaya actualizando este número. De esta forma representaremos el cambio de estados de la MT concreta • La Máquina de Turing Universal: • Lee en el contador el número de la siguiente instrucción. Mientras no es la última: • Lee el símbolo siguiente de la cadena de entrada • Identifica cuál es la instrucción aplicable de la MTuring concreta • Aplica la instrucción: • Cambiando el estado de la MTuring concreta • Generando la salida correspondiente

Departamento de Lógica - Facultad de Psicología - UCM

38

Lógica y Computación

Autómatas y Computabilidad

MAQUINAS DE REGISTROS • Una computadora digital (ordenador) es la realización física de una Máquina de Turing (universal) • Un modelo más realista se obtiene si sustituimos la cinta potencialmente infinita de la MT por un número finito pero potencialmente ilimitado de registros • Cada registro es un espacio de memoria que supondremos que puede almacenar: • Un número de cualquier longitud y tipo, o • Una cadena alfanumérica cualquiera, codificada numéricamente • Cada registro lleva asociado unívocamente un número, la dirección de ese registro • Un conjunto de registros, que comienza en una dirección dada, almacenará representaciones numéricas de las instrucciones del programa • Otro conjunto de registros almacena los datos sobre los que debe operar el programa • En general, las instrucciones se reformularán para que todas ellas se ajusten al formato: NúmeroInstrucción Operando [Operador1, ..., Operadorn] • Los operandos identifican la instrucción que se va a ejecutar • Los operadores son direcciones de registros en los que se guardan datos sobre los que se va a ejecutar la operación. En los lenguajes de programación se representan mediante variables.

Departamento de Lógica - Facultad de Psicología - UCM

39

Lógica y Computación

Autómatas y Computabilidad

DE LOS AUTOMATAS A LOS ORDENADORES • Un ordenador o computadora digital es la realización física de una Máquina de Registros -en último término, de una Máquina de Turing- Universal. • Cuando un ordenador ejecuta un programa, la máquina “universal” (que puede ejecutar cualquier programa o proceso computable) se convierte en una “máquina virtual” concreta. • Cada instrucción de los lenguajes de programación de alto nivel que se utilizan para programar ordenadores, es, en realidad, una macroinstrucción , es decir, una expresión que resume todo un conjunto más o menos complejo de operaciones elementales

Departamento de Lógica - Facultad de Psicología - UCM

40

Lógica y Computación

Autómatas y Computabilidad

Programas • Una macroinstrucción es una unidad lingüística que hace referencia, en último término, a una operación definible en términos de Máquina de Turing • Un lenguaje de programación es un conjunto de macroinstrucciones que puede ser utilizado para definir operaciones o procesos complejos • Hay lenguajes de programación de distintos niveles, de forma que los lenguajes de un nivel utilizan explícita o implícitamente macroinstrucciones del nivel inferior • Un programa es una secuencia finita de instrucciones tal que cada una de ellas es: • Una macroinstrucción de algún lenguaje de programación • Un subprograma (rutina o subrutina) formulada en ese mismo lenguaje • Una computadora digital (ordenador) es la realización física de una Máquina de Turing (universal) que ejecuta procesos definidos usualmente mediante programas escritos en lenguajes de programación de diferentes niveles • Cuando un ordenador ejecuta un programa, la máquina “universal” (que puede ejecutar cualquier programa o proceso computable) se convierte en una “máquina virtual” concreta. • Los ordenadores son relevantes en la Ciencia Cognitiva como herramienta de modelización (formulación de hipótesis) y contrastación.

Departamento de Lógica - Facultad de Psicología - UCM

41

Lógica y Computación

Autómatas y Computabilidad

ESPECIFICACIÓN DE ALGORITMOS • Para especificar la solución de un problema algorítmico: 1. Especificar el rango, posiblemente infinito, de todas las entradas admisibles 2. Especificar la salida deseada como una función de las entradas • Para especificar la salida como una función de las entradas, construir una secuencia finita de instrucciones tal que: • Cada instrucción prescribe que ha de realizarse una acción determinada • Cada instrucción ha de estar descrita mediante un lenguaje no ambigüo • La secuencia ha de tener un punto de terminación

Departamento de Lógica - Facultad de Psicología - UCM

42

Lógica y Computación

Autómatas y Computabilidad

LENGUAJE DE ESPECIFICACIÓN DE ALGORITMOS • El lenguaje de especificación de algoritmos utilizado en la máquina de Turing y en la máquina de registros es de “bajo nivel”: está muy alejado del lenguaje natural • En la modelización computacional suelen definirse los algoritmos mediante un lenguaje o pseudocódigo “de alto nivel” • Los lenguajes de alto nivel poseen, en general, cuatro tipos de instrucciones: • Declarativas: definen variables y sus tipos, clases de objetos, funciones: • entero(X) • es_una_lista(Y) • Expresiones: combinaciones de constantes, variables, operadores y funciones de acuerdo con reglas sintácticas precisas. • (5*3)+(3+2) • (X+Y)/25 • raiz2(X) • Ejecutables: Definen operaciones, flujos, asignaciones, llamadas a funciones o subrutinas: • • • •

sea A = 0 si (expresión) entonces (instrucción) escribir Z ejecutar prog1

• Comentarios Departamento de Lógica - Facultad de Psicología - UCM

43

Lógica y Computación

Autómatas y Computabilidad

LENGUAJE DE ESPECIFICACIÓN DE ALGORITMOS (2) • Para la construcción de la secuencia de instrucciones pueden utilizarse los siguientes recursos: • Secuenciación directa • Instrucciones condicionales: si (Condición), entonces (Instrucciones) • Iteración limitada: hacer (Instrucciones) n veces • Iteración condicional: mientras (Condición) hacer (Instrucciones) hacer (Instrucciones) mientras (Condición) hasta que (Condición) hacer (Instrucciones) hacer (Instrucciones) hasta que (Condición) • Una Condición es una expresión o una secuencia de expresiones unidas por operadores booleanos (Y, O, NO) • Las Instrucciones a ejecutar son, o bien una sola, o bien una secuencia de instrucciones. • Las iteraciones o bucles son necesarios para especificar procesos de longitud no prefijada

Departamento de Lógica - Facultad de Psicología - UCM

44

Lógica y Computación

Autómatas y Computabilidad

INSTRUCCIONES CONDICIONALES • Pueden tener una de las siguientes formas: si Condición entonces Instrucción o secuencia de instrucciones finsi si Condición entonces Instrucción o secuencia de instrucciones enotrocaso Instrucción o secuencia de instrucciones finsi si Condición entonces si Condición … finsi finsi • Si la Condición no se cumple, el control pasa a la instrucción siguiente al finsi • salir: Sale de una cadena de condicionales • Una cadena de condicionales puede expresarse más cómodamente como un conjunto de casos: seleccionar (Expresión) caso Valor1: Instrucción o secuencia de instrucciones … caso Valorn: Instrucción o secuencia de instrucciones enotrocaso: Instrucción o secuencia de instrucciones finseleccionar

Departamento de Lógica - Facultad de Psicología - UCM

45

Lógica y Computación

Autómatas y Computabilidad

ITERACIÓN LIMITADA hacer I desde J hasta K [intervalo L]] Instrucción1 ... Instrucciónn finhacer • Da sucesivos valores a la variable I, empezando por el valor J • El intervalo L fija la distancia entre los sucesivos valores de I (Si no se señala, por defecto es 1) • La iteración termina cuando I alcanza el valor K • Además: • salir: Sale de un bucle • continuar: Va a la siguiente iteración de un bucle ITERACION INFINITA hacer Instrucción1 ... Instrucciónn finhacer • Alguna de las instrucciones ha de ser salir

Departamento de Lógica - Facultad de Psicología - UCM

46

Lógica y Computación

Autómatas y Computabilidad

ITERACIÓN CONDICIONAL (1) • La iteración se ejecuta mientras que la expresión Condición es verdadera: mientras Condición [hacer]] Instrucción1 ... Instrucciónn finmientras • En la siguiente forma, se ejecuta al menos la primera vez: hacer Instrucción1 ... Instrucciónn mientras Condición finhacer

Departamento de Lógica - Facultad de Psicología - UCM

47

Lógica y Computación

Autómatas y Computabilidad

ITERACIÓN CONDICIONAL (2) • La iteración se ejecuta mientras que la expresión Condición es falsa: hasta que Condición [hacer]] Instrucción1 ... Instrucciónn finhasta • En la siguiente forma, se ejecuta al menos la primera vez: hacer Instrucción1 ... Instrucciónn hasta que Condición finhacer

Departamento de Lógica - Facultad de Psicología - UCM

48

Lógica y Computación

Autómatas y Computabilidad

SALTO INCONDICIONAL • Salto incondicional: ira Etiqueta • Etiqueta es una etiqueta o número de instrucción del programa • Hay que evitar su uso siempre que sea posible: • Dificulta la inteligibilidad de los algoritmos • Puede introducir ambigüedades

Departamento de Lógica - Facultad de Psicología - UCM

49

Lógica y Computación

Autómatas y Computabilidad

MANEJO DE SUBRUTINAS • El uso de subrutinas estructura y clarifica los algoritmos • Hay que utilizar subrutinas siempre que sea posible identificar la utilización reiterada del mismo procedimiento • Llamada a una subrutina o procedimiento: ejecutar Proc[[(Parámetros,Valor)]] • Proc es el nombre del procedimiento o subrutina que hay que ejecutar • La llamada puede llevar parámetros, mediante los cuales el procedimiento llamado recibe valores • Si el procedimiento llamado es una subrutina, su última instrucción es: regresar[[(Valor)]] • Si la subrutina debe devolver algún valor, llevará ese valor como argumento.

Departamento de Lógica - Facultad de Psicología - UCM

50

Lógica y Computación

Autómatas y Computabilidad

RECURSION • Recursión: Capacidad de un procedimiento para llamarse a sí mismo • Reducción del problema inicial a subproblemas más sencillos • En cada nueva invocación del procedimiento, los datos de entrada cambian • Al final del procedimiento, las soluciones parciales, obtenidas en cada ciclo del bucle recursivo se unen para formar la solución final • Ejemplo:Torres de Hanoi: Proc: Mover N de X a Y, utilizando Z 1. si N = 1, entonces escribir Mover X a Y. Terminar. 2. enotrocaso: 2.1. ejecutar Mover N-1 de X a Z, utilizando Y 2.2. escribir “Mover X a Y” 2.3. ejecutar Mover N-1 de Z a Y, utilizando X • Instrucciones de entrada/salida: leer Item escribir Item • Item puede ser una variable, una constante, un elemento de una estructura de datos, …

Departamento de Lógica - Facultad de Psicología - UCM

51

Lógica y Computación

Autómatas y Computabilidad

TIPOS DE DATOS • Los datos que manipulan los algoritmos son constantes de varios tipos: entero: 1, 0, 543, … decimal: 1.25, 0.000004, 47.36, … numero: un entero o decimal cadena: Secuencia de caracteres alfanuméricos que puede contener blancos. Suele escribirse entre comillas dobles. constante alfanumérica: Secuencia de caracteres alfanuméricos. Por convención, si empieza por mayúscula o contiene blancos, se escribe entre comillas simples. • Normalmente, los algoritmos se refieren a los datos mediante variables • Cada variable denota un dato de un tipo dado • Las variables pueden interpretarse como posiciones de memoria que almacenan datos • El dato al que cada variable se refiere es su valor • Las instrucciones de asignación dan un valor explícito a una variable: sea X = 34 sea Y = Expresión

Departamento de Lógica - Facultad de Psicología - UCM

52

Lógica y Computación

Autómatas y Computabilidad

CODIFICACION DE INFORMACIÓN ALFANUMERICA • En el nivel físico, los ordenadores sólo manipulan cadenas de símbolos 0,1. • La interpretación de estas cadenas como números codificados en notación binaria resulta inmediata. • Utilizando un esquema de codificación adecuado, también podemos interpretar estas cadenas de símbolos como: • caracteres alfabéticos (letras) • caracteres numéricos (cifras) • otros símbolos especiales • Uno de los esquemas de codificación más utilizados es el sistema de codificación ASCII. • Permite representar 128 (27) caracteres con siete bits (secuencias de 7 símbolos {0,1}) • Por ejemplo: A 4 ( f < ...

0001100 0100011 1000010 0110110 1100011

• Con cadenas de 8 símbolos (ASCII extendido) permite representar 256 caracteres

Departamento de Lógica - Facultad de Psicología - UCM

53

Lógica y Computación

Autómatas y Computabilidad

EXPRESIONES • Las constantes y variables se combinan con operadores para formar expresiones • Las expresiones pueden ser: • Aritméticas: • Operadores aritméricos: +, -,*, /, //, mod, exp, . . • Sus argumentos son constantes numéricas, u otras expresiones o funciones aritméticas • Pueden utilizarse para definir funciones aritméticas: función f(X,Y,Z) = (Y*(X exp 2))+Z o para asignar un valor a una variable: sea X = Y/ (Z mod X1) • Lógicas: • Operadores: = , >, < , >= , =< , < >, … • Sus argumentos son constantes numéricas o alfanuméricas, variables, o expresiones o funciones aritméticas, … • Toman como valor Verdadero o Falso • Se utilizan para expresar Condiciones • Además, suele contarse con funciones predefinidas: • De manipulación de cadenas (concatenación, …) • De conversión de tipo • …

Departamento de Lógica - Facultad de Psicología - UCM

54

Lógica y Computación

Autómatas y Computabilidad

ESTRUCTURAS DE DATOS • Un conjunto de datos se almacena formando una estructura • Diversas estructuras de datos: • • • • •

Vectores o listas Matrices o tablas Colas Pilas Arboles

• En algunos casos, es preciso declarar previamente el tamaño de la estructura de datos • Cada elemento de una estructura se identifica mediante: • El nombre de la estructura • Uno o más índices que indican la posición del elemento en la estructura • La estructura se puede recorrer iterativamente mediante bucles definidos sobre sus índices • Cada elemento identificado se puede manejar en una expresión como si fuera una variable

Departamento de Lógica - Facultad de Psicología - UCM

55

Lógica y Computación

Autómatas y Computabilidad

VECTORES Y LISTAS • Un vector es un conjunto finito de datos, dispuestos de forma que: • Hay un elemento, vect(1), que es el primero del vector vect. • Cada elemento, vect(n), del vector, excepto el primero, va precedido por otro elemento, vect(n-1), del vector • El índice o puntero del vector es el número que aparece como argumento del vector • En general, los vectores requieren una declaración explícita de tamaño (longitud) • Ejemplo: Procedimiento que incrementa en 1 cada número del vector vect = [5,43,57,58,34,27,15,2,1,1]] procedimiento Incrementar: dimension vect(10) hacer I desde 1 hasta 10 sea vect(I) = vect(I) + 1 finhacer fin Incrementar • ¡OJO!: Las siguientes expresiones no indican lo mismo: I+1 vect(I+1) vect(I)+1

Departamento de Lógica - Facultad de Psicología - UCM

56

Lógica y Computación

Autómatas y Computabilidad

LISTAS • Una lista es un vector que no requiere declaración explícita de tamaño • Las listas se estructuran en [Cabeza|RestoLista]] • Cabeza contiene el primer elemento de la lista • RestoLista es una lista • El último elemento de una lista es la lista vacía • Los elementos de una lista se suelen manejar con procedimientos recursivos • Ejemplo1: Procedimiento recursivo (Prolog) para comprobar la pertenencia de un elemento E a una lista L: procedimiento Pertenece Pertenece(E,[[E|_]]). Pertenece(E,[[_|L1]]) si Pertenece(E,L1). fin Pertenece • Ejemplo2: Procedimiento recursivo que incrementa en 1 cada elemento de la lista L = [5,43,57,58,34,27,15,2,1,1]] procedimiento Incrementa(ListaEntrada,ListaSalida) Incrementa([[],[[]). Incrementa([[Elemento|Lista]],[[Elemento1|Lista1]]) si sea Elemento1 = Elemento+1, Incrementa(Lista,Lista1). fin Incrementa

Departamento de Lógica - Facultad de Psicología - UCM

57

Lógica y Computación

Autómatas y Computabilidad

MATRICES O TABLAS • Vectores y listas son matrices unidimensionales • Los datos pueden situarse en una tabla o matriz bidimensional: pepe 25 1 logica aprobado ana 18 3 percepcion notable … … … … … juan 22 4 memoria suspenso • La posición de cada dato en una fila o columna dada indica de qué tipo de dato se trata • El tamaño de una tabla o matriz bidimensional se declara dando el número de filas y el número de columnas: dimension datos(50,5) • Para manejar los datos de una matriz nos referimos a cada elemento mediante sus índices de posición: • Ejemplos: datos(50,1) :el nombre de pepe datos(2,5) : la calificación de ana • Podemos utilizar matrices n-dimensionales (n>2)

Departamento de Lógica - Facultad de Psicología - UCM

58

Lógica y Computación

Autómatas y Computabilidad

COLAS Y PILAS • Una cola es una lista tal que: • Todo elemento añadido a ella se coloca como último elemento de la lista • Para extraer un elemento de ella, han de extraerse previamente los elementos que le anteceden • FIFO: First Input, First Output • Una pila es una lista tal que: • Todo elemento añadido a ella (push) se coloca como primer elemento de la lista • Para extraer un elemento de ella (pop), han de extraerse previamente los elementos que le anteceden • LIFO: Last Input, First Output • Se utilizan para almacenar los datos obtenidos en los sucesivos ciclos de los procedimientos recursivos

Departamento de Lógica - Facultad de Psicología - UCM

59

Lógica y Computación

Autómatas y Computabilidad

ARBOLES • Un árbol es un conjunto de datos ordenados jerárquicamente • Cada dato es un nodo del árbol • Cada nodo del árbol está unido al menos a otro nodo mediante una rama • Cada nodo puede ser: • El nodo raíz • Un nodo terminal • Un nodo no-terminal • Cada rama une el nodo raíz, o un nodo no terminal, con otro nodo, su sucesor inmediato • Si B es el sucesor inmediato de A, A es el antecesor inmediato de B • Un camino en el árbol es una lista de nodos del árbol tal que: • El primer nodo de la lista es el nodo raíz • El último nodo de la lista es un nodo terminal • Cada nodo de la lista, excepto el primero, es el sucesor inmediato del nodo que le precede en la lista • Un árbol binario es un árbol en el que cada nodo tiene como máximo dos sucesores

Departamento de Lógica - Facultad de Psicología - UCM

60

Lógica y Computación

Autómatas y Computabilidad

EJEMPLO • Procedimiento que genera un árbol binario a partir de una lista de números L, tal que, para cada nodo A: • Todos los nodos de su subárbol izquierdo son menores que A • Todos los nodos de su subárbol derecho son mayores que A procedimiento CreaArbol: sea A (el primer número de la lista L) el nodo raiz hacer sea B el siguiente elemento de la lista: sea C el nodo raíz hacer si B es menor que C, entonces: sea D el sucesor izquierdo de C si D es vacío, entonces B es el nuevo sucesor izquierdo de C. Salir enotrocaso, sea C = D finsi enotrocaso (B es mayor que C): sea D el sucesor derecho de C si D es vacío, entonces B es el nuevo sucesor derecho de C. Salir enotrocaso, sea C = D finsi finsi finhacer hastaque B = fin de la Lista finhacer fin CreaArbol

Departamento de Lógica - Facultad de Psicología - UCM

61

Lógica y Computación

Autómatas y Computabilidad

COMPUTABILIDAD Y DECIDIBILIDAD

Departamento de Lógica - Facultad de Psicología - UCM

62

Lógica y Computación

Autómatas y Computabilidad

Decidibilidad • Tesis de Turing: Un problema es decidible sii es computable (por una MTuring). En otro caso, es indecidible • La cuestión de si, para una clase dada de problemas, existe un algoritmo o procedimiento efectivo que los resuelva, se denomina problema de decisión • Decimos que un problema de decisión es indecidible si podemos demostrar que no existe ningún algoritmo que pueda responder a todas las preguntas que el problema pueda plantear • Ejemplos: • El problema “¿Hay enteros tales que satisfagan la ecuación 3x + 6y = 151?” (que tiene una respuesta negativa) no es un problema de decisión. • El problema “¿Hay enteros x, y tales que se cumple la ecuación ax + by = c?”, sí es un problema de decisión: • Para cada asignación de valores a los parámetros a, b, c, hay un problema distinto • Respuesta: • sí, si el máximo común divisor (mcd) de a y b divide a c • Tenemos el algoritmo de Euclides para hallar el mcd de dos números

Departamento de Lógica - Facultad de Psicología - UCM

63

Lógica y Computación

Autómatas y Computabilidad

El Problema de la Parada • Consideremos el siguiente problema de decisión: ¿Existe algún procedimiento efectivo (algoritmo o máquina de Turing) que nos permita determinar, para cualquier MT concreta representada en la cinta de la MTuring universal, si la MTuring concreta llegará a detenerse después de iniciar su computación? • Este problema tiene una respuesta negativa, por lo que se trata de un problema indecidible • Este resultado es equivalente a los obtenidos respecto a la Lógica Clásica de Primer Orden: • Gödel (1931): Cualquier sistema formal cuyo lenguaje sea lo suficientemente rico para describir las operaciones y relaciones básicas de la aritmética elemental es incompleto • La Aritmética de Peano, formalizada con la Lógica de Primer Orden con Identidad (y símbolos funcionales) y con axiomas específicos, es incompleta. • El conjunto de los enunciados verdaderos de la aritmética no es decidible • Church (1936): La Lógica de Primer Orden es indecidible • Consecuencias para las Ciencias Cognitivas: • Existen problemas elementales no decidibles • Pero los sujetos solucionan problemas muy complejos • Luego se requieren recursos de modelización no algorítmicos (heurísticos)

Departamento de Lógica - Facultad de Psicología - UCM

64

Lógica y Computación

Autómatas y Computabilidad

COMPLEJIDAD COMPUTACIONAL

Departamento de Lógica - Facultad de Psicología - UCM

65

Lógica y Computación

Autómatas y Computabilidad

Complejidad • No basta con el criterio de decidibilidad para establecer si una modelización cognitiva puede ser estríctamente algorítmica • Los recursos físicos utilizados en la solución de problemas (espacio y tiempo) son limitados • Ni siquiera todos los problemas decidibles son manejables • Podemos medir la complejidad de los algoritmos para estimar su manejabilidad • Los parámetros de medida son: • Tiempo de computación requerido (número de operaciones primitivas) • Espacio de memoria requerido: • Tamaño del input • Tamaño del output • Espacio requerido para almacenar resultados intermedias • La complejidad vendrá dada por el tiempo requerido para resolver el problema, dado como una función del tamaño del problema • Tipos de complejidad: • Polinómica (problemas “buenos”) • Exponencial (problemas “malos”)

Departamento de Lógica - Facultad de Psicología - UCM

66

Lógica y Computación

Autómatas y Computabilidad

Análisis de la Complejidad de un Algoritmo • Ejemplo: Complejidad de la Multiplicación • Sean dos enteros: • n, que tiene i dígitos • m, que tiene k dígitos • Para obtener m x n tenemos que obtener i filas que se sumarán • En cada fila tendremos aprox. j (≥ ≥ k) operaciones • Luego para obtener las i filas necesitamos, aproxim. , i x j operaciones • Finalmente, para sumar las filas necesitamos, aprox., i x j sumas de dos números de un dígito cada uno • Luego el tiempo de ejecución de toda la operación será proporcional a la ejecución de todas las operaciones • El número de operaciones es 2(i x j) • Luego la complejidad será proporcional al factor variable de esta expresión: i x j

Departamento de Lógica - Facultad de Psicología - UCM

67

Lógica y Computación

Autómatas y Computabilidad

La Medida de la Complejidad Algorítmica • Lo que resulta importante a la hora de medir la complejidad es su tasa funcional de crecimiento: • Esa tasa puede ser: • Lineal (buena) • Cuadrática (admisible en algunos casos) • Exponencial (no manejable) • ... • Los factores constantes se omiten • Denotación de la complejidad: O(f(n)) (La complejidad es proporcional a fn o “de orden f(n)) • Clasificación de los problemas respecto asu complejidad: • Problemas P: tienen algoritmos eficientes, con crecimiento polinómico • Problemas NP: • Es indemostrable que sean problemas P • Tienen un algoritmo eficiente (polinómico) de verificación de la solución • Problemas NP-completos: • No son problemas P ni NP • Si uno de la clase se solucionara mediante un algoritmo polinómico, todos tendrían un algoritmo de ese tipo • Problemas intrínsecamente difíciles: No son problemas P ni NP, y tienen algoritmos con tiempo exponencial

Departamento de Lógica - Facultad de Psicología - UCM

68

Lógica y Computación

Autómatas y Computabilidad

Los Algoritmos Básicos y su Complejidad • Algoritmos de Búsqueda: • Búsqueda Secuencial: • Dado un conjunto de n elementos, compara todos ellos con el buscado • En el peor caso (como máximo), n operaciones • Complejidad: O(n) • Búsqueda Binaria: • Requiere que el conjunto de elementos esté previamente ordenado • Peor caso: el primer valor entero k tal que 2k≥n, es decir k = log2 n • Complejidad: O(log2 n) • Algoritmos de Ordenación:

• ...

• Ordenación por Burbuja: • Número de comparaciones: 1/2 n (n-1) • Mejor caso: 0 • Peor caso: 3/2 (n2-n) • Caso medio: 3/4 (n2-n) • Complejidad: O(n2)

Departamento de Lógica - Facultad de Psicología - UCM

69