¿Por qué hay más funciones no computables que computables?

Actualmente estoy leyendo un libro sobre algoritmos y complejidad. En este momento, estoy leyendo sobre funciones computables y no computables, y mi libro dice que hay muchas más funciones que no son computables que computables, de hecho, la mayoría no son computables, dice. En cierto sentido, puedo aceptar eso intuitivamente, pero el libro no proporciona una prueba formal ni elabora mucho sobre el tema.

Solo quería ver una prueba / dejar que alguien aquí lo explique / entienda más estrictamente por qué hay tantas más funciones no computables que computables.

computability turing-machines combinatorics hsalin
fuente

Al comparar dos conjuntos infinitos, la semántica de "más" debe revisarse.

Raphael

Respuestas:

El son numerable muchas funciones computables:

Cada función computable tiene al menos un algoritmo. Cada algoritmo tiene una descripción finita usando símbolos de un conjunto finito, por ejemplo, cadenas binarias finitas usando símbolos $\{0,1\}$ . El número de cadenas binarias finitas denotadas por $\{0,1\}^*$ es contable (es decir, el mismo número de números naturales $\mathsf{N}$ ).

Por lo tanto, puede haber como máximo muchas funciones computables. Hay al menos muchas funciones computables contables ya que para cada , la función constante es computable. $c\in \{0,1\}^*$ $f(x)=c$

En otras palabras, hay una correspondencia entre:

el conjunto de funciones computables
el conjunto de algoritmos
, el conjunto de cadenas finitas de , y $\{0,1\}^*$ $\{0,1\}$
, el conjunto de números naturales. $\mathbb{N}$

Por otro lado, hay innumerables funciones sobre las cadenas (o números naturales). Una función (o ) asigna un valor para cada entrada. Cada uno de estos valores se puede elegir independientemente de los demás. Entonces hay posible función. El número de funciones sobre números naturales es igual al número de números reales. $f:\mathbb{N} \to \mathbb{N}$ $f:\{0,1\}^* \to \{0,1\}^*$ $\mathbb{N}^\mathbb{N}=2^\mathbb{N}$

Dado que solo muchas funciones son computables, la mayoría de ellas no lo son. De hecho el número de funciones incomputables es también . $2^{\mathbb{N}}$

Si desea visualizar esto intuitivamente, piense en números naturales y números reales, o en cadenas binarias finitas y cadenas binarias infinitas. Hay muchos más números reales y cadenas binarias infinitas que números naturales y cadenas finitas. En otras palabras, (para una prueba de este hecho, ver el argumento diagonal de Cantor y la aritmética cardinal ). $\mathbb{N} < 2^\mathbb{N}$

Kaveh
fuente

¡Buena respuesta! Lo que no entiendo (podría estar perdiendo algo trivial aquí) es cómo obtienes

N^{N} = 2^{N}

$\mathbb{N}^\mathbb{N} = 2^\mathbb{N}$

hsalin

Es aritmética cardinal. Escribe los números naturales en una secuencia infinita de números naturales en binario, eso debería dar la intuición.

Kaveh

¿Por qué esta suposición es cierta: "Cada algoritmo tiene una descripción finita utilizando símbolos de un conjunto finito"? ¿Por qué un algoritmo no puede tener una descripción infinita?

Roland Pihlakas

@RolandPihlakas que es parte de la definición de un algoritmo (si lo prefiere, un programa de computadora).

Kaveh

Aquí hay una construcción "explícita" de innumerables funciones booleanas no computables. Sea una función booleana fija no computable, digamos la función característica del problema de detención. Considere el conjunto de funciones Cada no es computable y es incontable. $K$

F = {f : N \to {0, 1} : \forall x \in N, f (2 x) = K (x)} .

$F = \{ f \colon \mathbb{N} \to \{0,1\} : \forall x \in \mathbb{N}, f(2x) = K(x) \}.$

f \in F

$f \in F$

F

$F$

$R$

G = {g : N \to {0, 1} : \exists n \in N \forall m \geq n, g (m) = R (m) .}

$G = \{ g \colon \mathbb{N} \to \{0,1\} : \exists n \in \mathbb{N} \forall m \geq n, g(m) = R(m). \}$

g \in G

$g \in G$

R

$R$

G

$G$

G

$G$

Así que hay muchas funciones no computables ya que tenemos "infinitamente" grados de libertad: infinito real en lugar de infinito "potencial" como en el caso computable.

Yuval Filmus
fuente