Haluaisin tietää mitä tarkoittaa Turring täydellinen ja onko sillä yhteyttä Turringin koneeseen, sekä mitä toimintoja tarvitaan ohjelmointikieleen jos se on turring täydellinen. Kysyn siksi koska olen utelias.
http://en.wikipedia.org/wiki/Turing_completeness
Turing täydelliseksi sanotaan sellaista ohjelmointikieltä, joka pystyy teoriassa laskemaan minkä tahansa laskettavissa olevan tehtävän, jos sille annetaan tarpeeksi aikaa ja muistia. Se kykenee siis samaan kuin Turingin kone.
Turingin kone on yksinkertainen laskulaite, joka voi liikuttaa nauhaa sekä lukea ja kirjoittaa merkkejä. Uskotaan kuitenkin, ettei mikään toinen mekanismi pysty laskemaan sellaista, mitä Turingin kone ei pystyisi. Jos ohjelmointikieli on Turing-täydellinen, sillä voi laskea kaiken saman kuin Turingin koneella. Lisäksi millään muulla ohjelmointikielellä ei oletuksen mukaan voi laskea enempää.
Käytännössä kaikki ohjelmointikielet ovat Turing-täydellisiä, eli kyseessä ei ole mitenkään hankalasti saavutettava ominaisuus. Jos haluaa varmistaa, että oma ohjelmointikieli on Turing-täydellinen, voi vaikkapa kirjoittaa sillä Turingin koneen simulaattorin. Jos Turingin kone pystyy laskemaan jotain, niin pystyy myös sen simulaattori.
Turing-täydellisen ohjelmointikielen voi tehdä monella tavalla, eikä ole mitään erityisiä vaatimuksia (esim. for-silmukka), jotka kielessä olisi pakko olla.
Aihe on jo aika vanha, joten et voi enää vastata siihen.