Ta
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Ta as PDF for free.
More details
- Words: 1,234
- Pages: 6
17/05/2007
Tema 13: Indecidibilitat Llenguatge Universal i Màquina Universal de Turing.
Llenguatge Universal
Definim el Llenguatge Universal com: Lu = {<M, ω>|amb ω acceptat per M}
Denominen Lu com el llenguatge format per qualsevol cadena particular de (0+1)* que serà acceptat per una màquina MT particular. Lu és recursivament enumerable. Lu no és recursiu.
1
17/05/2007
El Llenguatge Universal és recursivament enumerable
M’ : Màquina de Turing amb 3 cintes
1a cinta: és la d’entrada
El capçal és usat per a buscar els moviments de la MT Mi en rebre <Mi ω> coma entrada
2a cinta: simula la cinta de M
∑ = {0,1,B} Cada símbol de la cinta de M pot ser guardat en una cel·la de la segona cinta
Hem simplificat l’alfabet. Podria portar-se a terme per a qualsevol alfabet, però necessitaríem moltes cel·les de la 2a cinta de M’ per a simular-ne una de M
3a cinta: guarda l’estat de M amb qi representat amb 0i (Anomenarem a aquesta màquina Màquina Universal de Turing)
Llenguatge Universal no és recursiu.
Recordem:
Diem que si reduïm Ld a Lu ambdós son exemples de llenguatges recursius enumerables però no recursius
Ld no és recursiu enumerable Ld és recursiu
Ld = {ωi | Mi accepta ωi} Lu = {<M,ω> | M accepta ω}
Suposem un algoritme A que reconeix Lu, també reconeixerà Ld
Donada una cadena ω є (0+1)*, determinem el valor de i per tal que ω = ωi L’enter i és el determinant per a una MT Mi
2
17/05/2007
Llenguatge Universal no és recursiu
Si donem com a entrada <Mi,ωi> a l’algoritme A
S’acceptarà ω en M si i només si hi ha una Mi que accepti ωi
Esquema: Convertir
ω
SI A per a Lu
A per a Ld
Per tan A és un algorisme per Ld.
NO
No existeix un algorisme per Ld tal que s’accepti ω si només si ω = ωi є L(Mi) Com que A no existeix per a Ld, tampoc existeix un algoritme per a Lu
Conclusions:
Lu és un llenguatge recursiu enumerable però no recursiu
Màquina Universal de Turing.
Una MUT (Màquina Universal de Turing) és una màquina la cinta de la qual ha estat codificada amb una llista d’instruccions per a una màquina de Turing T concreta. La cinta ha estat codificada amb una sèrie de 0’s i de 1’s Aquest cinta s’utilitza com la part inicial de la MTU, que actua sobre una paraula d’entrada de la mateixa manera que actuaria T. Com que la cinta de la MTU pot ser configurada de la mateixa manera que la de qualsevol altre màquina de Turing, es podrà comportar com a aquesta màquina.
3
17/05/2007
Màquina Universal de Turing.
Hem de subratllar que aquest aspecte de l’obra de Turing és de vital importància, fins i tot més enllà de la teoria de la computació. En efecte, la idea de la màquina universal planteja, de manera abstracta, la possibilitat de dissenyar, o de trobar en la natura, un mecanisme autorregulador capaç d’imitar el comportament de qualsevol altre. Tot i que és impossible de construir a la pràctica, ja que requereix una cinta de memòria externa de longitud infinita, estableix el marc teòric que dona sentit a màquines més realistes que se’ls aproximen a la pràctica per tenir una gran quantitat de memòria.
La computació digital, constitueix un equivalent possible a la maquina universal: té una memòria limitada (en comptes d’una cinta infinita) i una velocitat de procés determinada. Tot i això, dintre d’aquests límits pot imitar, com la màquina de Turing, qualsevol alter màquina. Per altra banda, hi ha moltes raons de pes per a considerar que el cervell humà és, també, un exemplificació d’una màquina de Turing universal (evidentment, dintre dels límits de l’amplitud de memòria i de velocitat de procés).
Màquina Universal de Turing. Algorisme
Es tracta de simular amb la MUT el comportament de la M d’entrada. Pas 1
Comprovem el format de la 1a cinta: 111 ... 111 ω Inicialitzem la 2a cinta amb ω Inicialitzem la 3a cinta amb 0, que equival a dir que la inicialitzem a q1 (0i amb i = nº d’estat)
Si la comprovació del format no coincideix, la màquina s’atura: L(M) = Ø
Pas 2
Tenim els estats codificats de la següent manera: 0f10c10q10v10d11 Busquem el primer estat a la 1a cinta per acceptar el primer símbol
Pas 3
Avaluem l’estat i el símbol i actuem en conseqüència
Passem al següent estat L(M) = Ø
4
17/05/2007
Màquina Universal de Turing. Exemple
Sigui MTU = <111 010101010 11 0100100100 11 0100010010001000 111, 001>
Aclaració:
Evolució:
1
0
0 (c1)
-
q1
1
0 0 (es)
1
0 D
Format de la 1a cinta: Correcte 2a cinta: 001 3a cinta: 0 Llegim el 1r estat: 010101010 11 0100100100 11 0100010010001000 Actualitzem la 3a cinta amb el nou valor: 3aC 0 (q1 codificat) Estat de la paraula: 001
Repetició iterativa del pas 3
0
-
Pas 2+3
1
Pas 1
0 q1
Tornem a llegir el primer estat: 010101010 11 0100100100 11 0100010010001000 Actualitzem la 3a cinta amb el nou valor: 3aC 0 Estat de la paraula: 001
Repetició iterativa del pas 3
Llegim el segon estat: 010101010 11 0100100100 11 0100010010001000 Actualitzem la 3a cinta amb el nou valor: 3aC 0 Estat de la paraula: 001 00B (actualitzem el valor de la cinta)
Màquina Universal de Turing: Exemple
Sigui MTU = <111 010101010 11 0100100100 11 0100010010001000 111, 001>
Evolució:
Repetició iterativa del pas 3
Llegim el segon estat: 010101010 11 0100100100 11 0100010010001000
Actualitzem la 3a cinta amb el nou valor: 3aC 0
Estat de la paraula: 001 00B (actualitzem el valor de la cinta)
Repetició iterativa del pas 3
Llegim el primer estat: 010101010 11 0100100100 11 0100010010001000
Actualitzem la 3a cinta amb el nou valor: 3aC 0
Estat de la paraula: 00B
Repetició iterativa del pas 3
Llegim el primer estat: 010101010 11 0100100100 11 0100010010001000
Actualitzem la 3a cinta amb el nou valor: 3aC 00
Estat de la paraula: 00B
Com que hem acabat la paraula i hem passat per a q2 (en aquest cas, finalitzem en ell), direm que la paraula ha estat acceptada
5
17/05/2007
Exercici proposat
Exercici a entregar
Donada la MUT <111 01010001010 11 01001000010010 11 00010100001010 11 000100100001000100 11 0001000100010001000 11 00001010001000100 11 0000100100010010 111, ω> determinar si les següents paraules seran o no acceptades: (utilitzeu la següent codificació)
1100
0011
Donada la MUT <111 010101010 11 0100100010010 11 00010010010010 11 000100010010001000 111, ω> determineu si les següents paraules seran o no acceptades: (utilitzeu la següent codificació). Fer i entregar la taula de transicions.
111101
001
Codificació:
Estats
Moviments
Símbols
Q1
0
D
0
0
0
Q2
00
E
00
1
00
Q3
000
*
000
B
000
…
Llenguatge Universal Màquina Universal de Turing Francisco Gutiérrez Carles Hernández
6
Tema 13: Indecidibilitat Llenguatge Universal i Màquina Universal de Turing.
Llenguatge Universal
Definim el Llenguatge Universal com: Lu = {<M, ω>|amb ω acceptat per M}
Denominen Lu com el llenguatge format per qualsevol cadena particular de (0+1)* que serà acceptat per una màquina MT particular. Lu és recursivament enumerable. Lu no és recursiu.
1
17/05/2007
El Llenguatge Universal és recursivament enumerable
M’ : Màquina de Turing amb 3 cintes
1a cinta: és la d’entrada
El capçal és usat per a buscar els moviments de la MT Mi en rebre <Mi ω> coma entrada
2a cinta: simula la cinta de M
∑ = {0,1,B} Cada símbol de la cinta de M pot ser guardat en una cel·la de la segona cinta
Hem simplificat l’alfabet. Podria portar-se a terme per a qualsevol alfabet, però necessitaríem moltes cel·les de la 2a cinta de M’ per a simular-ne una de M
3a cinta: guarda l’estat de M amb qi representat amb 0i (Anomenarem a aquesta màquina Màquina Universal de Turing)
Llenguatge Universal no és recursiu.
Recordem:
Diem que si reduïm Ld a Lu ambdós son exemples de llenguatges recursius enumerables però no recursius
Ld no és recursiu enumerable Ld és recursiu
Ld = {ωi | Mi accepta ωi} Lu = {<M,ω> | M accepta ω}
Suposem un algoritme A que reconeix Lu, també reconeixerà Ld
Donada una cadena ω є (0+1)*, determinem el valor de i per tal que ω = ωi L’enter i és el determinant per a una MT Mi
2
17/05/2007
Llenguatge Universal no és recursiu
Si donem com a entrada <Mi,ωi> a l’algoritme A
S’acceptarà ω en M si i només si hi ha una Mi que accepti ωi
Esquema: Convertir
ω
SI A per a Lu
A per a Ld
Per tan A és un algorisme per Ld.
NO
No existeix un algorisme per Ld tal que s’accepti ω si només si ω = ωi є L(Mi) Com que A no existeix per a Ld, tampoc existeix un algoritme per a Lu
Conclusions:
Lu és un llenguatge recursiu enumerable però no recursiu
Màquina Universal de Turing.
Una MUT (Màquina Universal de Turing) és una màquina la cinta de la qual ha estat codificada amb una llista d’instruccions per a una màquina de Turing T concreta. La cinta ha estat codificada amb una sèrie de 0’s i de 1’s Aquest cinta s’utilitza com la part inicial de la MTU, que actua sobre una paraula d’entrada de la mateixa manera que actuaria T. Com que la cinta de la MTU pot ser configurada de la mateixa manera que la de qualsevol altre màquina de Turing, es podrà comportar com a aquesta màquina.
3
17/05/2007
Màquina Universal de Turing.
Hem de subratllar que aquest aspecte de l’obra de Turing és de vital importància, fins i tot més enllà de la teoria de la computació. En efecte, la idea de la màquina universal planteja, de manera abstracta, la possibilitat de dissenyar, o de trobar en la natura, un mecanisme autorregulador capaç d’imitar el comportament de qualsevol altre. Tot i que és impossible de construir a la pràctica, ja que requereix una cinta de memòria externa de longitud infinita, estableix el marc teòric que dona sentit a màquines més realistes que se’ls aproximen a la pràctica per tenir una gran quantitat de memòria.
La computació digital, constitueix un equivalent possible a la maquina universal: té una memòria limitada (en comptes d’una cinta infinita) i una velocitat de procés determinada. Tot i això, dintre d’aquests límits pot imitar, com la màquina de Turing, qualsevol alter màquina. Per altra banda, hi ha moltes raons de pes per a considerar que el cervell humà és, també, un exemplificació d’una màquina de Turing universal (evidentment, dintre dels límits de l’amplitud de memòria i de velocitat de procés).
Màquina Universal de Turing. Algorisme
Es tracta de simular amb la MUT el comportament de la M d’entrada. Pas 1
Comprovem el format de la 1a cinta: 111 ... 111 ω Inicialitzem la 2a cinta amb ω Inicialitzem la 3a cinta amb 0, que equival a dir que la inicialitzem a q1 (0i amb i = nº d’estat)
Si la comprovació del format no coincideix, la màquina s’atura: L(M) = Ø
Pas 2
Tenim els estats codificats de la següent manera: 0f10c10q10v10d11 Busquem el primer estat a la 1a cinta per acceptar el primer símbol
Pas 3
Avaluem l’estat i el símbol i actuem en conseqüència
Passem al següent estat L(M) = Ø
4
17/05/2007
Màquina Universal de Turing. Exemple
Sigui MTU = <111 010101010 11 0100100100 11 0100010010001000 111, 001>
Aclaració:
Evolució:
1
0
0 (c1)
-
q1
1
0 0 (es)
1
0 D
Format de la 1a cinta: Correcte 2a cinta: 001 3a cinta: 0 Llegim el 1r estat: 010101010 11 0100100100 11 0100010010001000 Actualitzem la 3a cinta amb el nou valor: 3aC 0 (q1 codificat) Estat de la paraula: 001
Repetició iterativa del pas 3
0
-
Pas 2+3
1
Pas 1
0 q1
Tornem a llegir el primer estat: 010101010 11 0100100100 11 0100010010001000 Actualitzem la 3a cinta amb el nou valor: 3aC 0 Estat de la paraula: 001
Repetició iterativa del pas 3
Llegim el segon estat: 010101010 11 0100100100 11 0100010010001000 Actualitzem la 3a cinta amb el nou valor: 3aC 0 Estat de la paraula: 001 00B (actualitzem el valor de la cinta)
Màquina Universal de Turing: Exemple
Sigui MTU = <111 010101010 11 0100100100 11 0100010010001000 111, 001>
Evolució:
Repetició iterativa del pas 3
Llegim el segon estat: 010101010 11 0100100100 11 0100010010001000
Actualitzem la 3a cinta amb el nou valor: 3aC 0
Estat de la paraula: 001 00B (actualitzem el valor de la cinta)
Repetició iterativa del pas 3
Llegim el primer estat: 010101010 11 0100100100 11 0100010010001000
Actualitzem la 3a cinta amb el nou valor: 3aC 0
Estat de la paraula: 00B
Repetició iterativa del pas 3
Llegim el primer estat: 010101010 11 0100100100 11 0100010010001000
Actualitzem la 3a cinta amb el nou valor: 3aC 00
Estat de la paraula: 00B
Com que hem acabat la paraula i hem passat per a q2 (en aquest cas, finalitzem en ell), direm que la paraula ha estat acceptada
5
17/05/2007
Exercici proposat
Exercici a entregar
Donada la MUT <111 01010001010 11 01001000010010 11 00010100001010 11 000100100001000100 11 0001000100010001000 11 00001010001000100 11 0000100100010010 111, ω> determinar si les següents paraules seran o no acceptades: (utilitzeu la següent codificació)
1100
0011
Donada la MUT <111 010101010 11 0100100010010 11 00010010010010 11 000100010010001000 111, ω> determineu si les següents paraules seran o no acceptades: (utilitzeu la següent codificació). Fer i entregar la taula de transicions.
111101
001
Codificació:
Estats
Moviments
Símbols
Q1
0
D
0
0
0
Q2
00
E
00
1
00
Q3
000
*
000
B
000
…
Llenguatge Universal Màquina Universal de Turing Francisco Gutiérrez Carles Hernández
6
