Decidabilidad del lenguaje de prefijo

9

A mitad de período había una variante de la siguiente pregunta:

Para un decidible, defina Muestre que no es necesariamente decidible. $L$
$Pref (L) = {x ∣ \exists y s.t. x y \in L}$ $\text{Pref}(L) = \{ x \mid \exists y \text{ s.t. } xy \in L\}$ $\text{Pref}(L)$

Pero si elijo entonces creo que también es , por lo tanto, decidible. También da el mismo resultado. Y dado que debe ser decidible, no puedo elegir el problema de detención o tal ... $L=\Sigma^*$ $\text{Pref}(L)$ $\Sigma^*$ $L=\emptyset$ $L$

¿Cómo puedo encontrar como no es decidible? $L$ $\text{Pref}(L)$
¿Qué condiciones en harán que decidible y cuál lo hará indecidible? $L$ $\text{Pref}(L)$

computability undecidability Sonó.
fuente

9

Tenga en cuenta que al usar un cuantificador existencial frente a un lenguaje decidible podemos obtener cualquier re lenguaje, es decir, cada lenguaje re se puede expresar como

{x \in Σ^{*} ∣ \exists y \in Σ^{*} ⟨ x, y ⟩ \in V}

$\{ x\in \Sigma^* \mid \exists y \in \Sigma^* \ \langle x,y \rangle \in V \}$

$V$

A_{T M} = {⟨ e, x ⟩ ∣ e encodes a Turing machine which accepts x}

$A_{TM} = \{ \langle e, x\rangle\ \mid \text{$e$ encodes a Turing machine which accepts $x$} \}$

$x$ $y$ $y$

Para la segunda pregunta, no existe una forma algorítmica general de verificar si los prefijos de un determinado lenguaje decidible son indecidibles. Esto se desprende del teorema de Rice.

Kaveh
fuente

V

$V$

A_{T M}

$A_{TM}$

2

y

$y$

M_{e}

$M_e$

x

$x$

V

$V$

y

$y$

M_{e}

$M_e$

x

$x$

Esa es una buena solución!

Ran G.

3

Metaconocimiento: desea encontrar un lenguaje no decidible que, sin embargo, tenga alguna propiedad computacional. Un lenguaje arbitrario no decidible probablemente no lo llevará muy lejos. Pero uno semi-decidible ...

$u$ $n$

u = f (n)

$u = f(n)$

Observe esta ecuación por un momento, teniendo en cuenta la capacidad de decisión y los prefijos.

$x$ $\mathrm{Pref}(L)$ $x a$ $x b$ $x a a$ $a,b,\cdots$ $\mathrm{Pref}(L)$ $\mathrm{Pref}(L)$ $S \subset \mathbb{N}$ $f$ $S$ $S = {f(x) \mid x\in\mathbb{N}}$

$0$ $1$ $:$ $\{\aleph,\beth\}$ $0$ $\aleph\aleph$ $1$ $\aleph\beth$ $:$ $\beth$ $n\in\mathbb{N}$ $\bar n$ $n$ $0$ $1$ $0$

$L = \{\bar y\mathord:\bar x \mid y = f(x)\}$ $S$ $L$ $:$ $0$ $f$ $\bar y$ $L$ $y$ $S$ $x$ $S$ $\mathrm{Pref}(L)$ $\mathrm{Pref}(L) \cap \{0,1\}^*\mathord: = S\mathord:$

Gilles 'SO- deja de ser malvado'
fuente

Decidabilidad del lenguaje de prefijo

Respuestas: