¿Es una función que busca subsecuencias de dígitos de computable?

¿Cómo se puede decidir si $\pi$ tiene alguna secuencia de dígitos? me inspiró a preguntar si la siguiente variación de aspecto inocente es computable:

f (n) = {\begin{cases} 1 & if \bar{n} occurs in the decimal representation of π \\ 0 & otherwise \end{cases}

$f(n) = \begin{cases} 1 & \text{if $\bar n$ occurs in the decimal representation of $\pi$} \\ 0 & \text{otherwise} \\ \end{cases}$

donde $\bar n$ es la representación decimal de $n$ sin ceros a la izquierda.

Si la expansión decimal de $\pi$ contiene todas las secuencias de dígitos finitos (llamemos a esto un número universal (en base 10)), entonces $f$ es la constante $1$ . Pero esta es una pregunta matemática abierta. Si $\pi$ no es universal, ¿significa esto que $f$ es indiscutible?

computability real-numbers Gilles 'SO- deja de ser malvado'
fuente

el truco para el otro problema funciona porque es unario, ese truco no funcionará para verificar cadenas binarias. Pero eso no significa que no sea posible de otra manera.

Kaveh

@Kaveh ¿Qué quieres decir con "unario"? La pregunta vinculada consideró la representación decimal de

π

$\pi$ .

Raphael

Esta es una forma de hacer que el

π

$\pi$ -ejemplo sea incuestionable. La otra forma es dar un número real como entrada. Sin embargo, no tengo una prueba a mano.

Raphael

@Kaveh: También podríamos haber verificado sin cambiar la respuesta.

(01)^{n}

$(01)^n$

Raphael

@Raphael, puedes pensar que es esencialmente unario también. (Lo importante es la estructura de posibles cadenas para verificar la relación del prefijo wrt.)

Kaveh

Respuestas:

Tenga en cuenta que puede ser la constante incluso si no es un número normal. (En francés decimos si es constante que es un nombre univers . No sé el término correspondiente en inglés) $f$ $1$ $\pi$ $f$ $\pi$

Por lo que vale: podría ser , de la siguiente manera:

Probar es computable no implicaría necesariamente la resolución de la pregunta abierta si es constante o no. Por ejemplo, puede construir que sea computable pero de modo que la constancia de sea equivalente a la conjetura de Goldbach . $f$ $f$ $g$ $g$

Por supuesto, eso ni siquiera comienza a responder su pregunta, pero es probable que esté abierto para mí.

jmad
fuente

Correcto, me refería a nombre univers , de hecho. Entonces podría ser computable sin ser constante. Estoy bastante seguro de que hay una manera más simple de mostrar esto. ¿Podría explicar un poco más cómo puede o no ser computable, al nivel de la teoría de computabilidad 101?

f

$f$

f

$f$

Gilles 'SO- deja de ser malvado'

Bueno, quería responder a la pregunta "Dado que es una pregunta difícil , ¿ implica que ?" y mi respuesta es "¿Por qué no? Al menos no implica que es una pregunta trivial "

[f ? = 1

$[f?=1$

]

$]$

f \neq 1

$f≠1$

P (f)

$P(f)$

\neg P (f)

$¬P(f)$

[f ? = 1

$[f?=1$

]

$]$

jmad