Mikä tekee kielestä Turingin täydellisen?

A Turing tarpit on eräänlainen esoteerinen ohjelmointikieli, joka pyrkii olemaan Turingin kokonainen käytettäessä mahdollisimman vähän elementtejä. Brainfuck on ehkä tunnetuin tarpit, mutta niitä on monia.

• Iota ja Jot ovat toiminnallisia kieliä, joissa on kaksi ja kolme symbolia, perustuen SK (I) kombinaattorilaskenta .

• OISC ( Yksi käskysarjatietokone ) tarkoittaa pakollisen laskennan tyyppiä, joka vaatii vain yhden yhden tai useamman argumentin käskyn, yleensä ”vähennä ja haara, jos se on pienempi tai yhtä suuri kuin nolla” ”Käänteinen vähennys ja ohita, jos lainaa”. x86 MMU toteuttaa edellisen käskyn ja on siten Turingin täydellinen.

Yleensä välttämätön kieli on Turing-täydellinen, se tarvitsee:

1. Ehdollisen toiston tai ehdollisen hypyn muodon (esim. while, if + goto)

2. Tapa lukea ja kirjoittaa jonkinlainen tallennustila (esim. , muuttujat, nauha)

Jos lambda-calculus -pohjainen toiminnallinen kieli on TC, se tarvitsee:

1. Kyky abstraktiota toimintoja argumenttien yli (esim. lambda-abstraktio, lainaus)

2. Kyky soveltaa toimintoja argumentit (esim. pelkistys)

Laskennan tarkasteluun on tietysti muita tapoja, mutta nämä ovat yleisiä malleja Turingin tarpiteille. Huomaa, että todelliset tietokoneet eivät Turingin yleiskoneita , koska niillä ei ole rajoittamatonta tallennustilaa. Tarkkaan ottaen ne ovat ”rajoitettuja varastointikoneita”. Jos jatkat muistin lisäämistä niihin, he lähestyisivät asymptoottisesti vallassa olevia Turingin koneita. Jopa rajatut tallennuslaitteet ja rajalliset tilakoneet ovat kuitenkin hyödyllisiä laskennassa; ne eivät yksinkertaisesti ole universaaleja .

Tarkkaan ottaen I / O: ta ei vaadita Turingin täydellisyyteen; TC vain väittää, että kieli voi laskea haluamasi toiminnon, ei että se voi näyttää tuloksen. Käytännössä jokaisella hyödyllisellä kielellä on tapa olla vuorovaikutuksessa maailman kanssa jollain tavalla.

Kommentit

• Riittävätkö yksinkertaiset muuttujat välttämättömille kielille? Minusta tuntui, että jonkinlainen kokoelma (esim. Taulukot tai linkitetyt luettelot) olisi tarpeen.
• @luiscubal sinun on pystyttävä määrittämään mielivaltainen määrä tietoa. Yksinkertaisilla muuttujilla voit edustaa muuttujien itsellään olevan tiedon määrää. Entä jos sinun on esitettävä N + 1 erilaista tietoa. Voidaan väittää, että -temppuilla kuten Fractran pelaa, voit tehdä sen jopa yksinkertaisilla muuttujilla … mutta että ’ eivät ole aivan mitä ’ kysyt.
• Ei ’ vaadi, että kielen on tuettava ENDLESS -silmukat?
• Re, ” jokaisella hyödyllisellä kielellä on tapa olla vuorovaikutuksessa maailman kanssa. ” Algol 60: lla ei ollut mitään määriteltyä tapaa olla vuorovaikutuksessa maailman kanssa. Kaikki Algol 60 -ohjelmasi I / O-toiminnot tehtiin kutsumalla kirjastotoimintoja, ja kirjastotoiminnot voisivat olla täysin erilaiset eri toteutuksissa. Voin kuitenkin vedota itseäni keskusteluun siitä, oliko Algol 60 ” hyödyllinen. ”

Käytännön näkökulmasta: jos pystyt kääntämään kaikki ohjelmat Turingin koko kielellä omalle kielellesi, niin (niin pitkälle kuin Tiedän), sinun kielesi on oltava Turing-täydellinen.Siksi, jos haluat tarkistaa, onko suunnittelemaasi kieli Turing-täydellinen, voit yksinkertaisesti kirjoittaa Brainf *** YourLanguage-kääntäjälle ja todistaa / osoittaa, että se pystyy kokoamaan kaikki lailliset BF-ohjelmat.

tarkennan, tarkoitan, että YourLanguage-tulkin lisäksi kirjoitat kääntäjän (millä tahansa kielellä), joka voi kääntää minkä tahansa BF-ohjelman YourLanguage-kielelle (tietenkin samalla semantiikalla).

Kommentit

• Kyllä, se olisi ehdottomasti käytännöllisin tapa lähestyä sitä. </sarcasm>
• @RobertHarveyilla on asia, mutta yleinen ajatus on melko tärkeä. Brainfuckin on osoitettu olevan täydellinen ja hyvin yksinkertainen ohjelmointikielien mukaan. Muille kuin esoteerisille ohjelmointikielille aivotulkin käyttöönotto voi olla paljon helpompaa ja nopeampaa kuin ankaran todistuksen antaminen tyhjästä (voin toteuttaa BF: n muutamassa Python-rivissä, mutta I ’ m ole varma, mistä aloittaa muodollisella todisteella siitä, että Python toimii täydellisesti); ja kymmenien esoteeristen brainfuck-innoittamien kielten tiedetään olevan täydellisiä, koska ’ tiedetään, miten he kartoittavat aivotapahtumia.
• @RobertHarvey: Miksi ei? Varmasti joku, joka suunnittelee omaa kieltään, pystyy kirjoittamaan siihen BF-kääntäjän (jos se on välttämätöntä, ja löytää muuten sopivan muun kielen).
• @delnan: Sinä pystyt on kuitenkin todistettava, että BF-tulkisi toteuttaa oikein BF-määrityksen, IOW sinun on osoitettava, että BF-tulkisi on itse asiassa BF-tulkki eikä BF-tyyppisen kielen tulkki, joka saattaa olla tai ei välttämättä Turing-täydellinen.
• @ DarekNędza, että ’ on vain luonnollinen seuraus siitä, miten täydentäminen on määritelty; kaikki Turing Complete -kielen laajennukset ovat edelleen Turing Complete.

Järjestelmää voidaan harkita vain olla Turingin täydellinen, jos se pystyy tekemään mitä tahansa yleinen Turingin kone. Koska universaalin Turing-koneen sanotaan pystyvän ratkaisemaan minkä tahansa laskettavan funktion tietyssä ajassa, myös Turingin kokonaiset järjestelmät voivat tehdä niin.

Jos haluat tarkistaa, onko jokin Turingin valmis, katso jos osaa toteuttaa sen sisällä Turingin koneen. Toisin sanoen tarkista, voiko se simuloida seuraavia:

1. Kyky lukea ja kirjoittaa ”muuttujia” (tai mielivaltaisia tietoja) : Melkein itsestään selittävä.
2. Kyky simuloida luku- / kirjoituspään siirtämistä : Se ei riitä muuttujien hakemiseen ja tallentamiseen. Nauhan pään siirtämisen on myös oltava mahdollista simuloida muiden muuttujien viittaamiseksi. Tätä voidaan usein simuloida ohjelmointikielissä käyttämällä matriisitietorakenteita (tai vastaavia) tai tiettyjen kielten, kuten konekoodin tapauksessa, kykyä viitata muihin muuttujiin ”osoittimien” (tai vastaavien) avulla.
3. Kyky simuloida äärellistä tilakonetta : Vaikka Turingin koneita ei mainita usein, ne ovat tekoälyn kehittämisessä usein käytettyjen äärellisten tilakoneiden vaihtelu. Alan Turingin mukaan tilojen tarkoituksena on simuloida henkilön erilaisia ongelmanratkaisumuotoja.
4. ”pysäyttää” tila : Vaikka siinä usein mainitaankin, joukon sääntöjä on kyettävä toistamaan itsensä, jotta sitä voidaan pitää Turingin täydellisenä, se ei todellakaan ole hyvä kriteeri, koska muodollinen määritelmä algoritmi on tila-algoritmien on aina lopulta tehtävä lopputulos. Jos ne eivät pääse jollakin tavalla, joko se ei ole Turingin täydellinen, tai mainittu algoritmi ei ole laskettavissa oleva funktio. Täydellisten järjestelmien, joita teknisesti ei voida tehdä johtuen toimintatavastaan (kuten esimerkiksi pelikonsolit), kiertäminen kiertää tämän rajoituksen kykenemällä ”simuloimaan” pysäytystilaa jollain tavalla. Ei pidä sekoittaa ”pysäytysongelmaan” ”, joka on ratkaisematon toiminto, joka osoittaa, että on mahdotonta rakentaa järjestelmää, joka voisi havaita 100-prosenttisesti luotettavasti, jos tietty syöttö ei johda toiseen järjestelmään.

Nämä ovat todellinen minimi vaatimukset, jotta järjestelmää voidaan pitää Turingin täydellisenä. Ei enempää eikä vähempää. Jos se ei voi simuloida mitään näistä jollakin tavalla, se ei ole Turingin täydellinen. Menetelmät, joita muut ihmiset ehdottavat, ovat vain keinoja loppuun saakka, koska on olemassa useita Turingin kokonaisia järjestelmiä, joilla ei ole näitä ominaisuuksia.

Huomaa, että todellisen Turingin koko järjestelmän rakentamiseen ei tunneta mitään tapaa. Tämä johtuu siitä, että ei ole tunnettua tapaa aidosti simuloida Turingin koneen nauhan rajattomuutta fyysisessä tilassa.

Ohjelmointikieli on valmis, jos voit tehdä mitään laskelmia sillä.Ei ole vain yhtä ominaisuusjoukkoa, joka tekee kielestä täydellisen, joten vastaukset sanovat, että tarvitset silmukoita tai tarvitset muuttujia, ovat väärässä, koska on kieliä, joilla ei ole kumpaa mutta ovat valmiita.

Alan Turing teki universaalikoneen, ja jos pystyt kääntämään minkä tahansa ohjelman, joka on suunniteltu toimimaan universaalikoneella toimimaan omalla kielelläsi, se on myös Turing valmis. Tämä toimii myös epäsuorasti, joten voit sanoa, että kieli X on valmis, jos kaikki ohjelmat täydellisen kielen Y kirjoittamiseksi voidaan kääntää X: lle, koska kaikki yleiskäyttöiset koneohjelmat voidaan kääntää Y-ohjelmaan.

Ajan monimutkaisuus , avaruuden monimutkaisuus, helppo syöttö- ja tulostusmuoto ja helppo kirjoittaa mikä tahansa ohjelma ei sisälly yhtälöön, joten tällainen kone voi teoreettisesti tehdä kaikki laskelmat, ellei laskelmia pysäytä tehohäviö tai maapallon nielemä aurinko.

Tavallisen täydellisyyden osoittamiseksi he tekevät tulkin kaikille todistetusti täydelliselle kielelle, mutta sen toimimiseksi tarvitaan syöttö- ja tulostustavat, kaksi asiaa, joita ei todellakaan vaadita, jotta kieli olisi täydellinen. Se riittää, että ohjelmasi voi muuttaa sen tilaa käynnistyksen yhteydessä ja että voit tarkistaa muistin ohjelman pysäyttämisen jälkeen.

Menestyksellisen kielen tekemiseksi se vaatii kuitenkin muutakin kuin täydellisyyttä. totta jopa turisteille. En usko, että BrainFuck olisi ollut suosittu ilman , ja ..

Kommentit

• ” Ohjelmointikieli on valmis, jos voit tehdä laskutoimituksia ” Tämä ’ on kirkon-turingin tutkielma, ei mikä tee kielestä turingin-täydellinen.
• @Rhymoid Joten tarkoitat, että mikään ei ole täydellinen, ellei voit tehdä tulkkia? Eli. Lambda-laskenta ei ole täydellinen, vaikka se olisi ’ vastaava?
• I ’ m etsin edelleen arvovaltaista määritelmää termeille Turing-ekvivalentti ja Turing-täydellinen (ja Turing-voimakas). I ’ olemme jo nähneet liian monta tapausta, ilmoitustauluilla olevista ihmisistä tutkijoille omissa friggin ’ -lehdissään, jotka tulkitsevat näitä termejä eri tavalla.
• Joka tapauksessa, Tulkitsen ’ Turing-complete ’ simulointina, joka vastaa Universal Turing Machine (UTM; joka puolestaan pystyy simuloimaan mitä tahansa Turingin konetta – siten ’ universal ’). Turingin ’ paperissa vuodelta 1936, jossa hän esitteli koneensa, hän määritteli UTM-käsitteen ja antoi luonnoksen todisteesta siitä, että UTM-laitteet ovat simulaatioita vastaavia kirkon ’ s lambda-laskenta. Tekemällä niin hän osoitti, että heillä oli sama laskentavoima. Church-Turingin väitöskirjassa väitetään yksinkertaisesti, että ” että ’ on kaikki laskentatehosi, joka sinulla on ’ ll koskaan saa ”.
• Siinä on kaksi muodollista määritelmää Wikipedian Turingin täydellisyys -sivulle. . Yksi vaatii I / O: n, toinen ei ’ t. Se, joka ’ ei sano, että kone on valmis, jos se pystyy laskemaan kaikki Turingin laskettavat toiminnot. Se palauttaa lambda-laskennan takaisin täydelliseksi, koska lambda-laskennassa voit helposti tehdä samanarvoisen ohjelman, joka laskee saman kuin kaikki muut koneohjelmat.

Et voi kertoa, jatkuuko se loputtomasti vai pysähtyykö.

————-

Selitys: Joitakin syötteitä käytettäessä on mahdotonta kertoa jokaisessa tapauksessa (toista Turingin konetta käytettäessä), jos asia silmukkaa loputtomasti tai lopettaa lopulta, paitsi suorittamalla sen (mikä antaa sinulle vastauksen, jos pysäytä, mutta ei, jos se silmukkaa!).

Tämä tarkoittaa, että sinun on pystyttävä tallentamaan mahdollisesti rajoittamaton määrä tietoja jollain tavalla – äärettömän nauhan on oltava vastaava (muuten tiloja on vain rajallinen määrä ja sitten voit tarkistaa, oletko käynyt läpi kyseisen tilan aiemmin ja lopulta lopetat). Yleensä Turingin koneet voivat kasvaa tai pienentää tilansa kokoa jollakin hallittavalla tavalla.

Koska Turingin alkuperäisellä universaalilla Turing-koneella on ratkaisematon pysähtymisongelma, omalla Turing-koneellasi on oltava myös ratkaisematon pysäytys ongelma.

Turingin täydelliset järjestelmät voivat jäljitellä mitä tahansa muuta Turingin täydellistä järjestelmää, joten jos pystyt rakentamaan emulaattorin jollekin tunnetulle Turingin koko järjestelmälle järjestelmässäsi, se osoittaa, että järjestelmäsi on myös Turingin täydellinen.

Oletetaan esimerkiksi, että haluat todistaa, että käärmeet & Ladders on Turing valmis, kun taululle annetaan äärettömän toistuva ristikkokuvio (yläosassa eri versio) ja vasemmalla puolella). Kun tiedät, että 2-laskuri Minsky-kone on Turing valmis (jolla on 2 rajoittamatonta laskuria ja 1 tila lopullisesta numerosta), voit rakentaa vastaavan levyn, jossa X- ja Y-sijainti ruudukossa on 2 laskurin nykyinen arvo ja nykyinen polku on nykyinen tila. Pamaus! Todistit juuri, että käärmeet & Tikkaat ovat valmistumassa.

Kommentit

• En ’ t osta tätä argumenttia. Se, että pysähtymisongelmaa ei voida ratkaista Turingin koneiden kohdalla, ei tarkoita suoraan, että jokainen merkintätapa, jonka avulla voit määrittää ohjelman, jolle pysäytysongelmaa ei voida päättää, on Turingin täydellinen. Vain käänteinen on ilmeisesti totta: Jos merkintätapa on Turingin täydellinen, on tietysti mahdollista kirjoittaa ohjelmia, joiden pysäyttämisongelma on ratkaisematon.
• Se ’ välttämätön kunto. Jos pystyt päättämään jokaisen ohjelman kohdalla, pysähtykö se, kieli ei ole ’ t Turing valmis.

Yksi välttämätön ehto on silmukka, jolla on suurin iterointiluku, jota ei määritetä ennen iteraatiota, tai rekursio, jossa enimmäisrekursiosyvyyttä ei määritetä eteenpäin. Esimerkiksi … in … -silmukat, jotka löydät monista uudemmista kielistä, eivät riitä tekemään kielestä täydellistä (mutta niillä on muita keinoja). Huomaa, että tämä ei tarkoita rajoitettua määrää iteraatioita tai rajoitettua rekursiosyvyyttä, mutta suurin iteraatio ja rekursiosyvyys on laskettava etukäteen.

Esimerkiksi Ackermann-toimintoa ei voida laskea kielellä ilman Toisaalta voidaan kirjoittaa monia erittäin monimutkaisia ja erittäin hyödyllisiä ohjelmistoja tarvitsematta näitä ominaisuuksia.

Toisaalta jokaisella iterointiluvulla ja jokaisella rekursiosyvyydellä lasketaan eteenpäin, ei vain voidaanko päättää, pysähtyykö ohjelma vai ei, mutta se pysähtyy .

tiedän, että tämä ei ole muodollisesti oikea vastaus, mutta kun otat ”minimaalisen” pois ”Turing-täydellinen” -kohdasta ja laitat ”käytännöllisen” takaisin mihin se kuuluu, näet tärkeimmät ominaisuudet, jotka erottavat ohjelmointikielen merkintäkieli ovat

• muuttujat
• ehdolliset (jos / sitten …)
• silmukka (silmukka / tauko, kun taas …)

seuraava com e

• nimettömät ja nimetyt toiminnot

testataksesi näitä väitteitä, aloita merkintäkielellä, esimerkiksi HTML: llä. voisimme keksiä HTML +: n vain muuttujilla tai vain ehdollisilla (MS teki sen ehdollisilla kommenteilla) tai jonkinlaisen silmukkarakenteen (joka ilman ehdollisia päätyisi todennäköisesti sellaiseksi kuin <repeat n="4">...</repeat>). minkä tahansa näistä tekeminen tekee HTML +: sta huomattavasti (?) tehokkaamman kuin tavallinen HTML, mutta se olisi silti enemmän merkintöjä kuin ohjelmointikieli; jokaisella uudella ominaisuudella teet siitä vähemmän deklaratiivisen ja enemmän imperatiivisen kielen.

Minimaalisuuden tavoittelu logiikassa ja ohjelmoinnissa on varmasti tärkeää ja mielenkiintoista, mutta jos minun piti opettaa n00bies nuorille tai vanhoille ”mitä on ohjelmointi” ja ”kuinka oppia ohjelmoimaan”, tuskin aloitan Turingin täydellisyyden teoreettisten perusteiden koko leveydellä ja leveydellä. koko ruoanlaiton ja ohjelmoinnin ydin on tavaroiden tekeminen oikeassa järjestyksessä, toistaminen, kunnes se on valmis, kuten äitisi teki. tämä noin tiivistää sen minulle. / p>

sitten en ole koskaan saanut valmiiksi CS: ääni.

Kommentit

• Jos et ole varma, sinun kannattaa tutkia se ensin. fractran on turing valmis , samoin kuin brainf * ck . Huomaa myös, että html 5 + CSS 3 on valmis, koska se voi toteuttaa sääntö 110 .
• kyllä kyllä, tiedän. mutta kaikki esitetyt esimerkit ovat enemmän tai vähemmän esoteerisia (vaikka ehkä mielenkiintoisia tai yllättäviä), m y vastaus oli käytännöllinen, eikä luultavasti ollenkaan vähäinen. mielestäni ’ on tärkeää huomauttaa tästä – tämä sivu oli ykkönen, kun etsitään Turingin täydellisyyttä Googlesta, tässä olevat vastaukset ovat IMHO, jolla ei ole juurikaan hyötyä esimerkiksi sanalle n00bie kuka haluaa tietää, mikä erottaa HTML: n PHP: stä tai Pythonista. tarkoitan, brainf ck: tä ei kutsuta brainf ck: ksi ilman syytä.