Keskustelu:Turingin kone

Lähdeluettelo olisi paikallaan. --Juha Kämäräinen 1. maaliskuuta 2006 kello 17.44 (UTC)

Aikavaativuusluokat P ja NP sekä niiden kuuluisa avoin samuusongelma olisi hyvä mainita. Ensin pitäisi(?) vain esitellä epädeterministinen Turingin kone sekä algoritmiin käytettävä aika jne. Toinen vaihtoehto olisi mainita ne kompleksisuusteorian tai laskettavuusteorian puolella. --Timo Aho 7. lokakuuta 2006 kello 20.29 (UTC)

Täällä on mm. artikkelit P=NP sekä P (vaativuusluokka), jos et huomannut. Toki ne voi mainita muissakin artikkeleissa, en tiedä asiasta sen enempää. -Aslak 7. lokakuuta 2006 kello 20.32 (UTC)

Totta. Hieno juttu, enpäs huomannut vaikka mielestäni etsiskelin. Pitääpä laajentaa niitä. --Timo Aho 10. lokakuuta 2006 kello 07.40 (UTC)

Kiinnitin huomiota väitteeseen, että Turingin kone ratkaisee vain kyllä/ei-päätöstehtäviä: Kone ratkaisee päätöstehtäviä, tehtäviä joihin vastaus on koneen lopputilan mukaan kyllä tai ei. Ratkaisu voidaan lukea koneen tilasta sen pysähtyessä. Päätöstehtäviä ovat esimerkiksi "onko luku 3 suurempi kuin 10?" tai "onko 745 alkuluku?". Esimerkki tehtävästä, joka ei ole päätöstehtävä: "Mikä luvuista 1, 3 ja 10 on pienin?". Mihin väite perustuu? Väitehän on ristiriidassa Churchin-Turingin teesin kanssa; Turingin koneella ratkaistavien ongelmien joukkohan on nimenomaan sama kuin algoritmisesti ratkeavien ongelmien joukko. Ei neliöjuuren tai planeettojen kiertoratojen laskeminen ole päätöstehtävä, vai? Kommentteja? --Nisku 20. marraskuuta 2008 kello 00.47 (EET)

Kyllä Turing-kone ratkaisee muitakin kuin kyllä/ei-päätöstehtäviä, ja tämä on ainakin minun monisteessani (yliopisto-matematiikan syventävä kurssi automaattiteoriasta) kerrottu. Se tapahtuu esimerkiksi tällä tavalla (eri variaatioita on olemassa). Merkitköön qH koneen hyväksymistilaa ja * nauhan tyhjäkohtaa (joita siis syötteen vasemmalla ja oikealla puolella on äärettömän pitkälle). Olkoon esimerkin vuoksi nauhassa muina symboleina bitit 0 ja 1. Olkoon nauhan konfiguraatio hyväksymistilaan saavuttaessa vaikkapa "***0011001(qH0)011101***" (missä *:t jatkuvat vasemmalle ja oikealle äärettömyyteen), eli "koneen asema" on hyväksymistilaan tultaessa viidennen nollan päällä. Tästä luetaan vastauksen arvo yksinkertaisesti niin, että luetaan järjestyksessä ne vasemmanpuoleisen äärettömän pitkän *-jonon jälkeen tulevat symbolit, jotka ovat ennen pysähtymistilassa olevaa "koneen asemaa". Esimerkissäni vastaukseksi saataisiin siis bittijono 0011001, eli vastaus voi siis olla monipuolisempi kuin pelkkä kyllä/ei. Tällaiset vastausjonot voidaan sitten tulkita vaikkapa erilaisina vastaukseksi saatavina desimaalilukuina. NettiKirjoittaja 18. kesäkuuta 2009 kello 23.03 (EEST)

Ei muka muistuta nykyaikaisia tietokoneita

Nykyaikaisten tietokoneiden toimintaperiaate muistuttaa erittäin paljon Turingin koneiden periaatteita. Asiaa havainnollistaa paljon se, jos korvaa abstraktin 'tilan' käsitteen koneen rekisterien sisällöllä, 'nauhan' muistilla ja 'säännöstön' konekielikäskyjen joukolla, tekemällä lisäoletus, että yksi tai useampi rekistereistä saattaa viitata johonkin nauhan kohtaan.

Mikko Nummelin (keskustelu) 13. joulukuuta 2012 kello 23.09 (EET)

Sopii etsiä lähteitä ja viitteitä suuntaan tai toiseen. Ipr1 (keskustelu) 7. helmikuuta 2020 kello 15.48 (EET)