Теорема Райса, узагальнення проблеми зупинки, стверджує, що всі нетривіальні семантичні властивості програм нерозв'язні. Нетривіальний у цьому випадку має вузьке технічне значення: те, що щось є тривіальним (зверніть увагу на логічну інверсію), означає, що воно є істинним для всіх програм або для жодної програми.10 квітня 2024 р.
Теорема Райса в обчислювальній науці охоплює нетривіальні властивості мов, які є напіврозв’язними. У ньому стверджується, що, за винятком тривіальних властивостей, усі інші властивості цих мов нерозв’язні.
У теорії обчислюваності це стверджує теорема Райса всі нетривіальні семантичні властивості програм нерозв'язні.
Проблема зупинки полягає в тому проблема рішення щодо властивостей комп’ютерних програм на фіксованій повній за Тьюрингом моделі обчислень, тобто всі програми, які можна написати певною заданою мовою програмування, яка є достатньо загальною, щоб бути еквівалентною машині Тьюрінга.
Теорема (теорема Райса). Нехай P — мова, що складається з описів машини Тьюрінга, де P відповідає двом умовам. по-перше, P є нетривіальним — він містить деякі, але не всі описи TM. По-друге, P є властивістю мови ТМ: коли L(M1) = L(M2), ми маємо (M1) ∈ P тоді і тільки тоді, коли (M2) ∈ P.
Теорема Райса, узагальнення проблеми зупинки, стверджує, що всі нетривіальні семантичні властивості програм нерозв'язні. Нетривіальний у цьому випадку має вузьке технічне значення: те, що щось є тривіальним (зверніть увагу на логічну інверсію), означає, що воно є істинним для всіх програм або для жодної програми.