turing kompleta - Wikilingue - Encydia
En la teorio de realaj komputiloj kaj imaginarias, de la lingvoj de programado kaj de aliaj logikaj sistemoj, sistemo Turing kompleta estas tiu kiu havas povi computacional ekvivalenta al la universala maŝino de Turing. En aliaj vortoj, la sistemo kaj la universala maŝino de Turing povas emularse inter oni.
Ankoraŭ kiam estas fizike neebla ol ekzistas ĉi tiuj maŝinoj pro tio ke ili postulas de senlima stokado kaj probablo nulo de faŭlto, familiare la completitud de Turing atribuas al fizikaj maŝinoj aŭ lingvoj de programado kiun ili eblus universalaj se ili havis senfinan stokadon kaj ili iris absolute solidaj. La unua de tiuj maŝinoj aperis en 1941: la Z3 de Konrad Zuse, kiu estis kontrolita de programoj. Lia universalidad, tamen, estis pruvita multe poste de Raúl Ruĝaj en 1998. En tiu malstreĉita senso, ĉiuj modernaj komputiloj estas ankaŭ Turing kompletaj.
La completitud de Turing estas signifa, ĉar, ĉiu dezajno plausible de mekanismo de komputado, por pli antaŭita ol estu (eĉ la komputiloj cuánticas), ili eblas emuladas por universala maŝino de Turing. Tiel, maŝino kiu povas agi kiel universala maŝino de Turing povas, en komenco, fari ajnan ŝtonon kiu ajna alia komputilo estas kapabla de fari (en aliaj vortoj, estas programable). Observu , tamen, kiu diras nenion sur la penado de skribi programon por la maŝino aŭ sur la tempo kiu povas preni la ŝtonon.
Estas la hipotezo kiun la Universo estas Turing kompleta (vidi filozofiajn implikaĵojn en la Tezo de Church-Turing kaj en cifereca Fiziko).
Vidi la artikolon en Teorio de la computabilidad por longa lerta de sistemoj kiuj estas Turing kompletaj, tiel kiel pluraj sistemoj kiuj estas malpli potencaj, kaj pluraj teoriaj sistemoj kiuj estas ankoraŭ pli potencaj ol la universala maŝino de Turing.
Ekzemploj
Estas malfacile trovi ekzemplojn de lingvoj ne Turing kompletaj, pro tio ke tiuj lingvoj estas tre limigitaj. Ekzemplo eblus la seriojn de matematikaj formuloj en folio de ŝtono sen cikloj. Dum kiu eblas fari plurajn interesajn operaciojn en tiu sistemo, ĉi tiu faŭlto en esti Turing kompleta pro tio ke estas neeble fari ciklojn. La lingvo de macros de Excel, tamen, estas Turing kompleta. Alia fama ekzemplo estas la regulaj esprimoj enhavitaj en lingvoj kiel perl. lerta de lingvoj Turing kompletaj estas sub la rubro de teorio de la computabilidad.
Grava rezulto de la teorio de la computabilidad estas kiu, ĝenerale, estas neeble scii se skribita programo en lingvo Turing kompleta daŭre ekzekutos nedifinite aŭ ĝi detenos en periodo finito de tempo. Metodo por antaŭvidi ke ĝi okazas lin unue estas fari ke la programoj detenas post fiksa periodo de tempo. Strikte, tiuj sistemoj ne estas Turing kompletaj.
La ŝtono lambda sen tipo estas Turing kompleta, sed multaj ŝtonoj lambda kun tipo, inkludante la Sistemo F ne lin estas. La valoro de la sistemoj kun tipo bazas en lia kapableco de reprezenti multaj de la programoj de tipaj "komputilo" dum ili detektas liajn erarojn.
Vidu ankaŭ
- Tezo de Church-Turing
- Teorio de la informo algorítmica
- La libro de Stephen Wolfram Al New Kind of Science
