View
19
Download
0
Category
Preview:
DESCRIPTION
Unidad 4 maquina de turing
Citation preview
7/17/2019 Unidad 4 maquina de turing
1/30
UNIDAD IV MQUINA DE TURING
INSTITUTO TECNOLGICO DE MINATITLN
PEA GARCA EVELIA
05231149 5 Seme!"e
TEORA DE LA COMPUTACIN
MC. JOS NGEL TOLEDO LVAREZ
ESTAD# DEL ARTE DE LA MQUINA DE TURING
7/17/2019 Unidad 4 maquina de turing
2/30
UNIDAD IV MQUINA DE TURING
MQUINA DE TURING
4.1 Definicin formal de una mquina de Turing.
Una mquina ! Tu"in# !$ un %i$&'$i(i)'* +'m' ,' !"an ,'$
au(-ma(a$ ini('$ ' ,'$ au(-ma(a$ a &i,a/ +'n m$ +a&a+ia!$ qu!0$('$. Di$&'n! (am1i0n ! un n2m!"' ini(' ! !$(a'$/ un' ! !,,'$ini+ia,/ 3 a,#un'$ ! !,,'$ ina,!$. Di$&'n! (am1i0n ! una +in(a/ qu!!$ una $u+!$i-n %'1,!m!n(! inini(a* ! %+!,a$*/ !n +aa una ! ,a$+ua,!$ 4a3 un $5m1','. La +in(a !$( ini+ia,m!n(! %!n 1,an+'* $a,)' !nuna &'"+i-n ini(a/ !n ,a qu! !$( a,ma+!naa ,a !n("aa. La mquina
! Tu"in# &u!! ,!!" 3 !$+"i1i" $5m1','$ !n ,a +in(a/ 3 m')!"$! a ,',a"#' ! !,,a !n am1'$ $!n(i'$. Pa"a !,,' i$&'n! ! una +a1!6a !,!+(u"a7!$+"i(u"a. Su '&!"a+i-n )i!n! !(!"minaa &'" $u un+i-n !("an$i+i-n.
7/17/2019 Unidad 4 maquina de turing
3/30
UNIDAD IV MQUINA DE TURING
E$(a +'n$(i(uia &'" ,'$ $i#ui!n(! !,!m!n('$8
MT 9 : E/ A/ ;/ !E 9 C'n?un(' ! !$(a'$/ n' )a+5'.A 9 C'n?un(' ! $5m1','$ ! !n("aa.; 9 C'n?un(' ! $5m1','$ au@i,ia"!$.!< 9 E$(a' ini+ia,.
= 9 C'n?un(' ! !$(a'$ ina,!$. 9 =un+i-n ! +'n("',/ !inia8
'n!8 8 : E 7 = > @ : A ; > B E @ : A ;> @ : I/ O/ D >
I 9 m')imi!n(' !, +a1!6a, a ,a i6qui!"a.
O 9 m')imi!n(' nu,'.D 9 m')imi!n(' a ,a !"!+4a.
Definicin formal de MT
7/17/2019 Unidad 4 maquina de turing
4/30
UNIDAD IV MQUINA DE TURING
La mquina ! Tu"in# +'n$(a ! un +a1!6a, ,!+('"!$+"i('" 3 una +in(ainini(a !n ,a qu! !, +a1!6a, ,!! !, +'n(!ni'/ 1'""a !, +'n(!ni' an(!"i'" 3
!$+"i1! un nu!)' )a,'". La$ '&!"a+i'n!$ qu! $! &u!!n "!a,i6a" !n !$(amquina $! ,imi(an a8
a)an6a" !, +a1!6a, ,!+('"!$+"i('" &a"a ,a !"!+4a.a)an6a" !, +a1!6a, ,!+('"!$+"i('" &a"a ,a i6qui!"a.
Definicin formal de MT
7/17/2019 Unidad 4 maquina de turing
5/30
UNIDAD IV MQUINA DE TURING
E, +-m&u(' !$ !(!"mina' a &a"(i" ! una (a1,a ! !$(a'$ !
,a '"ma8:!$(a'/ )a,'"> :nu!)' !$(a'/ nu!)' )a,'"/ i"!++i-n>
E$(a (a1,a ('ma +'m' &a"m!("'$ !, !$(a' a+(ua, ! ,amquina 3 !, +a"+(!" ,!5' ! ,a +in(a/ an' ,a i"!++i-n &a"a m')!" !,+a1!6a,/ !, nu!)' !$(a' ! ,a mquina 3 !, )a,'" a $!" !$+"i(' !n ,a
+in(a.
C'n !$(! a&a"a(' !@("!maam!n(! $!n+i,,' !$ &'$i1,! "!a,i6a"+ua,qui!" +-m&u(' qu! un +'m&u(a'" i#i(a, $!a +a&a6 ! "!a,i6a".
Definicin formal de MT
7/17/2019 Unidad 4 maquina de turing
6/30
UNIDAD IV MQUINA DE TURING
M!ian(! !$(a (0+ni+a $! &u!an !$a""',,a"$! maquina$ ! Tu"in#+'m&,!?a$ a &a"(i" ! 1,'qu!$ ! !,!m!n(a,!$ a &a"(i" ! maquina$ ma$&!qu!a$ m!ia$(! ia#"ama$ ! ("an$i+i'n!$.
La +'n$("u++i-n ! maquina$ ! Tu"in# $! ,,!)a a +a1' m!ian(!,'$ ia#"ama$ ! ("an$i+i-n 3 +'m1ina",'$ ! man!"a &a"!+ia a ,' qu! $!
"!a,i6a !n ,a '"ma+i-n ! ,a uni-n 3 +'n+a(!na+i-n ! ,'$ au(-ma(a$ini('$.
4.2 Construccin modular de una mquina de Turing.
7/17/2019 Unidad 4 maquina de turing
7/30
UNIDAD IV MQUINA DE TURING
Pasos para la construccin de una mquina de Turing
F.7E,imin! ,a$ +a"a+(!"5$(i+a$ ! ini+i' ! ,'$ !$(a'$ ini+ia,!$ ! ,a$maquina$/ !@+!&(' ,a ! aqu!, 'n! ini+ia"a ,a maquina +'m&u!$(a.
.7E,imin! ,a$ +a"a+(!"5$(i+a$ ! !(!n+i-n ! ,'$ !$(a'$ ! &a"aa! ('a$ ,a maquina$ ! in("'u6+a un nu!)' !$(a' ! &a"aa qu! n'$ $!!n+u!n("! !n nin#un' ! ,'$ ia#"ama$ qu! $! +'m1inan.
H.7Pa"a +aa un' ! ,'$ an(i#u'$ !$(a'$ ! &a"aa & 3 +aa @ !n 3.
4.2 Construccin modular de una mquina de Turing.
7/17/2019 Unidad 4 maquina de turing
8/30
UNIDAD IV MQUINA DE TURING
Ejemplificacin de dica construccin.
4.2 Construccin modular de una mquina de Turing.
7/17/2019 Unidad 4 maquina de turing
9/30
UNIDAD IV MQUINA DE TURING
Una mquina ! Tu"in# !$ un au(-ma(a qu! $! mu!)! $'1"! una$!+u!n+ia ,in!a, ! a('$. En +aa in$(an(! ,a mquina &u!! ,!!" un $','a(' ! ,a $!+u!n+ia :#!n!"a,m!n(! un +a"+(!"> 3 "!a,i6a +i!"(a$ a++i'n!$
!n 1a$! a una (a1,a qu! (i!n! !n +u!n(a $u !$(a' a+(ua, :in(!"n'> 3 !,2,(im' a(' ,!5'.
En("! ,a$ a++i'n!$ !$( ,a &'$i1i,ia ! !$+"i1i" nu!)'$ a('$ !n ,a$!+u!n+ia "!+'""!" ,a $!+u!n+ia !n am1'$ $!n(i'$ 3 +am1ia" !!$(a' !n("' ! un +'n?un(' ini(' ! !$(a'$ &'$i1,!$.
Mquina ! Tu"in# C'm&u!$(a
4.2 Construccin modular de una mquina de Turing.
7/17/2019 Unidad 4 maquina de turing
10/30
UNIDAD IV MQUINA DE TURING
Una mquina ! Tu"in# $! &u!! +'m&'"(a" +'m' un a+!&(a'"! un ,!n#ua?!. Si +','+am'$ una +a!na K !n ,a +in(a/ $i(uam'$ ,a
+a1!6a ! ,!+(u"a!$+"i(u"a $'1"! !, $5m1',' !, !@("!m' i6qui!"' ! ,a+a!na K 3 &'n!m'$ !n ma"+4a ,a mquina a &a"(i" ! $u !$(a'ini+ia,. En('n+!$ K !$ a+!&(aa $i/ !$&u0$ ! una $!+u!n+ia !m')imi!n('$/ ,a mquina ! Tu"in# ,,!#a a un !$(a' ina, 3 para. P'"(an(' K !$ a+!&(aa. Si qK KF&K &a"a a,#2n !$(a' ina, & 3 una$+a!na$ KF 3 K.
En('n+!$/ $! '1(i!n! ,a $i#ui!n(! !ini+i-n8
S!a M 9 :/ / / q una mquina ! Tu"in#. En('n+!$ !,,!n#ua?! a+!&(a' &'" M !$8 L:M> 9 K qFK KF&K &a"a &= 3
Ki .
4.! "enguajes aceptados por la MT.
7/17/2019 Unidad 4 maquina de turing
11/30
UNIDAD IV MQUINA DE TURING
L'$ ,!n#ua?!$ '"ma,!$ qu! $'n a+!&(a'$ &'" una mquina !Tu"in# $'n !@a+(am!n(! aqu!,,'$ qu! &u!!n $!" #!n!"a'$ &'" una
#"am(i+a '"ma,. E, +,+u,' Lam1a !$ una '"ma ! !ini" un+i'n!$.La$ un+i'n!$ qu! &u!!n $! +'m&u(aa$ +'n !, +,+u,' Lam1a $'n!@a+(am!n(! aqu!,,a$ qu! &u!!n $!" +'m&u(aa$ +'n una mquina !Tu"in#.
E$('$ ("!$ '"ma,i$m'$/ ,a$ mquina$ ! Tu"in#/ ,'$ ,!n#ua?!$
'"ma,!$ 3 !, +,+u,' Lam1a $'n '"ma,i$m'$ mu3 i$5mi,!$ 3 u!"'n!$a""',,a'$ &'" i!"!n(!$ &!"$'na$. Sin !m1a"#'/ !,,'$ $'n (''$!qui)a,!n(!$ 3 (i!n!n !, mi$m' &'!" ! !@&"!$i-n. G!n!"a,m!n(! $!('ma !$(a n'(a1,! +'in+i!n+ia +'m' !)i!n+ia ! qu! ,a (!$i$ !C4u"+47Tu"in# !$ +i!"(a/ qu! ,a ai"ma+i-n ! qu! ,a n'+i-n in(ui(i)a !a,#'"i(m' ' &"'+!imi!n(' !!+(i)' ! +-m&u(' +'""!$&'n! a ,a n'+i-n
! +-m&u(' !n una mquina ! Tu"in#.
4.! "enguajes aceptados por la MT.
7/17/2019 Unidad 4 maquina de turing
12/30
UNIDAD IV MQUINA DE TURING
-G"am(i+a$ !$("u+(u"aa$ &'" "a$!$8Pa"(! i6qui!"a ! ,a$ "!#,a$8 +'m1ina+i-n ! $5m1','$
(!"mina,!$ 3 n' (!"mina,!$/ +'n a, m!n'$ un n' (!"mina,.
Pa"(! !"!+4a ! ,a$ "!#,a$8 +'m1ina+i-n ! $5m1','$ (!"mina,!$ 3
n' (!"mina,!$ ! +ua,qui!" ,'n#i(u :in+,u$' .
7 La$ mquina$ ! Tu"in# a+!&(an ,!n#ua?!$ !$("u+(u"a'$ &'""a$!$.
4.! "enguajes aceptados por la MT.
7/17/2019 Unidad 4 maquina de turing
13/30
UNIDAD IV MQUINA DE TURING
a3 '("a$ !ini+i'n!$ ! ,a$ mquina$ ! Tu"in# qu! $'n!qui)a,!n(!$. A,#un'$ ! !$'$ m'!,'$ a,(!"na(i)'$ $'n mu+4' m$+'m&,i+a'$ aunqu! (''$ (i!n!n ,a mi$ma &'(!n+ia +'m&u(a+i'na, :' !+,+u,'>. Mu+4a$ ! !,,a$ '(an ! ma3'" ,!@i1i,ia a, i$!' ! una
mquina ! Tu"in# qu! "!$u!,)a un &"'1,!ma !n &a"(i+u,a". .
4.4 #ariantes de una mquina de Turing.
7/17/2019 Unidad 4 maquina de turing
14/30
UNIDAD IV MQUINA DE TURING
Mquina de Turing con Directi$a de Permanecer
R!+u0"!$! qu! ,a mquina ! Tu"in# $!n+i,,a $i(2a ,a +a1!6a !,!+(u"a!$+"i(u"a $'1"! !, &"im!" ; qu! 4a3a a ,a i6qui!"a ! ,a &'$i+i-na+(ua,. Pa"a 4a+!",'/ 1u$+a u!"a ! ,a +!,a a+(ua, 3 "!("'+!!. E$(' !$!1i' a ,a !ini+i-n '"i#ina, qu! "!qui!"! qu! &'" +aa ("an$i+i-n $!mu!)a ,a +a1!6a ! ,a +in(a.
La un+i-n ! ("an$i+i-n !$(a1a !inia +'m'8
8 @
@ @ R/L3 &u!! $!" m'ii+aa +'m'8 8 @ @ @ R/ L/ S 'n! S
$i#nii+a %&!"man!+!"*/ !$ !+i" n' m')!" ,a +a1!6a ! ,!+(u"a!$+"i(u"a.
P'" (an(' :q/ >9:&/ Q/ S> $i#nii+a qu! $! &a$a !, !$(a' q a, &/ $!
!$+"i1!
Q !n ,a +!,a a+(ua, 3 ,a +a1!6a $! qu!a $'1"! ,a +!,a a+(ua,.
4.4 #ariantes de una mquina de Turing.
7/17/2019 Unidad 4 maquina de turing
15/30
UNIDAD IV MQUINA DE TURING
4.4 #ariantes de una mquina de Turing.
Mquina ! Tu"in# Mu,(i&i$(a
E$ aqu!,,a m!ian(! ,a +ua, +aa +!,a ! ,a +in(a $! i)i! !n
$u1+!,a$. Caa $u1+!,a !$ +a&a6 ! +'n(!n!" $5m1','$ ! ,a +in(a. La+in(a (i!n! +aa +!,a $u1i)iia !n ("!$ $u1+!,a$. S! i+! qu! !$(a+in(a (i!n! m2,(i&,!$ &i$(a$. Pu!$(' qu! +aa +!,a ! !$(a mquina !Tu"in# +'n(i!n! m2,(i&,!$ +a"a+(!"!$/ !, +'n(!ni' ! ,a$ +!,a$ ! ,a+in(a &u!! $!" "!&"!$!n(a' m!ian(! n7(u&,a$ '"!naa$. En !, !?!m&,'an(!"i'"/ ,a$ +!,a$ ! ,a +in(a +'n(i!n!n :;/ a/ a>/ :1/ a/ a> 3 :1/ 1/ ;>. P'"(an('/ ,'$ m')imi!n('$ qu! "!a,i+! !$( mquina !&!n!"n ! $u!$(a' a+(ua, 3 ! ,a n7(u&,a qu! "!&"!$!n(! !, +'n(!ni' ! ,a +!,aa+(ua,.
7/17/2019 Unidad 4 maquina de turing
16/30
UNIDAD IV MQUINA DE TURING
Una mquina ! Tu"in# mu,(i&i$(a n' (i!n! m$ &'(!n+ia qu!,a mquina ! Tu"in# '"i#ina,. Sin !m1a"#'/ 4a+! qu! $!a m$ +i,,a +'n$("u++i-n ! mquina$ ! Tu"in# qu! "!$u!,)an +i!"('$&"'1,!ma$.
4.4 #ariantes de una mquina de Turing.
: Qn-->Q({L,R})n
7/17/2019 Unidad 4 maquina de turing
17/30
UNIDAD IV MQUINA DE TURING
Mquina de Turing de Cinta infinita en una Direccin
Mquina ! Tu"in# qu! u$a una +in(a qu! $! !@(i!n! inini(am!n(! !nuna 2ni+a i"!++i-n. G!n!"a,m!n(!/ $! (i!n! una +in(a qu! $! !@(i!n!inini(am!n(! 4a+ia ,a !"!+4a. N' !$( &!"mi(i' "!a,i6a" nin#2nm')imi!n(' 4a+ia ,a i6qui!"a a &a"(i" ! ,a +!,a !, !@("!m'i6qui!"'.
D!$! ,u!#'/ +ua,qui!" mquina ! Tu"in# ! !$(a '"ma&u!! $!" $imu,aa &'" una ! ,a$ qu! "!$&'n!n a ,a !ini+i-n'"i#ina,. Pa"a +aa +'m&u(a+i-n/ $im&,!m!n(! $! ma"+a una ! ,a$+!,a$ ! ,a +in(a inini(a &'" ,'$ '$ ,a'$/ +'m' ,a +!,a qu! $!!n+u!n("a !n !, ,5mi(! i6qui!"'.
4.4 #ariantes de una mquina de Turing.
7/17/2019 Unidad 4 maquina de turing
18/30
UNIDAD IV MQUINA DE TURING
Mquina de Turing en Dos Direcciones
Una mquina ! Tu"in# +'n una +in(a inini(a !n un $!n(i' &u!!$imu,a" una mquina ! Tu"in# +'n ,a +in(a inini(a !n ,'$ '$ $!n(i'$&!"' +'n '$ &i$(a$. S!a Muna mquina ! Tu"in# +'n una +in(a inini(a!n ,'$ '$ $!n(i'$.
La mquina ! Tu"in# MQ/ qu! (i!n! una +in(a inini(a !n un$!n(i'/ &u!! $imu,a" a M$i (i!n! una +in(a +'n '$ &i$(a$. La +in(a$u&!"i'" +'n(i!n! ,a in'"ma+i-n +'""!$&'ni!n(! a ,a &a"(! !"!+4a ! ,a+in(a M/ a &a"(i" ! un &un(' ! "!!"!n+ia a'. La &i$(a in!"i'" +'n(i!n!,a &a"(! i6qui!"a ! ,a +in(a M:!n '"!n in)!"$'>.
4.4 #ariantes de una mquina de Turing.
7/17/2019 Unidad 4 maquina de turing
19/30
UNIDAD IV MQUINA DE TURING
Mquina de Turing Multicinta
La mquina ! Tu"in# mu,(i+in(a (i!n! )a"ia$ +in(a$/ +aa una ! ,a$ +ua,!$ (i!n! $u&"'&ia +a1!6a ! ,!+(u"a!$+"i(u"a. La$ +a1!6a$ ! ,!+(u"a!$+"i(u"a $! +'n("',an
in!&!ni!n(!m!n(! :!$ !+i"/ a, mi$m' (i!m&'/ n' (i!n!n qu! m')!"$! !n ,ami$ma i"!++i-n/ ni "!a,i6a" !, mi$m' n2m!"' ! m')imi!n('$/ ni in+,u$'/ 4a+!"naa a ,a )!6>.
Cam1ia ! !$(a' !&!ni!n' !, !$(a' a+(ua, 3 !, +'n(!ni' ! ,a$ +!,a$! ('a$ ,a$ +in(a$/ qu! !$(n ana,i6an' a+(ua,m!n(! ,a$ +a1!6a$ !,!+(u"a!$+"i(u"a.
E$+"i1!n un nu!)' $5m1',' !n +aa una ! ,a$ +!,a$ 1a""ia$ &'" $u$ +a1!6a$! ,!+(u"a!$+"i(u"a.
Mu!)! +aa una ! $u$ +a1!6a$ 4a+ia ,a i6qui!"a ' 4a+ia ,a !"!+4a :! '"main!&!ni!n(! a, "!$(' ! ,a$ +a1!6a$>.
P'" (an('/ ,a un+i-n ! ("an$i+i-n &a"a una mquina ! Tu"in# +'n n +in(a$/ !$! ,a '"ma 8 @ n @ n @ R/ L n 'n! una ("an$i+i-n ! ,a '"ma :q/:F/ // n>> 9 :&/:F/ / / n>/ :F/ / / n>> $i#nii+a qu! +am1ia !,!$(a' q a &/ "!!m&,a6a
i&'"
i!n ,a +in(a i3 mu!)! ,a +a1!6a ! ,a +in(a i !n ,a
4.4 #ariantes de una mquina de Turing.
7/17/2019 Unidad 4 maquina de turing
20/30
UNIDAD IV MQUINA DE TURING
Mquina de Turing Muldimensional.
La mquina ! Tu"in# mu,(iim!n$i'na, !$ aqu!,,a qu! &!"mi(! qu! ,a+in(a (!n#a mu+4a$ im!n$i'n!$. P'" !?!m&,'/ una +in(a ! '$im!n$i'n!$ qu! $! !@(i!na 4a+ia a1a?' 3 4a+ia a""i1a/ a, i#ua, qu! 4a+ia,a !"!+4a 3 4a+ia ,a i6qui!"a. D!&!ni!n' !, !$(a' a+(ua, ! ,amquina ! Tu"in# 3 !, $5m1',' ana,i6a'/ +am1ia ! !$(a'/ !$+"i1! un$5m1',' !n ,a +!,a a+(ua, 3 $! mu!)! a ,a i6qui!"a/ a, !"!+4a/ 4a+ia
a""ia1a ' 4a+ia a1a?'. P'" (an('/ ,a un+i-n ! ("an$i+i-n &a"a !$(amquina ! Tu"in# $!" ! ,a '"ma8
8 @ @ @ R/ L/ U/ D
4.4 #ariantes de una mquina de Turing.
7/17/2019 Unidad 4 maquina de turing
21/30
UNIDAD IV MQUINA DE TURING
Una mquina ! Tu"in# mu,(iim!n$i'na, $imu,a una mquina ! Tu"in#!$(na". Sim&,!m!n(! "!a,i6an' ('a$ $u$ +'m&u(a+i'n!$ !n una
2ni+a im!n$i-n. Una mquina ! Tu"in# !$(na" (am1i0n &u!!$imu,a" una mquina ! Tu"in# mu,(iim!n$i'na, 3/ &'" (an('/ ,a+'m&,!?ia 3 ,a ,!@i1i,ia ai+i'na, qu! $! !1! a ,a m2,(i&,!im!n$i-n/ n' !$ una +a&a+ia "!a,.
Pa"a $imu,a" una mquina ! Tu"in# ! '$ im!n$i'n!$ m!ian(! unamquina ! Tu"in# !$(na"/ &"im!"' $! a$'+ia"a una i"!++i-n a ('a$,a$ +!,a$ ! ,a +in(a. Una '"ma ! 4a+!",' !$ i?a"/ ! '"ma a"1i("a"ia/un ,u#a" !n ,a +in(a a &a"(i" !, +ua, $! a$i#na"n ,a$ +''"!naa$ a ,a$+!,a$ ! ,a mi$ma '"ma qu! $! "!a,i6a !n un &,an' ! +''"!naa$.
4.4 #ariantes de una mquina de Turing.
7/17/2019 Unidad 4 maquina de turing
22/30
UNIDAD IV MQUINA DE TURING
Mquina de Turing %o determinista.
La mquina ! Tu"in# N' !(!"mini$(a !$ aqu!,,a qu! &a"a un !$(a' a+(ua, 3 !,
$5m1',' a+(ua, ! ,a +in(a/ &u!! 4a1!" un n2m!"' ini(' ! m')imi!n('$ a !,!#i".P'" ,' (an('/ ,a "!#,a ! ("an$i+i-n ! i+4a mquina/ $a(i$a+!
:q/ > @ @ R/ L
P'" !?!m&,'/ $i ,a mquina ! Tu"in# (i!n! una ("an$i+i-n
:qF/ a> 9 :qF/ 1/ R>/ :q/ a/ L> !n('n+!$ ,'$ m')imi!n('$a11qFa1 a111qF1 3 a11qFa1a1q1a1 $'n &'$i1,!$.
a qu! +ua,qui!" mquina ! Tu"in# !(!"mini$(a !$ (am1i0n n'!(!"mini$(a/ !$ ,-#i+' qu! una mquina ! Tu"in# !(!"mini$(a $! &u!! $imu,a"m!ian(! una n' !(!"mini$(a. Tam1i0n una mquina ! Tu"in# !(!"mini$(a &u!!$imu,a" una n' !(!"mini$(a. P'" (an('/ n' $! #ana nin#una &'(!n+ia ai+i'na, a
+au$a !, n' !(!"mini$m'.
4.4 #ariantes de una mquina de Turing.
7/17/2019 Unidad 4 maquina de turing
23/30
UNIDAD IV MQUINA DE TURING
L'$ &"'1,!ma$ ! i,1!"( $'n una ,i$(a ! H &"'1,!ma$ ma(!m(i+'$+'m&i,a'$ &'" !, ma(!m(i+' a,!mn Da)i i,1!"( &a"a ,a +'n!"!n+ia!n Pa"5$ !, C'n#"!$' In(!"na+i'na, ! Ma(!m(i+'$ ! F
7/17/2019 Unidad 4 maquina de turing
24/30
UNIDAD IV MQUINA DE TURING
(il'ert ten)a un peque*o grupo de pares+ ,dolf (ur-it / (ermann
Min0o-s0i eran am'os amigos cercanos e iguales intelectuales. (a/ un
gui*o a la geometr)a de nmeros de Min0o-s0i en el pro'lema 13 / asu tra'ajo en las formas cuadrticas en el pro'lema 11. (ur-it fue el
gran desarrollador de la teor)a de la superficie de iemann. (il'ert us
la analog)a del cuerpo de funciones3 una gu)a a la teor)a alge'raica de
nmeros mediante el uso de anlogos geom5tricos3 para desarrollar la
teor)a del cuerpo de clases dentro de su propia in$estigacin3 / esto
queda reflejado en el pro'lema 63 asta cierto punto en el pro'lema 123
/ en los pro'lemas 21 / 22. Por otro lado3 el nico ri$al de (il'ert en
1677 era (enri Poincar53 / la segunda parte del pro'lema 18 es una
cuestin de sistemas dinmicos al estilo de Poincar5.
4.& Pro'lemas de (il'ert.
7/17/2019 Unidad 4 maquina de turing
25/30
UNIDAD IV MQUINA DE TURING
"os $eintitr5s pro'lemas de (il'ert son+
F!" La 4i&-(!$i$ !, +'n(inu' :!$(' !$/ n' !@i$(! +'n?un(' +u3' (ama' !$(0
!$("i+(am!n(! !n("! !, ! ,'$ !n(!"'$ 3 !, ! ,'$ n2m!"'$ "!a,!$> S! 4a &"'1a' ,aim&'$i1i,ia ! &"'1a",' +'m' +i!"(' ' a,$' m!ian(! ,'$ a@i'ma$ ! Z!"m!,'7="a!nY!,. N' 4a3 +'n$!n$' a, "!$&!+(' ! +'n$i!"a" !$(' +'m' $',u+i-n a,&"'1,!ma.
P"'1a" qu! ,'$ a@i'ma$ ! ,a a"i(m0(i+a $'n +'n$i$(!n(!$ :!$(' !$/ qu! ,aa"i(m0(i+a !$ un $i$(!ma '"ma, qu! n' $u&'n! una +'n("ai++i-n>. Pa"+ia,m!n(!
"!$u!,('8 4a3 qui!n!$ $'$(i!n!n qu! $! 4a !m'$("a' im&'$i1,! ! !$(a1,!+!" !nun $i$(!ma +'n$i$(!n(!/ ini(i$(a 3 a@i'm(i+' Sin !m1a"#'/ G!n(6!n &"'1- !nFH qu! ,a +'n$i$(!n+ia ! ,a a"i(m0(i+a $! !"i)a !, 1u!n unam!n(' !, '"ina,[
7/17/2019 Unidad 4 maquina de turing
26/30
UNIDAD IV MQUINA DE TURING
^C'n$("ui" ('a$ ,a$ m0("i+a$ +u3a$ "!+(a$ $!an #!'0$i+a$. D!ma$ia' )a#'&a"a !+ii" $i $! 4a "!$u!,(' ' n'.
_\S'n ,'$ #"u&'$ +'n(inu'$ #"u&'$ i!"!n+ia,!$ ! '"ma au('m(i+a]R!$u!,(' &'" An"!K G,!a$'n
A@i'ma(i6a" ('a ,a 5$i+a Sin "!$',)!". N' ma(!m(i+'
W \E$ a 1 ("a$+!n!n(a,/ $i!n' a ` . A1i!"('
En+'n("a" ,a ,!3 m$ #!n!"a, !, (!'"!ma ! "!+i&"'+ia !n +ua,qui!" +u!"&'num0"i+' a,#!1"ai+' Pa"+ia,m!n(! "!$u!,('
4.& Pro'lemas de (il'ert.
7/17/2019 Unidad 4 maquina de turing
27/30
UNIDAD IV MQUINA DE TURING
F
7/17/2019 Unidad 4 maquina de turing
28/30
UNIDAD IV MQUINA DE TURING
FT'&','#5a ! ,a$ +u")a$ 3 $u&!"i+i!$ a,#!1"ai+a$. A1i!"('
FW E@&"!$i-n ! una un+i-n !inia "a+i'na, +'m' +'+i!n(! ! $uma$ !+ua"a'$ R!$u!,('. R!$u,(a'8 $! !$(a1,!+i- un ,5mi(! $u&!"i'" &a"a !,n2m!"' ! (0"min'$ +ua"a'$ n!+!$a"i'$
FX \E@i$(! un &',i!"' i""!#u,a" 3 qu! +'n$("u3a '("'$ &',i!"'$] \Cua, !$ !,a&i,ami!n(' +'m&a+(' m$ !n$'] R!$u!,('.
F\S'n $i!m&"! ana,5(i+a$ ,a$ $',u+i'n!$ ! ,'$ La#"an#ian'$] R!$u!,('.R!$u,(a'8 $5
7/17/2019 Unidad 4 maquina de turing
29/30
UNIDAD IV MQUINA DE TURING
F!" P"'1a" ,a !@i$(!n+ia ! !+ua+i'n!$ ,in!a,!$ i!"!n+ia,!$ qu! (!n#anun #"u&' m'n'"-mi+' &"!$+"i(' R!$u!,('. R!$u,(a'8 $5 ' n'/
!&!ni!n' ! una '"mu,a+i-n m$ !@a+(a !, &"'1,!ma
Uni'"mi6a+i-n ! ,a$ "!,a+i'n!$ ana,5(i+a$ &'" m!i' ! un+i'n!$au('m-"i+a$ R!$u!,('
H!"E@(!n$i-n ! ,'$ m0(''$ !, +,+u,' ! )a"ia+i'n!$ R!$u!,('
4.& Pro'lemas de (il'ert.
7/17/2019 Unidad 4 maquina de turing
30/30
UNIDAD IV MQUINA DE TURING
;i1,i'#"a5a
http://iie.fing.edu.uy/~vagonbar/unixbas/expreg.htm
http://www.microsoft.com/spanish/msdn/articulos/archivo/!"!#/vo
ices/regex.mspx
http://www.desarrolloweb.com/articulos/!$$.phphttp://www.elguille.info/regexp/indice.aspx%intro&eg'xp
http://(avascript.espaciolatino.com/leng(s/(sgram/expregulares.htm
http://es.wi)ipedia.org/wi)i/*ram+,$+"ticalibredecontexto
http://www.itculiacan.edu.mx/apuntes/maestros/&icardo+!uin
tero/0is+!1ebs/parte+!+!2engua(es+!&egulares/3orden+!d
e+!precedencia.htmhttp://es.wi)ipedia.org/wi)i/2engua(eregularhttp://www.monografias.com/traba(os"4/automatas-y-
gramaticas/automatas-y-gramaticas.shtml
http://www.suigeneris.org/)b/display/5,678/'xpresiones9&egulare
s9a9artir9de9utomatas
http://es.wi)ipedia.org/wi)i/ut+,$+6$matafinito
http://iie.fing.edu.uy/~vagonbar/unixbas/expreg.htmhttp://www.microsoft.com/spanish/msdn/articulos/archivo/201205/voices/regex.mspxhttp://www.microsoft.com/spanish/msdn/articulos/archivo/201205/voices/regex.mspxhttp://www.desarrolloweb.com/articulos/2033.phphttp://www.itculiacan.edu.mx/apuntes/maestros/Ricardo%20Quintero/Mis%20Webs/parte%202%20Lenguajes%20Regulares/4orden%20de%20precedencia.htmhttp://www.itculiacan.edu.mx/apuntes/maestros/Ricardo%20Quintero/Mis%20Webs/parte%202%20Lenguajes%20Regulares/4orden%20de%20precedencia.htmhttp://www.itculiacan.edu.mx/apuntes/maestros/Ricardo%20Quintero/Mis%20Webs/parte%202%20Lenguajes%20Regulares/4orden%20de%20precedencia.htmhttp://www.itculiacan.edu.mx/apuntes/maestros/Ricardo%20Quintero/Mis%20Webs/parte%202%20Lenguajes%20Regulares/4orden%20de%20precedencia.htmhttp://www.itculiacan.edu.mx/apuntes/maestros/Ricardo%20Quintero/Mis%20Webs/parte%202%20Lenguajes%20Regulares/4orden%20de%20precedencia.htmhttp://www.itculiacan.edu.mx/apuntes/maestros/Ricardo%20Quintero/Mis%20Webs/parte%202%20Lenguajes%20Regulares/4orden%20de%20precedencia.htmhttp://www.desarrolloweb.com/articulos/2033.phphttp://www.microsoft.com/spanish/msdn/articulos/archivo/201205/voices/regex.mspxhttp://www.microsoft.com/spanish/msdn/articulos/archivo/201205/voices/regex.mspxhttp://iie.fing.edu.uy/~vagonbar/unixbas/expreg.htmRecommended