Tri problema koje računari (nikad) neće moći riješiti [Video]

Hoće li kakav računarski program biti pokretan u nedogled ili će eventualno stati? Za neke programe je rješenje krajnje jednostavno, nego za složenije instrukcije stvari postaju vrlo teške. Štaviše, ne postoji univerzalan način kojim bi se to moglo predvidjeti za bilo koji dati program.

Prikaži sve

Portal AnalitikaIzvor

U računarstvu, ili tačnije teoriji izračunljivosti jedan od najpoznatijih problema je upravo problem zaustavljanja (halting problem). Upravo Alan Turing je 1936. godine dokazao kako je problem neodlučiv/neizračunljiv.

Kako bi to napravio, Turing je osmislio Turingovu mašinu, apstraktni uređaj za manipulaciju znakovima/simbolima, a kojim se moglo simulirati logiku kakvog računarskog algoritma. Te mašine nikad nisu mogli riješiti problem zaustavljanja, a s obzirom da su svi računari danas u osnovi Turingove mašine – ne mogu niti oni, prenosi tportal.

Kolmogorova kompleksnost vezana za komprimovanje informacija te Wangove pločice su druga dva problema, koja je ukratko opisao video New Scientista:

(tehnologija.me)