Anar al contingut

Màquina de Turing universal

De L'Enciclopèdia, la wikipedia en valencià
Est artícul o secció té referències, pero necesita més per a complementar la seua verificabilitat.
Busca fonts: «Màquina de Turing universal» – notícies · llibres · acadèmic · imàgens
Este aviso fue puesto el 12 de giner de 2016.
Per a atres usos d'este terme vore Turing (desambiguació).

Plantilla:Teoria d'autómates

En ciències de la computació, una màquina universal de Turing (UTM) és una màquina de Turing que pot simular una màquina de Turing arbitrària en l'entrada arbitrària. La màquina universal essencialment conseguix açò per mig de la llectura de tant la descripció de la màquina a ser simulada com també l'entrada mateixa de la seua pròpia cinta. Alan Turing va introduir esta màquina en 1936-1937. Este model és considerat per alguns (per eixemple,Davis, 2000) l'orige del computador de programa almagasenat — usat per John von Neumann (1946) per al "instrument de computació electrònica" que ara du el nom de von Neumann: l'arquitectura de von Neumann. És també coneguda com una màquina de computació universal, màquina universal.

En térmens de complexitat computacional, una màquina universal de Turing de múltiple cinta només necessita ser més llenta per un factor logarítmic, comparada en les màquines que simula.

Introducció

Tota màquina de Turing realisa una certa funció parcial computable fixa des de les cadenes d'entrada sobre el seu alfabet. En eixe sentit, es comporta com un computador en un programa fix. No obstant, la taula d'acció, de qualsevol màquina de Turing, pot ser codificada en una cadena. Aixina, es pot construir una màquina de Turing que espera en la seua cinta una cadena descrivint la taula d'acció (d'una atra màquina de Turing), seguida d'una cadena que descriu la cinta d'entrada (de l'atra màquina), i després computa la cinta que la màquina de Turing codificada hauria computat. Turing va descriure tal construcció en complet detall en el seu artícul de 1936:

És possible inventar una única màquina que pot ser usada per a computar qualsevol seqüència computable. Si esta màquina O és proveïda en una cinta en el principi de que està escrit el S.D ["Descripció estàndar" d'una taula d'acció] d'alguna màquina de computació M, llavors O computarà la mateixa seqüència que M.[1]

Computador de programa almagasenat

Davis fa un argument persuasivo que la concepció de Turing, de lo que ara és conegut com "el computador de programa almagasenat", que coloca la "taula d'acció" - les instruccions per a la màquina — en la mateixa "memòria" que les senyes d'entrada, fortament va influenciar la concepció de John von Neumann del primer computador de símbol discret, l'EDVAC, (en oposició al computador analògic). A este efecte, Davis cita a la revista Clave, "tot lo món que tecleja en un teclat... està treballant en una encarnació d'una màquina de Turing" i que "John von Neumann [va construir] sobre el treball d'Alan Turing" (Davis 2000:193 citant a la revista Clave del 29 de març de 1999).

Davis fa un cas indicant que el computador de Turing, l'Automatic Computing Engine (ACE), "va anticipar" les nocions de microprogramación (microcódigo) i processadors RISC (Davis 2000:188). Donald Knuth cita el treball de Turing en el computador ACE com designant "hardware per a facilitar la vinculació a subrutina";[2] Davis també fa referència a este treball com l'us per Turing d'un hardware de "stack" (Davis 2000:237 Nota 18).


A mida que la màquina de Turing fomentava la construcció de computadors, la UTM estava encorajant el desenroll de l'incipient ciència de la computació. Un primerenc, si no el primer, ensamblador va ser propost "per un jove programador hot-shot" per al EDVAC (Davis 2000:192). El "primer programa sério de von Neumann... [va ser] para simplement ordenar senyes eficientemente" (Davis 2000:184). Knuth observa que la tornada de subrutina incrustat en el propi programa en lloc de registres especials és atribuible a von Neumann i Goldstine.[3] Knuth ademés afirma que

Pot dir-se que la primera rutina interpretativa és la "màquina universal de Turing"... Rutines interpretatives, en el sentit convencional, varen ser mencionades per John Mauchly en les seues llectures en la Moore School en 1946... Turing també va prendre part en este desenroll; baix la seua direcció varen ser escrits sistemes interpretatius per al computador Pilot ACE"

Davis menciona breument als sistemes operatius i als compiladors com a resultats de la noció de programa com a senyes (Davis 2000:185).

Alguns, no obstant, podrien plantejar problemes en esta evaluació. En el moment (des de mediats de 1940 fins a mediats de la década de 1950) un relativament chicotet grup d'investigadors estaven íntimament involucrats en l'arquitectura de les noves "computadores digitals". Hao Wang (1954), un jove investigador en este llavors, va fer la següent observació:

La teoria de funcions computables de Turing va antecedir pero no ha influenciat molt en l'extensa construcció de computadores digitals. Estos dos aspectes de la teoria i la pràctica han segut desenrollats casi en la seua totalitat independentment un de l'un atre. Sense dubte, la raó principal és que els llògics estan interessats en qüestions radicalment diferents de les que els interessen als matemàtics aplicats i ingeniers elèctrics, No obstant, no es pot fallar en falcar com prou estrany que a sovint els mateixos conceptes són expressats en térmens molt diferents en els dos desenrolls
Wang 1954, 1957:63

Wang esperava que el seu artícul seria "conectar els dos enfocaments". De fet, Minsky confirma açò: "que la primera formulació de la teoria de la màquina de Turing en models com a computadora apareix en Wang (1957)" (Minsky 1967:200). Minsky passa a demostrar l'equivalència de Turing d'una màquina de contador.

Sobre la reducció dels computadors a simples models Turing equivalents (i viceversa), és un debat obert la designació de Minsky de que Wang va fer "la primera formulació". Mentres que tant l'artícul de Minsky de 1961 i l'artícul de Wang de 1957 són citats per Shepherdson i Sturgis (1963), també citen i sumarizan en cert detall el treball dels matemàtics europeus Kaphenst (1959), Ershov (1959), i Péter (1958). Els noms de matemàtics Hermes (1954, 1955, 1961) i Kaphenst (1959) apareixen en les bibliografia de Sheperdson-Sturgis (1963) i Elgot-Robinson (1961). Atres dos noms d'importància són els investigadors canadencs Melzak (1961) i Lambek (1961). Per a molt més, veja equivalents de la màquina de Turing; les referències poden ser trobades en màquina de registre.

Referències

  1. ↑ Boldface replacing script. Turing 1936 in Davis 1965:127-128. An example of Turing's notion of S.D is given at the end of this article.
  2. ↑ Knuth, 1973, p. 225.
  3. ↑ In particular: Burks, Goldstine, von Neumann (1946), Preliminary discussion of the logical design of an electronic computing instrument, reprinted in Bell and Newell 1971

Referències generals

Artículs seminals

  • F. C. Hennie and R. E. Stearns. Two-tape simulation of multitape Turing machines. JACM, 13(4):533–546, 1966.

Atres referències

  • .
  • Goldstine, Herman H., and von Neumann, John, "Planning and Coding of the Problems for an Electronic Computing Instrument", Rep. 1947, Institute for Advanced Study, Princeton. Reprinted on pp. 92–119 in Bell, C. Gordon and Newell, Allen (1971), Computer Structures: Readings and Examples, McGraw-Hill Book Company, New York. ISBN 0-07-004357-4}.
  • (and ). Reprinted in Martin Davis ed. (1965) The Undecidable, Raven Press, Hewlett NY pp. 115–154; with corrections to Turing's UTM by Emil Post cf footnote 11 in Davis 1965:299.

Vore també


Referències


Obtingut de «https://lenciclopedia.org/w/index.php?title=Màquina_de_Turing_universal&oldid=1443248»