Разрешимые (рекурсивные) языки — различия между версиями
(→Примеры разрешимых множества) |
|||
Строка 47: | Строка 47: | ||
<tex>p(r): </tex> | <tex>p(r): </tex> | ||
− | <tex>int[] \ eDigits = getDigits(e) \ // \ array \ of \ digits | + | <tex>int[] \ eDigits = getDigits(e) \ // \ array \ of \ digits \ e </tex> |
− | <tex>int[] \ rDigits = getDigits(r) \ // \ array \ of \ digits | + | <tex>int[] \ rDigits = getDigits(r) \ // \ array \ of \ digits \ r </tex> |
<tex> \mathrm{for}</tex> (i = 0 to eDigits.length()) | <tex> \mathrm{for}</tex> (i = 0 to eDigits.length()) | ||
<tex> \mathrm{if} </tex> (rDigits[i] > eDigits[i]) | <tex> \mathrm{if} </tex> (rDigits[i] > eDigits[i]) |
Версия 15:49, 9 января 2015
Содержание
Основные определения
Определение: |
Рекурсивный язык (англ. recursive language) | — язык, для которого существует программа .
Если мы рассматриваем язык как проблему, то проблема называется разрешимой, если язык рекурсивный. В противном случае проблема называется неразрешимой. Но часто данные понятия просто отождествляются.
Определение: |
Класс всех разрешимых (рекурсивных) языков часто обозначается буквой | .
Определение: |
Функция | называется вычислимой (англ. computable), если существует программа .
Определение: |
Язык | называется разрешимым, если существует такая вычислимая функция .
Определение: |
Универсальный язык (англ. universal language) | .
Примеры разрешимых множества
Лемма: |
Язык чётных чисел разрешим. |
Доказательство: |
Приведём программу, разрешающую язык чётных чисел: Заметим, что программа нигде не может зависнуть. |
Лемма: |
Множество всех рациональных чисел, меньших числа e (основания натуральных логарифмов), разрешимо. |
Доказательство: |
Воспользуемся известной формулой для вычисления числа e , с помощью которой e может быть вычислено с произвольной точностью. Приведем программу, разрешающую данный вопрос:Так как число e иррационально, то ответ будет найден. (i = 0 to eDigits.length()) (rDigits[i] > eDigits[i]) (rDigits[i] < eDigits[i]) |
Примеры неразрешимых множества
Лемма: |
Универсальный язык неразрешим. |
Доказательство: |
Приведём доказательство от противного. Пусть язык разрешим, тогда существует программа : , .Составим следующую программу: Рассмотрим вызов :
|
Источники информации
- Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
- Wikipedia — Recursive language
- Википедия — Рекурсивный язык
- Методические указания к курсу ”Сложность вычислений” Гамова А.Н.