Разрешимые (рекурсивные) языки — различия между версиями
(Новая страница: «{{Определение |definition=Язык <tex>L</tex> называется '''разрешимым''' ('''рекурсивным'''), если существу...») |
|||
| Строка 2: | Строка 2: | ||
|definition=Язык <tex>L</tex> называется '''разрешимым''' ('''рекурсивным'''), если существует такая программа <tex> p </tex>, что <tex> \forall w \in L: p(w) = 1</tex> и <tex> \forall w \notin L: p(w) = 0</tex>. | |definition=Язык <tex>L</tex> называется '''разрешимым''' ('''рекурсивным'''), если существует такая программа <tex> p </tex>, что <tex> \forall w \in L: p(w) = 1</tex> и <tex> \forall w \notin L: p(w) = 0</tex>. | ||
}} | }} | ||
| + | |||
| + | =Примеры= | ||
| + | ==Пример разрешимого множества== | ||
| + | ==Пример неразрешимого множества== | ||
Версия 05:51, 14 декабря 2011
| Определение: |
| Язык называется разрешимым (рекурсивным), если существует такая программа , что и . |
