Co dělá jazyk Turing úplným?

A Turingova tarpit je druh esoterického programovacího jazyka, který se snaží být Turingův úplný při používání co nejméně prvků. Brainfuck je možná nejznámější tarpit, ale existuje jich mnoho.

• Iota a Jot jsou funkční jazyky se dvěma, respektive třemi symboly, založené na SK (I) kombinatorický počet .

• OISC ( Počítač s jednou instrukční sadou ) označuje typ imperativního výpočtu, který vyžaduje pouze jednu instrukci jednoho nebo více argumentů, obvykle „odečíst a větvit, pokud je menší nebo roven nule“, nebo „Zpět odečíst a přeskočit, pokud si půjčíte“. x86 MMU implementuje dřívější instrukci a je tedy Turing-úplný.

Obecně platí, že pro nezbytně nutné, aby byl Turingův jazyk úplný:

1. Forma podmíněného opakování nebo podmíněného skoku (např. while, if + goto)

2. Způsob čtení a zápisu určité formy úložiště (např. , proměnné, páska)

Aby funkční jazyk založený na lambda-kalkulu byl TC, je potřeby:

1. Schopnost abstrahovat funkce nad argumenty (např. lambda abstrakce, citace)

2. Schopnost aplikovat funkce na argumenty (např. redukce)

Existují samozřejmě i jiné způsoby pohledu na výpočet, ale jedná se o běžné modely pro Turingovy tarpy. Skutečné počítače nejsou univerzální Turingovy stroje , protože nemají neomezené úložiště. Přesně řečeno, jsou to „ohraničené skladovací stroje“. Pokud byste jim měli stále přidávat paměť, asymptoticky by se přiblížili k Turingovým strojům u moci. Pro výpočet jsou však užitečné i omezené úložné stroje a stroje s konečným stavem ; prostě nejsou univerzální .

Přesně řečeno, I / O není pro Turingovu úplnost vyžadován; TC pouze tvrdí, že jazyk může vypočítat požadovanou funkci, nikoli že vám může zobrazit výsledek. V praxi má každý užitečný jazyk způsob interakce se světem.

Komentáře

• Jsou pro imperativní jazyky dostačující jednoduché proměnné? Měl jsem dojem, že bude nutný nějaký druh sběru (např. Pole nebo propojené seznamy).
• @luiscubal, musíte být schopni určit libovolné množství dat. Pomocí jednoduchých proměnných můžete představovat množství dat, která samotné proměnné mají. Co když potřebujete reprezentovat N + 1 různých dat. Dalo by se namítnout, že s triky , jako hraje Fractran, byste to dokázali i v jednoduchých proměnných … ale ‚ to není úplně to, na co ‚ žádáte.
• Není to ‚ pokud to vyžaduje jazyk, který musí podporovat ENDLESS smyčky?
• Re, “ každý užitečný jazyk má způsob interakce se světem. “ Algol 60 neměl žádný definovaný způsob interakce se světem. Všechny vaše I / O v programu Algol 60 byly provedeny voláním funkcí knihovny a funkce knihovny se mohly v různých implementacích zcela lišit. Tím se však vzdávám diskuse o tom, zda byl Algol 60 “ užitečný. “

Z praktičtějšího hlediska: pokud můžete přeložit všechny programy v Turingově úplném jazyce do svého jazyka, pak (pokud Vím), váš jazyk musí být Turingův úplný.Pokud tedy chcete zkontrolovat, zda je jazyk, který jste navrhli, Turing-complete, můžete jednoduše napsat kompilátor Brainf *** do YourLanguage a prokázat / prokázat, že může kompilovat všechny legální programy BF.

To objasnit, mám na mysli, že kromě tlumočníka pro YourLanguage píšete kompilátor (v jakémkoli jazyce), který může zkompilovat jakýkoli BF program do YourLanguage (samozřejmě při zachování stejné sémantiky).

Komentáře

• Ano, to by byl určitě nejpraktičtější způsob, jak k tomu přistupovat. </sarcasm>
• @RobertHarvey má pravdu, ale obecná myšlenka je zcela zásadní. Ukázalo se, že Brainfuck je turing-kompletní a velmi jednoduchý jak programovací jazyky jdou. Pro neesoterické programovací jazyky může být implementace brainfuckového tlumočníka mnohem jednodušší a rychlejší, než poskytnout z ničeho nic přísný důkaz (mohu implementovat BF v několika řádcích Pythonu, ale já ‚ m si nejste jisti, kde začít s formálním důkazem, že Python je dokončen); a o desítkách esoterických jazyků inspirovaných brainfuckem je známo, že jsou úplné, protože ‚ je známo, jak se mapují na brainfuck.
• @RobertHarvey: Proč ne? Určitě by někdo, kdo navrhuje svůj vlastní jazyk, byl schopen do něj napsat kompilátor BF (pokud by to bylo nutné, a jinak by našel vhodný jiný jazyk).
• @delnan: Vy budete musíte však prokázat, že váš tlumočník BF správně implementuje specifikaci BF, IOW budete muset prokázat, že váš tlumočník BF je ve skutečnosti tlumočník BF a ne tlumočník jazyka podobného BF, který může nebo nemusí být Turing-complete.
• @ DarekNędza, že ‚ je jen přirozeným důsledkem toho, jak je definována Turingova úplnost; jakékoli rozšíření jazyka Turing Complete bude stále Turing Complete.

Systém lze považovat pouze za být Turing kompletní, pokud dokáže všechno, co univerzální Turingův stroj dokáže. Protože se říká, že univerzální Turingův stroj dokáže vyřešit jakoukoli vypočítatelnou funkci v daném čase, může to Turing Complete Systems také rozšířit.

Chcete-li zjistit, zda je něco Turingova úplné, podívejte se, zda může do něj implementovat Turingův stroj. Jinými slovy zkontrolujte, zda dokáže simulovat následující:

1. Schopnost číst a zapisovat „proměnné“ (nebo libovolná data) : Docela vysvětlující.
2. Schopnost simulovat pohyb čtecí / zapisovací hlavy : Nestačí to jen k načtení a uložení proměnných. Musí být také možné simulovat schopnost pohybovat hlavou pásky, aby bylo možné odkazovat na jiné proměnné. Toto lze často simulovat v programovacích jazycích s využitím datových struktur pole (nebo ekvivalentu) nebo v případě určitých jazyků, jako je strojový kód, schopnost odkazovat na jiné proměnné pomocí „ukazatelů“ (nebo ekvivalentů).
3. Schopnost simulovat stroj s konečným stavem : Ačkoli to není často zmiňováno, Turingovy stroje jsou ve skutečnosti variace konečných stavových strojů často používaných při vývoji AI. Alan Turing uvedl, že účelem států je simulovat různé způsoby řešení problémů osoby.
4. Stav „zastavení“ : Ačkoliv je to často zmiňovaná sada pravidel, musí být schopna se opakovat, aby se mohla považovat za Turingova úplnost, ale od formální definice toho, co je Algoritmus je stav Algoritmy musí vždy nakonec dojít k závěru. Pokud nemohou nějakým způsobem dojít k závěru, buď to není Turing kompletní, nebo uvedený algoritmus není vypočítatelnou funkcí. Turing kompletních systémů, které technicky nelze uzavřít kvůli způsobu jejich práce (například herní konzole), obejdou toto omezení tím, že budou moci nějakým způsobem „simulovat“ stav zastavení. Nesmí být zaměňována s „problémem zastavení“ „, nerozhodnutelná funkce, která dokazuje, že je nemožné vybudovat systém, který by dokázal detekovat se 100% spolehlivostí, pokud daný vstup způsobí, že jiný systém nebude mít závěr.

Toto je skutečné minimum požadavky na systém, který má být považován za Turinga úplný. Nic víc nic míň. Pokud některé z nich nemůže nějakým způsobem simulovat, není to Turing úplné. Metody, které navrhli jiní, jsou pouze prostředky do konce, protože existuje několik systémů Turing Complete, které tyto funkce nemají.

Všimněte si, že neexistuje žádný známý způsob, jak skutečně vytvořit skutečný systém Turing Complete. Je to proto, že neexistuje žádný známý způsob, jak skutečně simulovat neomezenost pásky Turingova stroje ve fyzickém prostoru.

Programovací jazyk je hotový, pokud s ním můžete provést jakýkoli výpočet.Není jen jedna sada funkcí, díky nimž je jazykové testování úplné, takže odpovědi, které říkají, že potřebujete smyčky nebo že potřebujete proměnné, jsou špatné, protože existují jazyky, které nemají ani ale jsou turing kompletní.

Alan Turing vytvořil univerzální turingův stroj a pokud můžete přeložit jakýkoli program navržený pro práci na univerzálním stroji, aby běžel ve vašem jazyce, je to také Turing complete. To také funguje nepřímo, takže můžete říci, že jazyk X je turing úplný, pokud lze všechny programy pro turing kompletní jazyk Y přeložit pro X, protože všechny programy univerzálního turingova stroje lze přeložit do programu Y.

Časová složitost , prostorová složitost, snadný formát vstupu / výstupu a snadné psaní žádný program není do rovnice zahrnut, takže takový stroj může teoreticky provádět všechny výpočty, pokud nejsou výpočty zastaveny ztrátou energie nebo Zemí pohlceno sluncem.

K prokázání úplnosti jazyka obvykle dělají tlumočníka pro jakýkoli jazyk, který dokáže prokázat úplnost jazyka, ale aby to fungovalo, potřebujete prostředky vstupu a výstupu, což jsou dvě věci, které jsou pro dosažení úplného jazyka opravdu nepotřebné. Stačí, že váš program může změnit jeho stav při spuštění a že můžete po zastavení programu zkontrolovat paměť.

Chcete-li vytvořit úspěšný jazyk, potřebujete víc než jen úplnost a toto je platí pro rovnoměrné ošetřování plachet. Nemyslím si, že BrainFuck by byl populární bez , a ..

Komentáře

• “ Programovací jazyk je dokončen, pokud můžete provést jakýkoli výpočet s tím. “ To ‚ je teze Church-Turing, nikoli to, co dělá jazyk Turing-complete.
• @Rhymoid Takže máte na mysli, že nic není úplné, pokud nemůžete udělat tlumočníka? Tj. Lambda kalkul není úplné, i když to ‚ odpovídá stejné?
• I ‚ stále hledám autoritativní definici pojmů Turingův ekvivalent a Turingův úplnost (a Turingův mocný). I ‚ div Už jsme viděli příliš mnoho případů, od lidí ve vývěskách až po výzkumníky ve vlastních prvotních ‚ příspěvcích, kteří tyto pojmy interpretují odlišně.
• Každopádně Interpretuji ‚ Turing-complete ‚ simulaci ekvivalentní Universal Turing Machine (UTM; který je zase schopen simulovat jakýkoli Turingův stroj – tedy ‚ univerzální ‚). V článku Turing ‚ z roku 1936, kde představil své stroje, definoval pojem UTM a poskytl náčrt důkazu, že UTM jsou simulací ekvivalentní Church ‚ s lambda kalkul. Tím dokázal, že mají stejnou výpočetní sílu. Teze Church-Turing jednoduše tvrdí, že “ že ‚ je veškerá výpočetní síla, kterou ‚ Vždy získá „.
• Má dvě formální definice pro Turingova stránka úplnosti Wikipedie . Jeden vyžaduje I / O a druhý ‚ t. Ten, který ‚ neříká, že stroj je turing úplný, pokud dokáže vypočítat každou Turingově vypočítatelnou funkci. Tím se kalkul lambda vrátí k úplnému dokončení, protože v kalkulu lambda můžete snadno vytvořit rovnocenný program, který počítá stejně jako všechny programy turingových strojů.

Nelze určit, zda bude smyčka nekonečná nebo zastavená.

————-

Vysvětlení: Vzhledem k určitému vstupu není možné v každém případě (pomocí jiného Turingova stroje) zjistit, zda se věc bude nekonečně opakovat nebo nakonec zastaví, s výjimkou jejího spuštění (což vám dá odpověď, pokud ano zastavit, ale ne, pokud se smyčky!).

To znamená, že musíte být schopni nějakým způsobem ukládat potenciálně neomezené množství dat – musí existovat ekvivalent nekonečné pásky, bez ohledu na to, jak spletitý! (Jinak existuje jen konečný počet stavů a pak můžete zkontrolovat, zda jste tímto stavem již dříve prošli a případně se zastavit). Obecně platí, že Turingovy stroje mohou růst nebo zmenšit velikost svého stavu některými kontrolovatelnými prostředky.

Protože Turingův původní univerzální Turingův stroj má neřešitelný problém s zastavením, musí mít váš vlastní Turingův kompletní stroj také neřešitelné zastavení problém.

Turing Complete Systems může emulovat jakýkoli jiný Turing Complete System, takže pokud si můžete vytvořit emulátor pro nějaký dobře známý Turing Complete System ve vašem systému, to dokazuje, že váš systém je také Turing Complete.

Předpokládejme například, že chcete dokázat, že Snakes & Žebříky jsou Turingovy kompletní, protože jim bude dána deska s nekonečně opakovaným vzorem mřížky (s jinou verzí nahoře) a levá strana). S vědomím, že Minsky stroj se 2 počitadly je Turing kompletní (který má 2 neomezené čítače a 1 stav z konečného počtu), můžete postavit ekvivalentní desku, kde pozice X a Y na mřížce je aktuální hodnota 2 čítačů a aktuální cesta je aktuální stav. Bang! Právě jste dokázali, že hadi & Žebříky jsou Turingovy kompletní.

Komentáře

• Nemám ‚ tento argument nekupujte. Jen proto, že problém se zastavením je pro Turingovy stroje nerozpoznatelný, přímo neznamená, že každý zápis, který vám umožňuje určit program, pro který je problém se zastavením nerozhodnutelný, je Turing úplný. Zjevně platí pouze inverzní: Pokud je notace Turing Complete, pak je samozřejmě možné psát programy, u nichž je problém zastavení nerozhodnutelný.
• It ‚ je nezbytná podmínka. Pokud se můžete rozhodnout pro každý program, zda se zastaví, jazyk není ‚ t Turing dokončen.

Jednou z nezbytných podmínek je smyčka s maximálním počtem iterací, která není určena před iterací, nebo rekurze, kde není předem určena maximální hloubka rekurze. Jako příklad lze uvést, že smyčky for … in …, jak je najdete v mnoha novějších jazycích, nejsou dostačující k tomu, aby bylo jazykové zpracování úplné (ale budou mít jiné prostředky). Všimněte si, že to neznamená omezený počet iterací nebo omezenou hloubku rekurze, ale že maximální počet iterací a hloubku rekurze je třeba vypočítat předem.

Například funkci Ackermann nelze vypočítat v jazyce bez tyto funkce. Na druhou stranu lze napsat spoustu vysoce komplexního a velmi užitečného softwaru, aniž byste tyto funkce vyžadovali.

Na druhou stranu, s každým počtem iterací a každou hloubkou rekurze počítanou dopředu, nejen lze rozhodnout, zda se program zastaví nebo ne, ale se zastaví.

vím, že to není formálně správná odpověď, ale jakmile odstraníte „minimální“ z „Turing-complete“ a vložíte „praktické“ tam, kam patří, uvidíte nejdůležitější funkce, které odlišují programovací jazyk od značkovací jazyk jsou

• proměnné
• podmínky (if / then …)
• loopage (loop / break, while …)

další com e

• anonymní a pojmenované funkce

k testování těchto tvrzení začněte značkovacím jazykem, řekněme HTML. mohli bychom vymyslet HTML + pouze s proměnnými, nebo pouze s podmíněnými (MS to udělalo s podmíněnými komentáři), nebo nějaký konstrukt smyčky (který by v případě neexistence podmíněných podmínek pravděpodobně skončil jako něco jako <repeat n="4">...</repeat>). provedením kteréhokoli z nich bude HTML + výrazně (?) výkonnější než obyčejné HTML, ale stále by to bylo spíše označení než programovací jazyk; s každou novou funkcí je činí méně deklarativním a více imperativním jazykem.

Hledání minimality v logice a programování je jistě důležité a zajímavé, ale kdybych měl učit n00bies mladé nebo staré „co programuje“ a „jak se naučit programovat“, těžko bych začal s celou šíří a šířkou teoretických základů Turingovy úplnosti. celá podstata vaření a programování dělá věci ve správném pořadí a opakuje se, dokud to není připraveno, jak to udělala tvá máma. to pro mě shrnuje.

pak jsem svůj CS nikdy nedokončil.

Komentáře

• Pokud si nejste jisti, měli byste si to nejprve prozkoumat. fractran je dokončen , stejně jako brainf * ck . Všimněte si také, že html 5 + CSS 3 je Turing kompletní, protože může implementovat pravidlo 110 .
• ano ano ano, ale všechny uvedené příklady jsou víceméně esoterické (i když možná zajímavé nebo překvapivé), m Odpověď byla pragmatická a pravděpodobně vůbec ne minimální. Myslím, že ‚ je důležité na to upozornit – tato stránka byla # 1 při hledání Turing-úplnosti na google, odpovědi zde jsou IMHO málo užitečné pro, řekněme, n00bie kdo chce vědět, co odlišuje HTML od PHP nebo Pythonu. Myslím, že brainf ck se bezdůvodně nenazývá brainf ck.