Membro : Ensaluti |Register |Alŝuti scio
Serĉu
Turingma maŝino [Modifu ]
Turingma maŝino estas matematika modelo de komputado, kiu difinas abstraktan maŝinon, kiu manipulas simbolojn sur strio de bendo laŭ tabulo de reguloj. Malgraŭ la simpleco de la modelo, donita komputila algoritmo, oni povas konstrui Turing-maŝinon kapablan simuli tiun logikon de algoritmo.
La maŝino funkcias sur senfina memoro-bendo dividita en diskretajn ĉelojn. La maŝino posedas sian kapon super ĉelo kaj "legas" (skanojn) la simbolon tie. Tiam, laŭ la simbolo kaj ĝia nuna loko en tabelo finita de instrukcioj specifitaj de uzanto, la maŝino (i) skribas simbolon (ekz. Ciferon aŭ leteron de finita alfabeto) en la ĉelo (iuj modeloj, kiuj permesas simboloŝalti aŭ ne skribi), tiam (ii) movas la bendon unu ĉelo maldekstre aŭ dekstre (iuj modeloj ne permesas movi, iuj modeloj movas la kapon), tiam (iii) (laŭ difinita simbolo observita kaj la loko de la maŝino en la tablo) aŭ procede al posta instrukcio aŭ haltigas la komputadon.
La Turing-maŝino estis inventita en 1936 fare de Alan Turing, kiu nomis ĝin maŝino (aŭtomata maŝino). Kun ĉi tiu modelo, Turing povis respondi du demandojn negativajn: (1) Ĉu maŝino ekzistas, kiu povas determini ĉu iu ajn maŝino sur sia bendo estas "cirkla" (ekz. Frostigas aŭ malsukcesas daŭrigi sian komputikan taskon); simile, (2) ekzistas maŝino kiu povas determini ĉu iu ajn maŝino sur sia bendo iam ajn presas simbolitan donacon. Tiel, havigante matematikan priskribon de tre simpla aparato kapabla al arbitraj komputiloj, li povis pruvi propraĵojn de komputado ĝenerale, kaj precipe la nekompreneblecon de la problemo de Entscheidungs ​​("problemo de decido").
Tiel, Turing-maŝinoj havas fundamentajn limigojn pri la potenco de mekanika komputado. Dum ili povas esprimi arbitrajn komputojn, ilia minimumisma dezajno faras ilin netaŭga por komputado en la praktiko: la realaj mondkomputiloj estas bazitaj sur malsamaj dezajnoj, kiuj, kontraste kun Turing-maŝinoj, uzas aliman aliron-memoron.
Turing kompleteco estas la kapablo por sistemo de instrukcioj por simuli Turing-maŝinon. Programlingvo, kiu estas Turing kompleta, teorie kapablas esprimi ĉiujn taskojn plenumeblajn per komputiloj; preskaŭ ĉiuj programlingvoj estas Turing kompletaj, se la limigoj de finita memoro estas ignoritaj.
[Abstrakta maŝino][Diskretaj matematikoj][Kompetenteco][Memoro al la hazarda aliro]
1.Superrigardo
1.1.Fizika priskribo
2.Neformala priskribo
3.Formala difino
4.Pliaj detaloj postulataj por bildigi aŭ efektivigi Turing-maŝinojn
4.1.Alternativaj difinoj
4.2.La ŝtato"
4.3.Turing maŝino "ŝtat" diagramoj
5.Modeloj ekvivalentaj al la Turing-maŝino-modelo
6.Elekto c-maŝinoj, orakolo-maŝinoj
7.Maŝinoj de Turing Universala
8.Komparo kun realaj maŝinoj
8.1.Limigoj de Turing-maŝinoj
8.1.1.Komputika komplekseca teorio
8.1.2.Konkurado
8.1.3.Interago
9.Historio
9.1.Historia fono: komputila maŝinaro
9.2.La problemo de Entscheidungs ​​(la "problemo de decido"): la deka demando de Hilbert de 1900
9.3.Maŝino de Alan Turing
9.4.1937-1970: La "cifereca komputilo", la naskiĝo de "komputiko"
9.5.1970-nuna: la Turing-maŝino kiel modelo de komputado
[Alŝuti Pli Enhavo ]


Kopirajto @2018 Lxjkh