Teadusteave MTÜ – MIS ON ARVUTITEADUS?/Jaan Penjam

Arvutiteadus püüab vastata küsimusele, kas mingi ülesanne on algoritmiliselt lahendatav. On lahendatavaid ülesandeid. On lahendamatuid ülesandeid. On praktiliselt lahendamatuid ülesandeid, mis võtaksid näiteks nii palju aega, kui Universum siiani eksisteerinud on. Nii näiteks on pangakaardi salasõna lahtikodeerimine ülesanne, mida arvutiga pole praktiliselt võimalik lahendada. On aga selliseid ülesandeid, mille kohta pole teada, kas need on lahendatavad või need pole lahendatavad. Pole teada lahendamise algoritmi ega ka lahenduskiirust. Võibolla on need ülesanded lihtsamatele taandatavad, võibolla teisendatavad. Kuid neid oleks vaja lahendada. Nagu näiteks keeruliste toimingute planeerimine, ilma ennustamine. Kas on aga ülesandeid, mille kohta ei saagi öelda, kas nad on lahendatavad või need pole lahendatavad? Arvutiteadus selliseid ei käsitle, eeldatakse ikka lõpliku arvu muutujaid, mitte lõpmatut arvu muutujaid.

Vt arvutisüsteemide tippkeskuse kohta http://cdc.ioc.ee