Miha Habič: Turingovi stroji z neskončnim časom

Povzetek. Kaj storiti s Turingovim strojem, ki se sicer ne ustavi, a morda izračunava kaj zelo zanimivega, na primer seznam kod programov, ki se ustavijo? Je smiselno cel algoritem zavreči le zato, ker stroj pač nima dovolj časa, da bi dokončal svojo nalogo?

Na seminarju si bomo ogledali formalizem Turingovih strojev z neskončnim časom, v katerem strojem dovolimo, da tečejo poljubno ordinalno število korakov. Ta izboljšava izjemno poveča računsko moč modela, odpira pa tudi nova vprašanja, ki se v končnem času ne pojavijo: koliko časa lahko program teče, kaj so možne izhodne vrednosti programa, kakšna je vloga nedeterminizma ipd.

 

 

Vabljeni!