En teoría de la computabilidad funciones computables o funciones Turing-computables son los objetos básicos de estudio. Hacen nuestras nociones intuitivas de algoritmo presicas y según el tesis Church-Turing son exactamente las funciones que pueden ser calculados con una máquina de calculación. La noción de la computabilidad de una función puede ser relativizado a un conjunto arbitrario de números naturales A, o equivalentamente a una función arbitraria f de los naturales a los naturales, por medio de máquinas de Turing extendidas por un oracle por A o f. Tales funciones puede ser llamados A-computable o f-computable respectivamente. Antes la definición preciso de una función computable matemáticos solían usar el término informal efectivamente computable.
jueves, 28 de abril de 2011
6.3 FUNCIONES COMPUTABLES
Son una formalización de la noción intuitiva de algoritmo y según la Tesis de Church-Turing son exactamente las funciones que pueden ser calculadas con una máquina de cálculo. La noción de la computabilidad de una función puede ser relativizada a un conjunto arbitrario de números naturales A, o equivalentamente a una función arbitraria f de los naturales a los naturales, por medio de máquinas de Turing extendidas con un oráculo por A o f. Tales funciones puede ser llamados A-computable o f-computable respectivamente. Antes la definición precisa de una función computable los matemáticos usaban el término informal efectivamente computable
6.2 UN PROBLEMA SIEMPRE INSOLUBLE
El Arggone Natinla Laboratory demostró, en esencia, que de las ecuaciones de algebra de Robbins:
x _ y = y _ x
(x _ y) _ z = x _ (y_ z)
: ( : (x_y) _ : (x_:y)) = x
Implican las ecuaciones de algebre de Boole:
x _ y = y _ x
(x _ y) _ z = x _ (y_ z)
: ( : (x_y) _ : (x_:y)) = x
Asi se demostró ser capaz de razonar con ecuaciones matemáticas, de hacer demostraciones dentro de una teoría matemática.
x _ y = y _ x
(x _ y) _ z = x _ (y_ z)
: ( : (x_y) _ : (x_:y)) = x
Implican las ecuaciones de algebre de Boole:
x _ y = y _ x
(x _ y) _ z = x _ (y_ z)
: ( : (x_y) _ : (x_:y)) = x
Asi se demostró ser capaz de razonar con ecuaciones matemáticas, de hacer demostraciones dentro de una teoría matemática.
6.1 PROBLEMAS INSOLUBLES TEORIAS DE LENGUAJES
Sea el problema Palguna el siguiente problema:
Pacept: ¿Existe un procedimiento efectivo capaz de determinar si una máquina de Turing se detiene sobre alguna cadena?
Para demostrar que Palguna no es soluble, comenzaremos suponiendo que lo es, llegando de esta manera a un absurdo. Este absurdo tendrá lugar debido a que la solubilidad de Palguna implica la solubilidad de Pdet. Expresado de otra manera, demostramos que Pdet se reduce a Palguna. Demostración:
Supongamos que Palguna es un problema de decisión soluble. Al ser un problema soluble, entonces existe un procedimiento efectivo (o máquina universal de Turing), Alguna, que resuelve Palguna. Alguna toma como datos de entrada la descripción de una máquina de Turing T y determina en un tiempo finito si T se detiene sobre alguna cadena o no. Es decir Alguna recibe como entrada (T) y retorna un 1 si T se detiene para alguna cadena, mientras que devuelve la salida 0 si T no se detiene para ninguna cadena. Construyamos a partir de Alguna, un procedimiento efectivo (o máquina universal de Turing)
Unidad 6; REDUCIBILIDAD
• Se dice que un problema L1 se reduce en tiempo polinomial 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 para significar 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 problema P2 en tiempo polinomial determinístico.
Ejemplo
• Ordenar se reduce a encontrar el menor
TEMAS DE LA UNIDAD
5.3 TEORÍAS LÓGICAS
Una teoría lógica (TL) se define a partir de un conjunto de enunciados dados llamados axiomas, unas reglas de inferencia y un esquema de derivación. A partir de los axiomas y aplicando las reglas de inferencia y el esquema de derivación se infieren los teoremas de la teoría. El conjunto de teoremas de la teoría forman un lenguaje formal.
Si es posible definir una máquina de Turing tal que reconozca al lenguaje de los teoremas, este lenguaje es decidible y la teoría también lo es en consecuencia. Dicho en otras palabras, si el conjunto de teoremas visto como un lenguaje es reconocido por una máquina de Turing, entonces la TL es decidible. Y viceversa.
Puede hablarse entonces de manera indistinta de teorías lógicas o de lenguajes decidibles, como aquellos para los que existe una máquina de Turing capaz de reconocerlos. Luego, la correspondencia entre la sintaxis de una teoría lógica (lenguaje formal) y el reconocimiento simbólico de la mismo por parte de un autómata queda establecida.
Desde el punto de vista semántico, las interpretaciones de las cadenas del lenguaje se realizan ya sea por el intérprete ó bien por el compilador del lenguaje de programación en el cual se dan las instrucciones (ver Sección de Autómatas de Pila). Las cadenas que resultan en instrucciones realizadas por la computadora pueden considerarse interpretadas como verdaderas y por tanto tienen, al menos, un modelo de la Teoría Lógica formada por tales cadenas.
En particular, los axiomas se consideran teoremas de la teoría, los cuales se derivan aplicando cero veces las reglas de inferencia
No Computabilidad
Se ha visto que los algoritmos son un concepto fundamental de la ciencia de la computación y se ha desarrollado cierto conocimiento interno sobre la forma en que pueden construirse. Se sabe que existen algoritmos para tejer un suéter, construir un modelo de aeroplano, preparar un pastel y ejecutar una sonata de Beethoven. Es conocido que las computadoras pueden controlar señales de tráfico, líneas de producción y plantas químicas. Pueden llevar las revisiones de vuelos en líneas aéreas, controlar robots y producir nominas. Existen algoritmos para preparar una taza de café, determinar cual es el mayor de un conjunto de números, descubrir si un número es primo o no o no primo e imprimir el máximo común divisor de 2 números. Desde la época escolar se recuerda que existen algoritmos para sumar, resta, multiplicar y dividir números enteros y para calcular raíces cuadradas. Sin duda existen algoritmos para calcular logaritmos, determinar la frecuencia de las palabras en un fragmento dado de texto y controlar un submarino nuclear. Existen trabajos que las computadoras no pueden realizar. Hay muchas cosas que una computadora no puede hacer. En realidad, el número de cosas que pueden calcularse o computarse es infinitesimal en comparación con el número de cosas que a uno le gustaría calcular, las computadoras no pueden hacer muchas cosas.
5.2 EL PROBLEMA DE HALTING
El problema de halting o de paro consiste en determinar si una máquina de Turing cualquiera se detendrá ante cualquier entrada dada.
Es decir, si existe una máquina MTh capaz de determinar si cualquier otra máquina se va a detener o no. Es conocido que el problema del alto es indecidible.
5.1 LENGUAJES DECIDIBLES
Los lenguajes decidibles son cadenas de palabras calculables mediante funciones recursivas por lo cual también se les llamas lenguajes recursivos.
Un posible alfabeto sería, digamos, {a, b}, y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba .
Un lenguaje sobre este alfabeto, que incluyera esta cadena, sería: el conjunto de todas las cadenas que contienen el mismo número de símbolos que , por ejemplo
La palabra vacía (esto es, la cadena de longitud cero) se permite en este tipo de lenguajes, notándose frecuentemente A diferencia de que ocurre con el alfabeto (que es un conjunto finito) y con cada palabra (que tiene una longitud también finita), un lenguaje puede estar compuesto por un número infinito de palabras.
Unidad 5 ; DECIBILIDAD
* En lógica, el termino decidible se refiere a la existencia de un método efectivo para determinar si un objeto es miembro de un conjunto de fórmulas. Un sistema lógico o teoría es decidible sintácticamente si el conjunto de todas las formulas validas en el sistemas es decidible. Es decir, existe un algoritmo tal que para cada formula del sistema es capaz de decidir en un número finito de pasos si la fórmula es válida o no en el sistema.
TEMAS DE LA UNIDAD
Suscribirse a:
Entradas (Atom)