Наредни састанак Семинара биће одржан у уторак, 14. јуна 2022, у сали 301ф са почетком у 14.15 часова.
Предавач: Илир Чапуни, Природно-математички факултет Универзитета Црне Горе
Наслов предавања: КОНСТРУКЦИЈА ТУРИНГОВЕ МАШИНЕ ОТПОРНЕ НА ВЈЕРОВАТНОСНИ ШУМ
Апстракт: Поузданост израчунавања односи се на рачунање помоћу машине која је подвргнута одређеном шуму. Нас прије свега интересују пролазне грешке, тј. грешке које нијесу посљедица неког квара или трајног оштећења неке компоненте, а јављају се независно један од другог са неком малом вјероватноћом. Историјски први резултат ове врсте је рад von Neumanna који за сваки Booleovo коло $C$ величине $n$ конструише ново коло $C’$ величине $O(n\log{n})$ који са великом вјероватноћом рјешава исти задатак као и $C$, иако сваки гејт кола $C’$ може да погреши са неком малом вјероватноћом.
У овом предавању, даћемо конструкцију универзалне Туринговог машине са једном траком која може спровести произвољно дугачка израчунавања чак и уз присуство вјероватносног шума који се дефинише како слиједи: у сваком кораку, независно од претходног корака, промјена стања главе, активне ћелије и кретање главе могу, са малом вјероватноћом, бити различите од оне коју диктира програм машине. Конструкција је изненађујуће сложена и користи хијерархију симулација: машина $M_1$ симулира машину $M_2$ који симулира машину $M_3$, и тако даље.
Машина $M_1$ може “издржати” шума нивоа 1, $M_2$ може поднијети шум 2.-ог нивоа, и тако даље. Свака од ових машина може се имплементирати на универзалној машини користећи програм $p$ и ниво $k$ као улазне податке. Програм $p$ је заједнички програм за све ове машине и он је уграђен на машини $M_1$, па се исти не може оштетити од грешака. Форсираћемо све нивое да користе исти програм користећи Kleen-ову теорему о фиксној тачки. Овом конструкцијом, израчунавање које траје $t$ корака може се симулирати у $t(\log{t})^{\alpha \log{\log{\log{t}}}}$ корака уз присуство вјероватносног шума, за неку константу $\alpha$.
Коаутор овог рада је Peter Gacs.
Напомена: Састанак Семинара се може пратити на даљину преко линка
https://miteam.mi.sanu.ac.rs/asset/YoqHWKALRkRTbK9So
уколико предавач да своју сагласност.
За активно учешће неопходна је регистрација преко линка:
https://miteam.mi.sanu.ac.rs/asset/xzGqvSp7aWbg8WpYX