Problema de halting
Páginas: 3 (596 palabras)
Publicado: 24 de agosto de 2010
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 MThcapaz de determinar si cualquier otra máquina se va a detener o no. Es conocido que el problema del alto es indecidible.
El método de la Diagonalización
La prueba de la indecidibilidad delproblema de Halting utiliza una técnica llamada diagonalización, descubierta por el matemático Georg Cantor en 1873. Cantor estaba interesado con el problema de medir los tamaños de los conjuntosinfinitos.
Si tenemos dos conjuntos infinitos, ¿cómo podemos decir si uno es más grande que el otro o si son del mismo tamaño? Para conjuntos finitos, por supuesto, responder a estas preguntas es fácil.Nosotros simplemente contamos los elementos de un conjunto finito, y el número resultante es su tamaño.
Pero, si tratamos de contar los elementos de un conjunto infinito, ¡nunca terminaríamos!Así que no podemos utilizar el método de conteo para determinar los tamaños relativos de los conjuntos infinitos.
Por ejemplo, tomemos el conjunto de enteros pares y el conjunto de todas las cadenasde más de {0,1}. Ambos conjuntos son infinitos y, por lo tanto, más grande que cualquier conjunto finito, pero ¿uno de los dos es más grande que el otro? ¿Cómo podemos comparar su tamaño relativo?Cantor propuso una solución bastante buena a este problema. Observó que dos conjuntos finitos tienen el mismo tamaño si los elementos de un conjunto se pueden combinar con los elementos del otroconjunto.
Este método compara el tamaño sin tener que recurrir al conteo. Podemos extender esta idea para los conjuntos infinitos. Vamos a ver lo que significa mayor precisión.
Definición
Asumirque tenemos conjuntos A y B y una función ƒ desde A a B. Decimos que ƒ es uno a uno si no se asignan dos elementos diferentes a un mismo lugar, esto es si ƒ(a) ≠ ƒ(b) cuando a ≠ b.
Decimos que ƒ...
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 MThcapaz de determinar si cualquier otra máquina se va a detener o no. Es conocido que el problema del alto es indecidible.
El método de la Diagonalización
La prueba de la indecidibilidad delproblema de Halting utiliza una técnica llamada diagonalización, descubierta por el matemático Georg Cantor en 1873. Cantor estaba interesado con el problema de medir los tamaños de los conjuntosinfinitos.
Si tenemos dos conjuntos infinitos, ¿cómo podemos decir si uno es más grande que el otro o si son del mismo tamaño? Para conjuntos finitos, por supuesto, responder a estas preguntas es fácil.Nosotros simplemente contamos los elementos de un conjunto finito, y el número resultante es su tamaño.
Pero, si tratamos de contar los elementos de un conjunto infinito, ¡nunca terminaríamos!Así que no podemos utilizar el método de conteo para determinar los tamaños relativos de los conjuntos infinitos.
Por ejemplo, tomemos el conjunto de enteros pares y el conjunto de todas las cadenasde más de {0,1}. Ambos conjuntos son infinitos y, por lo tanto, más grande que cualquier conjunto finito, pero ¿uno de los dos es más grande que el otro? ¿Cómo podemos comparar su tamaño relativo?Cantor propuso una solución bastante buena a este problema. Observó que dos conjuntos finitos tienen el mismo tamaño si los elementos de un conjunto se pueden combinar con los elementos del otroconjunto.
Este método compara el tamaño sin tener que recurrir al conteo. Podemos extender esta idea para los conjuntos infinitos. Vamos a ver lo que significa mayor precisión.
Definición
Asumirque tenemos conjuntos A y B y una función ƒ desde A a B. Decimos que ƒ es uno a uno si no se asignan dos elementos diferentes a un mismo lugar, esto es si ƒ(a) ≠ ƒ(b) cuando a ≠ b.
Decimos que ƒ...
Leer documento completo
Regístrate para leer el documento completo.