Fundamentos de la Computabilidad: Decidibilidad, Lenguajes Formales y Máquinas de Turing

Decibilidad: ||

N= "sobre la ent.. B es AFN y w cad} ||
3.Si N acept, acepte ||
F="Sobre la entra.., A y B son AFD's

Un lengua L es decidibl cuando ||
1.Convierta el AFN B para un || Teorema 4.4:
Edfa = {<A> | A es un AFD y L(A) =∅} ||
Sea L(c) = L(A) ⊗L(B)=

L aceptada por una MT, la MT no hay loop || AFD equivale C || T=sobre entrad <A> don A es un AFD || (L(A)∩L(B)^c) ∪ (L(A)^c ∩L(B))

Acepta si w perten a L, contrario rechaza ||
2. Ejecute la MT M del teo4.1 ||
1. Marca el estado inicial de A || (todo menos la intersección) 

Teorema4.1:

Aafd ={<B,w>| B es AFD q acep la cade w} || sobre <C,w> || 2.Repite hasta ningún nuevo estad sea marcado:

||

L(c)=⌀ si L(A)=L(B)

M=“Sobr la entr<B,w> B es un AFD, y w es una cad:

||

3. Si M acept, acepte ||
2.1 Marq cualquier estado q tenga una transici ||
1.Constru el AFD C

1. Simule B sobre la entrada w

|| Teorema4.3:

Arex ={<R,w> |R es una ER que describe w} || llegando en el a partir de cualq || con lo descrito

2. Si la simulación termi en aceptación, ||
P=sobre... R es ER y w una cad: 
|| estado q ya está marcado 3.Si ningún estado de ||
2.Ejecute la MT T del 

acepte. Si end en no-aceptación, rechace.”||
1.Convier la ER R para un AFN|| aceptac estuvi marcad, acep ||teore4.4 sobre <C>. 3.Si t acept,aceptar

Teorema4.2:

Anfa={<B, w>|B un AFN y B acepta w} ||
2. Ejecut la MT N sobre <B', w> || Teorema4.5:
EQdfa = {<A,B> | A y B son AFDs y L(A) = L(B)} || 

Teorema4.7:
Acfg= {<G,w> | G es GLC que genera la cadena w} || Teorema4.8 Ecfg = {<G> | G es una GLC y L(G) = ∅} || 1. Sea G un GLC para A

S = “Sobre la entrada <G,w>, don G es GLC y w es una cade: || R=Sobre <G>, donde G es GLC || 2.Ejecut MT S, q decide Acfg, sobre <G,w>

1.Conviert G para una GLC equival en la forma normal de chomsky || 1.Marca todos los simb terminales de G || 3. Si la MT S acepta,aceptar

->Eliminar épsilon, sustituir con versiones sin A -> Elimin A->B || 2.Repita hsta q no se marq new variables: ||INDECIBILIDAD:
Atm={⟨M,w⟩∣M es

reemplaza por todas las reglas de B en A -> Elimin A->aB, crea  || 2.1Marq cualq variabl A donde G tiene una producc || MT que acepta w}  

variable intermediaria -> Elimin A->BCD, reempla con new variables || A->U1 U2...UK y cada simb U1,...UK ya  || U= sobre<M,w>,....

Solo aceptan A->BC y A->a || haya sido marcad 3. Si la variabl inicial no esta marcada, acepte || 1. Simula M sobre w 2.Si M en algún moment

2. Liste todas la derivac con 2n-1 pasos, donde n es el tama de w,  || Teorema4.9:
todo LLC es decidible || entra en estad de aceptac,acepte

except si n=0; en ese caso liste todas las derivac de 1 paso || Sea A un LLC-> diseña una MT M q decide A.Construir || SI M entra en loop

3. Si alguna de las deriva gnera w, aceptar || una copia de G dentro de M: M=Sobre w  || sobr w. U es una MT universal

Teorema: Atm es indecidible || inyectiva: f(x)≠f(y) siempre q x≠y || y su complemento son Turing Reconocible

-Por contradicc Atm es decidible || sobreyectiva: si ∀z∈ B  ∃x∈ A tal q z=f(x) || 1. Si L es decidibl -> L y L^c son 

-H es una MT q decide Atm || cada elemt B tiene al menos uno de A || turing reconocibles

-Sobre <M,w>= H acepta si M acepta w || Biyectiva: si es inyectiv u sobreyectivo || 2. Si L y  L^c son turing reconocibles,

Crear D new MT que usa a H como subrutina || Definición: Dos conjun A y B tiene el  || entonces L es  decidible:

1. Ejecut H sobre <M,<M>> 2. Si H acepta, rechazar || mismo tam si existe biyecci f:A->B || 2.1 Hacemos M1 para L y M2 para

Si D(<M>)= acepte, si M no acepta <M> || Definición: Un conjunto A es contable si: || L^c -> ejecute ambos M1 y M2 sobre

Si D(<D>)= Acepta si D no acepta <D> || es finito o tiene el mismo tam de N={0,1,2,3...} || w en paralelo -> Si m1 Acepta

Método De diagonalizacion:  || Otra forma de probar decibilidad:  || acepte, si M2 acepta, rechazar

Si A yB son conjunto y f:A->B, decimos: || teorema: Un lenguaj es decidibl si y solo si el  || 

Teorema: Algunos lenguajes son turing irreconocibles

El conjunto L de todos los lenguajes es incontable

Conjunto B de todas las secuencias binarias es incontable

1.Mostrar biyección f:L->B

2.Cada lenguaj A∈L tiene una secuencia única en B, que

llamamo secuencias caracterisitica de A, Xa.

3.Sea ∑*={s1,s2,s3,...} 4.El i-ésimo bit de Xa es 1 si Si∈A y 0

caso contrario.