Машина на Тюринг: Разлика между версии
Изтрито е съдържание Добавено е съдържание
м robot Adding: be:Машына Т'юрынга |
|||
Ред 78:
Горната задача е нерешима и в по-обща формулировка, известна като теорема на Райс, т.е. няма алгоритъм, който да установява еквивалентност на компютърни програми. Такъв тип нерешимост има важно практическо значение — ''не можем да създадем автоматизирани средства за проверка на коректността на компютърните програми''.
Още
Нерешимите задачи имат пряка връзка с основите на математиката и математическата логика. Известната [[теорема на Гьодел за непълнота]], изключително важен резултат за математиката и цялата наука и философия, доказана още през 1932 г. конструира специално неразрешимо твърдение за всяка достатъчно богата формална математическа теория. Това Гьоделево твърдение, което нито може да се докаже, нито да се опровергае със формални математически методи по същество е еквивалентно на алгоритмично нерешима задача.
|