Машина на Тюринг: Разлика между версии

Горната задача е нерешима и в по-обща формулировка, известна като теорема на Райс, т.е. няма алгоритъм, който да установява еквивалентност на компютърни програми. Такъв тип нерешимост има важно практическо значение — ''не можем да създадем автоматизирани средства за проверка на коректността на компютърните програми''.

 

 

Нерешимите задачи имат пряка връзка с основите на математиката и математическата логика. Известната [[теорема на Гьодел за непълнота]], изключително важен резултат за математиката и цялата наука и философия, доказана още през 1932 г. конструира специално неразрешимо твърдение за всяка достатъчно богата формална математическа теория. Това Гьоделево твърдение, което нито може да се докаже, нито да се опровергае със формални математически методи по същество е еквивалентно на алгоритмично нерешима задача.