Turing teljesség

A Turing-teljesség  a végrehajtó (számítási elemek halmaza) jellemzője a kiszámíthatósági elméletben , ami azt jelenti, hogy képes bármilyen kiszámítható függvényt megvalósítani rajta . Más szavakkal, minden kiszámítható függvényhez van egy elem, amely kiszámolja azt (például egy Turing-gép ) vagy egy program egy végrehajtó számára, és minden számológép által kiszámított függvény kiszámítható függvény (talán bizonyos bemeneti kódolással és kimeneti adatok).

Az ingatlan nevét Alan Turingról kapta , aki kifejlesztette az absztrakt számológépet, a Turing-gépet, és meghatározta a Turing-gépekkel kiszámítható függvénykészletet.

Példák

A legszélesebb körben használt programozási nyelvek  a Turing-komplett programozási nyelvek. Ez vonatkozik mind az olyan kötelező nyelvekre , mint a Pascal , mind a funkcionális ( Haskell ) és a logikai programozási nyelvekre ( Prolog ). Egyes programozási nyelvek (Haskell, C++ ) a futásidejű Turing-teljesség mellett fordítási idejű Turing-teljesek.

Turing-teljes normál Markov algoritmus , 2-tag rendszer , szabály 110 sejtautomata , gátló Petri-háló , lambda kalkulus béta redukcióval . A korlátlan nyelvtanok is Turing-teljesek .

A Turing-inkomplett formalizmusokra példák a véges automaták , a primitív rekurzív függvények , a környezetfüggetlen és a reguláris nyelvtanok.

Univerzális rendszer

Minden Turing-teljes számológéposztályban van egy univerzális osztályreprezentátor, amely egy tetszőleges adott osztályreprezentáció végrehajtását szimulálja. Így például egy univerzális Turing-gép egy szalagon, amely egy tetszőleges adott M Turing-gép rejtjelét tartalmazza, és annak B bemeneti karakterlánca utánozza az M végrehajtását B-n. Jelenleg 23-nál kevesebb utasítást tartalmazó univerzális Turing-gépeket építettek . ] a szimbólumállapotok számának 4x6, 5x5 kombinációihoz. Az univerzális gátló Petri-háló 56 csúcsot tartalmaz [2] .

Jegyzetek

  1. T. Neary archiválva : 2015. szeptember 24., the Wayback Machine and D. Woods. Négy kis univerzális Turing-gép. Fundamenta Informaticae, 91(1):123-144, 2009. Archiválva : 2015. szeptember 24. a Wayback Machine -nél
  2. Zaitsev DA archiválva : 2022. április 1., a Wayback Machine Toward the Minimal Universal Petri Net, IEEE Transactions on Systems, Man and Cybernetics: Systems, 2013, 1-12.

Irodalom

Linkek