Máquinas de Touring

Embed Size (px)

Citation preview

  • 7/23/2019 Mquinas de Touring

    1/5

    Maquinas de Turing (es un modelomatemtico)

    Modelo matemtico es una expresin de esas que seutilizan con cierta frecuencia pero que pocas veces nosparamos a pensar qu signica ! aunque parezca algocomplicado" en realidad se trata de un concepto #astantesencillo

    $n modelo matemtico es un con%unto de reglas que

    enca%an en la explicacin & resolucin de un pro#lema" esdecir" que modelizan una situacin concreta para poderexplicarla & encontrar el modo de resolverla Ms a'n" sepodra decir que un modelo matemtico es un con%unto dereglas capaces de generalizar & resolver un pro#lemamatemtico concreto & cualquier otro de su mismanaturaleza que se pueda plantear

    l e%emplo ms simple que se me ocurre es" ante el

    pro#lema *cuntas manzanas tenemos si &o tengo tres & t'tienes dos+" el modelo matemtico a aplicar es el quecomprende a los n'meros naturales (,"-"."/"0) & su sumanita 1s" cuando nos encontremos con otro caso similar"como por e%emplo averiguar cuntos a2os suman las edadesde tres personas" #asta con aplicar este modelo paraaveriguarlo" es decir" sumar la edad de cada uno de ellos

    Tan fcil como parece

    13ora la armacin una Mquina de Turing es un modelomatemtico co#ra signicado4 nos dice que es una forma deresolver cierto tipo de pro#lemas" que adems funciona

    n

    ,7.," el matemticoc3eco 8urt 9odel

    descu#ri que 3a#ateoremas matemticosque eran verdaderos a'ncuando no se pudiesenpro#ar 1nte esto" 1lanTuring se puso a investigaraquellos que s podan serpro#ados :uera intentardemostrar la vie%a idea deque las matemticas noson un arte misterioso"sino una ciencia exactaregida por reglas lgicas

  • 7/23/2019 Mquinas de Touring

    2/5

    Maquinas de Turing (es un modelomatemtico)

    ;a Mquina de Turing (MT) fue introducida por 1lan M Turingen ,7.

  • 7/23/2019 Mquinas de Touring

    3/5

    Turing ide un sorprendente experimento mentalKa#a nacido la mquina de Turing

    1lan empez por denir lo que era un n'merocomputa#le4 n'meros reales cu&a expresin comodecimal puede calcularse por medios nitos

    1 partir de esta denicin" Turing ide unamquina imaginaria que pudiera tratar conn'meros computa#les ;as caractersticas son lassiguientes4

    1l#erga un n'mero nito de condiciones" a lasque llam conguracionesFm (qLi)

    ;a mquina tiene una cinta dividida en celdas"cada una de los cuales puede tener escrito unsm#olo ;a cinta pasa a travs de la mquina &tiene una longitud innita

    n cada momento de funcionamiento de la

    mquina" una sola celda de la cinta estar dentrode ella 1 la celda de la cinta que puede leer la mquina"

    le llamaremos la celda activa l sm#olo dentrode esta celda es el 'nico dato de entrada queconoce la mquina en un momento dado" pero atravs de cam#ios de conguraciones" se puedetener conocimiento de los sm#olos ledosanteriormente

    ;a conguracinFm activa en la mquina" %unto al

    ;a mquina de Touring

    Turing deni tam#in las posi#les acciones quepoda realizar la mquina4

    scri#ir un sm#olo en la celda activa (6) Corrar sm#olo de la celda activa () Mover la cinta una posicin 3acia la izquierda

    (;) Mover la cinta una posicin 3acia la derec3a () Dinalmente" en cada paso puede producirse un

    cam#io en la conguracin

    squema de una mquina escrito por Turing n concreto parala mquina que escri#e la secuencia @@,@,,@,,,@,,,,0

  • 7/23/2019 Mquinas de Touring

    4/5

    ;egado

    ;os conceptos que present en estedocumento" %unto a su tra#a%o en las

    mquinas 5olossus para el descifrado decdigos de nigma" situaron a Turing comouno de los ma&ores expertos en computacinal nal de la Aegunda 9uerra Mundial NonOeumann quiso contar con l" pero en su#reve visita a $$ no se sinti cmodo &volvi a =nglaterra" donde cre el primerordenador #ritnico4 15

    Mientras" en $$" se crea#a el O=15 & NonOeumann pona nom#re" de manera un tantoin%usta" a su arquitectura 6rcticamente todoslos ordenadores de 3o& en da utilizan laarquitectura Non Oeumann" en la que tanto elprograma a e%ecutar como los datos" seencuentran en una misma memoria Pste erael concepto que Turing adelant en ,7.< que

    aca#ara imponindose en la #reve 3istoria delos computadores

  • 7/23/2019 Mquinas de Touring

    5/5

    Ci#liografa

    3ttp4>>esslides3arenet>Qeroo,R>mquinasFdeFturingF/S//S/,@+nextLslides3oB,

    3ttp4>>esslides3arenet>iscrquinter>parteF/FmquinasFdeFturing+relatedB.3ttps4>>sinclairqlesordpresscom>-@,@>@S>@R>maquinaFdeFturingFlaFcintFteorica>3ttp4>>zatorcom>5pp>@L,L,3tm3ttp4>>,@.R@@S/galeoncom>u/3tm

    3ttp4>>e#ingpuccl>Umarenas>iic.-/-F,,>clases>mtFimppdf3ttp4>>sce3ues>%i3e3um->T5>temas>V-Wturingpdfle4>>>54>$sers>alp3N>Eonloads>M5LTemaXpdf3ttp4>>turingiimasunammx>Uluis>cursosLpdf>computa#ilidad>5apit.6ED

    https://sinclairqles.wordpress.com/2010/05/08/maquina-de-turing-la-cinta-teorica/http:/www.zator.com/Cpp/E0_1_1.htmhttps://sinclairqles.wordpress.com/2010/05/08/maquina-de-turing-la-cinta-teorica/http:/www.zator.com/Cpp/E0_1_1.htmhttps://sinclairqles.wordpress.com/2010/05/08/maquina-de-turing-la-cinta-teorica/http:/www.zator.com/Cpp/E0_1_1.htmhttp://web.ing.puc.cl/~marenas/iic3242-11/clases/mt-imp.pdfhttp://www.sc.ehu.es/jiwhehum2/TC/temas/%5B2%5Dturing.pdfhttp://c/Users/RalphV/Downloads/MC_Tema7.pdfhttp://c/Users/RalphV/Downloads/MC_Tema7.pdfhttp://c/Users/RalphV/Downloads/MC_Tema7.pdfhttp://www.sc.ehu.es/jiwhehum2/TC/temas/%5B2%5Dturing.pdfhttp://www.sc.ehu.es/jiwhehum2/TC/temas/%5B2%5Dturing.pdfhttp://web.ing.puc.cl/~marenas/iic3242-11/clases/mt-imp.pdfhttp://web.ing.puc.cl/~marenas/iic3242-11/clases/mt-imp.pdfhttps://sinclairqles.wordpress.com/2010/05/08/maquina-de-turing-la-cinta-teorica/http:/www.zator.com/Cpp/E0_1_1.htmhttps://sinclairqles.wordpress.com/2010/05/08/maquina-de-turing-la-cinta-teorica/http:/www.zator.com/Cpp/E0_1_1.htmhttps://sinclairqles.wordpress.com/2010/05/08/maquina-de-turing-la-cinta-teorica/http:/www.zator.com/Cpp/E0_1_1.htm