Mitől teljes a Turing-nyelv?

A Turing tarpit egyfajta ezoterikus programozási nyelv, amely arra törekszik, hogy Turing-teljes legyen, miközben a lehető legkevesebb elemet használja. A Brainfuck talán a legismertebb tarpit, de sok ilyen van.

• Iota és Jot funkcionális nyelv, két, illetve három szimbólummal, a SK (I) kombinátor számítása .

• OISC ( Egy utasításkészlet-számítógép ) az imperatív számítás olyan típusát jelöli, amely egy vagy több argumentumból csak egy utasítást igényel, általában „kivon és elágazik, ha nullánál kisebb vagy egyenlő”, vagy „Fordított kivonás és kihagyás, ha kölcsön”. Az x86 MMU végrehajtja az előbbi utasítást, és így Turing-teljes.

Általában egy az elengedhetetlen nyelv, hogy Turing-teljes legyen, a következőkre van szüksége:

1. A feltételes ismétlés vagy a feltételes ugrás egyik formája (pl. while, if + goto)

2. A tárolás valamilyen formájának (pl. olvasása) módja , változók, szalag)

Ha egy lambda-calculus alapú funkcionális nyelv TC, akkor ez igényei:

1. A funkciók elvonatkoztatása az argumentumok felett (pl. lambda absztrakció, idézet)

2. Funkciók alkalmazásának képessége argumentumok (pl. redukció)

A számításnak természetesen vannak más módjai is, de ezek a Turing tarpits szokásos modelljei. Ne feledje, hogy a valós számítógépek nem univerzális Turing-gépek , mert nincs korlátlan tárhelyük. Szigorúan véve „korlátozott tárológépek”. Ha folyton memóriát adna hozzájuk, aszimptotikusan közelítenék a hatalmon lévő Turing-gépeket. Ugyanakkor még a korlátozott tároló gépek és a véges állapotú gépek is hasznosak a számításhoz; egyszerűen nem egyetemesek.

Szigorúan véve az I / O nem szükséges a Turing-teljességhez; A TC csak azt állítja, hogy egy nyelv kiszámíthatja a kívánt funkciót, nem pedig azt, hogy megmutathatja neked az eredményt. A gyakorlatban minden hasznos nyelvnek módja van arra, hogy valahogy kölcsönhatásba lépjen a világgal.

Megjegyzések

• A kötelező nyelvekhez elegendőek-e az egyszerű változók? Az volt a benyomásom, hogy valamilyen gyűjtésre (például tömbökre vagy összekapcsolt listákra) lenne szükség.
• @luiscubal tetszőleges mennyiségű adatot kell megadnia. Az egyszerű változókkal megadhatja, hogy mennyi adatmennyiség van maguknak a változóknak. Mi van, ha N + 1 különböző adatot kell ábrázolnia. Lehet vitatni, hogy trükkökkel , mint például a Fractran játszik, akár egyszerű változókban is megteheti … de hogy ‘ s nem egészen az, amit ‘ kérdezel.
• Nem ‘ szükséges, hogy a nyelvnek támogatnia kell VÉGTELEN hurkok?
• Re, ” minden hasznos nyelvnek módja van a világgal való interakcióra. ” Algol 60 nem rendelkezett semmilyen meghatározott módszerrel a világgal való interakcióra. Az Algol 60 programban használt összes I / O-t a függvénykönyvtár-függvények meghívásával hajtották végre, és a könyvtári funkciók teljesen eltérőek lehetnek a különböző megvalósításokban. De ezennel visszautasítom magam minden olyan vitából, hogy az Algol 60 ” hasznos volt-e. ”

Gyakorlatiasabb szempontból: ha az összes programot lefordíthatja egy Turing-teljes nyelven az Ön nyelvére, akkor (amennyiben Tudom), a nyelvének Turing-teljesnek kell lennie.Ezért, ha azt szeretné ellenőrizni, hogy az Ön által tervezett nyelv Turing-teljes-e, egyszerűen írjon egy Brainf *** -ot a YourLanguage fordítójához, és bebizonyítsa / bebizonyítsa, hogy az összes legális BF-programot képes lefordítani.

pontosítom, úgy értem, hogy a YourLanguage tolmácsán kívül írsz egy fordítót (bármilyen nyelven), amely bármilyen BF programot lefordíthat a YourLanguage-ba (természetesen ugyanazt a szemantikát megtartva).

Megjegyzések

• Igen, mindenképpen ez lenne a legpraktikusabb megközelítés. </sarcasm>
• @RobertHarvey van egy pontja, de az általános elképzelés meglehetősen fontos. A Brainfuck bizonyítottan teljes és nagyon egyszerű, ahogy a programozási nyelvek használják. A nem ezoterikus programnyelvek esetében az brainfuck tolmács megvalósítása sokkal egyszerűbb és gyorsabb lehet, mint a semmiből történő szigorú bizonyítás (a BF-et a Python pár sorában tudom megvalósítani, de I ‘ m nem tudom, hol kezdjem egy hivatalos bizonyítékkal arra, hogy a Python teljes) és az ezoterikus brainfuck által inspirált nyelvek tucatjai teljes körűek, mert ‘ s tudják, hogyan térképeznek fel agymenést.
• @RobertHarvey: Miért ne? Bizonyára valaki, aki a saját nyelvét tervezi, képes lenne írni egy BF fordítót hozzá (ha ez elengedhetetlen, és egyébként találna megfelelő más nyelvet).
• @delnan: Ön lesz igazolnia kell azonban, hogy a BF tolmácsod helyesen hajtja végre a BF specifikációt, IOW bizonyítanod kell, hogy a BF tolmácsod valójában BF tolmács, és nem tolmács egy olyan BF-szerű nyelvhez, amely esetleg nem Turing-teljes.
• @ DarekNędza, ez ‘ csak természetes következménye annak, hogy a Turing teljesség meghatározva van; a Turing Complete nyelv bármely kiterjesztése továbbra is Turing Complete lesz.

A rendszer csak akkor tekinthető meg hogy teljes legyen Turing, ha bármit megtehet, amit egy univerzális Turing-gép képes. Mivel az univerzális Turing-gép állítólag képes bármilyen kiszámítható funkció adott időre történő megoldására, a Turing komplett rendszerei kiterjesztve ezt is megtehetik.

Ha szeretné ellenőrizni, hogy valami befejeződött-e, akkor nézze meg, hogy megvalósíthat benne egy Turing-gépet. Más szavakkal, ellenőrizze, hogy képes-e szimulálni a következőket:

1. A “változók” (vagy tetszőleges adatok) olvasási és írási képessége : Nagyjából magától értetődő.
2. Az olvasási / írási fej mozgatásának szimulációs képessége : Ez nem elég ahhoz, hogy csak változókat lehessen beolvasni és tárolni. Lehetségesnek kell lennie a szalag fejének mozgatásának szimulálására is, hogy más változókra hivatkozhasson. Ez gyakran szimulálható a programozási nyelveken belül tömb adatstruktúrák (vagy azzal egyenértékű) használatával, vagy bizonyos nyelvek, például gépi kód esetén más mutatók hivatkozására való képességgel “mutatók” (vagy ezzel egyenértékű) használatával.
3. A véges állapotú gép szimulálásának képessége : Bár nem említik gyakran, a Turing-gépek valójában az AI fejlesztésénél gyakran használt véges állapotú gépek variációja. Alan Turing szerint az állapotok célja egy személy különböző problémamegoldási módjainak szimulálása.
4. A “megáll” állapot : Bár gyakran emlegetnek egy szabálykészletet, képesnek kell lennie arra, hogy megismételje önmagát ahhoz, hogy Turing teljesnek tekintsék, ez nem igazán jó kritérium, mivel a az algoritmus olyan állapot, hogy az algoritmusoknak mindig véget kell vetniük. Ha valamilyen módon nem tudnak következtetni, akkor vagy nem teljes Turing, vagy az említett algoritmus nem számítható függvény. Olyan komplett rendszerek előkészítése, amelyek technikailag nem tudnak következtetni működésüknek köszönhetően (például a játékkonzolok) megkerülik ezt a korlátozást azzal, hogy valamilyen módon képesek „szimulálni” egy leállási állapotot. Nem tévesztendő össze a „leállási problémával” “, egy megdönthetetlen függvény, amely bebizonyítja, hogy lehetetlen olyan rendszert felépíteni, amely 100% -os megbízhatósággal képes felismerni, ha egy adott bemenet miatt egy másik rendszer nem következtet.

Ezek az igazi minimum a Turing teljesnek tekinthető rendszer követelményei. Se több, se kevesebb. Ha ezek egyikét sem tudja valamilyen módon szimulálni, akkor Turing nem teljes. A mások által javasolt módszerek csak a végsőkig jelentenek, mivel több olyan komplett Turing-rendszer létezik, amelyek nem rendelkeznek ezekkel a funkciókkal.

Ne feledje, hogy nincs igazi módja annak, hogy valóban létrehozzanak egy valódi Turing-rendszert Ez azért van, mert nincs ismert módszer a Turing-gép szalagjának határtalanságának valós szimulálására a fizikai térben.

A programozási nyelv készen áll, ha bármilyen számítást el tud vele végezni.Nem csak egy olyan funkciókészlet teszi teljessé a nyelvet, amely tévesen válaszol, mondván, hogy hurokra van szükséged, vagy hogy változókra van szükséged, mivel vannak olyan nyelvek, amelyek nem rendelkeznek de teljes körűek.

Alan Turing készítette az univerzális turing gépet, és ha bármilyen nyelven lefordítható programot úgy terveztek, hogy az univerzális gépen működjön, akkor az is teljes Turing. Ez közvetetten is működik, így azt mondhatja, hogy az X nyelv befejeződött, ha az összes program az Y teljes nyelvének fordításához lefordítható az X nyelvre, mivel az összes univerzális gép program lefordítható Y programba.

Az idő összetettsége , a tér bonyolultsága, az egyszerű bemeneti / kimeneti formátum és a könnyű program megírása nem szerepel az egyenletben, így egy ilyen gép elméletileg minden számítást elvégezhet, ha a számításokat nem állítja le az energiaveszteség vagy a Föld lenyeli a napot.

A telt teljesség igazolásához általában tolmácsot készítenek minden bizonyítottan teljes nyelvűnek, de a működéséhez be- és kimeneti eszközökre van szükséged, két dologra, amelyek valóban nem szükségesek ahhoz, hogy a nyelv teljes legyen. Elég, ha a program indításkor megváltoztathatja állapotát, és hogy a program leállítása után megvizsgálhatja a memóriát.

A sikeres nyelv elkészítéséhez azonban nem csak a teljességre van szükség, és ez igaz még a kisteherautókra is. Nem hiszem, hogy a BrainFuck népszerű lett volna , és ..

Megjegyzések

• ” A programozási nyelv befejeződött, ha bármilyen számítást megtehet ” Ez ‘ az egyház-türingi tézis, nem pedig az, ami miatt a nyelv turing-teljes.
• @Rhymoid Tehát azt akarod mondani, hogy semmi sem változik, hacsak nem tudsz tolmácsot készíteni? Azaz a lambda számítás még akkor sem teljes, ha ‘ egyenlő?
• I ‘ még mindig a Turing-ekvivalens és a Turing-teljes (és a Turing-erős) kifejezések hiteles meghatározását keresem. I ‘ már túl sok esetet láttam, az üzenőfalak embereitől kezdve a kutatókig a saját friggin ‘ cikkeikben, akik eltérően értelmezik ezeket a kifejezéseket.
• Egyébként A ‘ Turing-complete ‘ -t úgy értelmezem, hogy az univerzális Turing Machine (UTM; amely viszont bármely Turing-gépet képes szimulálni – ezért ‘ univerzális ‘). Turing ‘ 1936-os dolgozatában, ahol bemutatta gépeit, meghatározta az UTM fogalmát, és vázlatosan bemutatta annak igazolását, hogy az UTM-ek szimulációval egyenértékűek az egyház ‘ s lambda kalkulus. Ezzel bebizonyította, hogy számítási erejük azonos. Az egyház-türingi tézis azt állítja, egyszerűen fogalmazva, hogy ” hogy ‘ minden számítási teljesítményed megvan

Nem tudja megmondani, hogy végtelen ciklusban áll-e vagy leáll.

————-

Magyarázat: Bizonyos bemenetek alapján lehetetlen minden esetben megmondani (egy másik Turing-gép használatával), hogy a dolog végtelenül fog-e hurkolni, vagy végül le fog-e állni, kivéve, ha futtatja (ami választ ad, ha mégis állítsa le, de ne, ha hurkol!).

Ez azt jelenti, hogy valamilyen módon képesnek kell lennie egy potenciálisan korlátlan mennyiségű adat tárolására – a végtelen szalagnak egyenértékűnek kell lennie, bármennyire is összevissza! (Ellenkező esetben csak véges számú állapot van, és akkor ellenőrizheti, hogy korábban átment-e már ezen az állapoton, és végül leáll-e). Általánosságban elmondható, hogy a Turing gépek bizonyos irányítható eszközökkel növekedhetnek vagy csökkenthetik az állapotukat.

Mivel a Turing eredeti univerzális Turing gépének megoldhatatlan leállási problémája van, a saját Turing teljes gépének is megoldhatatlan leállással kell rendelkeznie. probléma.

A Turing komplett rendszerek bármely más Turing komplett rendszert utánozhatnak, tehát ha emulátort tudsz építeni a rendszered egyik jól ismert Turing teljes rendszeréhez, az bizonyítja, hogy a rendszered is teljes.

Tegyük fel például, hogy be akarja bizonyítani, hogy a Kígyók & létra készen áll, és egy végtelenül megismételt rácsmintával ellátott táblát kapunk (a tetején más verzióval) és bal oldal). Tudva, hogy a 2-számlálós Minsky-gép készen áll a Turing-mel (amelynek 2 korlátlan számlálója és 1 állapota van egy véges számból), létrehozhat egy egyenértékű táblát, ahol a rács X és Y helyzete a 2 számláló aktuális értéke és az aktuális út az aktuális állapot. Bumm! Most bizonyítottad, hogy a kígyók & A létra készen áll.

Hozzászólások

• Nem ‘ nem veszi meg ezt az érvet. Csak azért, mert a leállítási probléma a Turing-gépek számára eldönthetetlen, még nem jelenti közvetlenül azt, hogy minden olyan jelölés, amely lehetővé teszi olyan program megadását, amelynél a leállítási probléma nem eldönthető, Turing teljes. Nyilvánvalóan csak az inverz igaz: Ha a jelölés Turing teljes, akkor természetesen olyan programokat is lehet írni, amelyeknél a leállítási probléma eldönthetetlen.
• Ez ‘ szükséges állapot. Ha minden programnál el tudja dönteni, hogy leáll-e, akkor a nyelv nem ‘ t Turing befejeződött.

Az egyik szükséges feltétel egy hurok, amelynek maximális iterációs számát nem az iteráció előtt határozzák meg, vagy rekurzió, ahol a maximális rekurziós mélység nincs előre meghatározva. Például a … in … ciklusokhoz, mivel sok újabb nyelven megtalálod őket, nem elegendő a nyelv kiteljesedése (de más módjaik is lesznek). Ne feledje, hogy ez nem korlátozott számú iterációt vagy korlátozott rekurziós mélységet jelent, hanem azt, hogy a maximális iterációkat és rekurziós mélységet előre ki kell számolni.

Például az Ackermann függvényt nem lehet olyan nyelven kiszámítani, amelynek nincs Másrészt sok nagyon összetett és nagyon hasznos szoftver írható anélkül, hogy szükség lenne ezekre a funkciókra.

Másrészt minden iterációszámmal és minden rekurziós mélységgel előre számolva, nemcsak el lehet dönteni, hogy leáll-e egy program vagy sem, de leáll .

tudom, hogy ez nem formailag helyes válasz, de ha egyszer kiveszed a „minimálisat” a „Turing-complete” -ból, és visszateszed a „praktikusat” oda, ahová tartozik, meglátod a legfontosabb jellemzőket, amelyek megkülönböztetik a programozási nyelvet a egy jelölőnyelv

• változó
• feltételes (ha / akkor …)
• hurok (hurok / törés, míg …)

következő com e

• névtelen és elnevezett függvények

ezeknek az állításoknak a teszteléséhez kezdje el a jelölőnyelvet, mondjuk a HTML-t. kitalálhatnánk egy HTML + -t csak változókkal, vagy csak feltételekkel (az MS ezt feltételes megjegyzésekkel tette), vagy valamilyen hurok konstrukciót (amely feltételes feltételek hiányában valószínűleg <repeat n="4">...</repeat>). ezek bármelyikének elvégzése jelentősen (?) erősebbé teszi a HTML + -ot, mint a sima HTML, de ez mégis inkább jelölés, mint programozási nyelv lenne; minden új funkcióval kevésbé deklaratív és inkább imperatív nyelvvé teszi.

A logika és a programozás minimalitására való törekvés biztosan fontos és érdekes, de ha n00-asokat fiataloknak vagy időseknek kellett volna megtanítanom, hogy „mi a programozás” és „hogyan kell megtanulni programozni”, akkor alig indulok el. a Turing teljességének elméleti alapjainak teljes szélességével és szélességével. A főzés és a programozás lényege, hogy dolgokat csinál, megfelelő sorrendben, ismételve, amíg készen áll, ahogy az édesanyád tette. ez körülbelül nekem összegzi.

akkor még soha nem fejeztem be a CS-t.

Megjegyzések

• Ha nem biztos benne, akkor először kutatnia kell. fractran teljes , ahogy brainf * ck . Vegye figyelembe azt is, hogy a html 5 + CSS 3 befejeződött, mert képes megvalósítani a 110. szabály .
• igen igen, tudom. de az összes megadott példa többé-kevésbé ezoterikus (bár érdekes vagy meglepő), m y pragmatikus válasz volt, és valószínűleg egyáltalán nem minimális. szerintem ‘ fontos erre rámutatni – ez az oldal volt az első, amikor a google-on a Turing-teljességet kereste, az itteni válaszok az IMHO-nak nincs sok haszna mondjuk egy n00bie számára aki tudni akarja, mi különbözteti meg a HTML-t a PHP-től vagy a Python-tól. úgy értem, az brainf ck-t ok nélkül nem nevezik brainf ck-nek.