Изменения

Перейти к: навигация, поиск

Разрешимые (рекурсивные) языки

263 байта добавлено, 02:37, 12 января 2015
Нет описания правки
}}
Другими словами, ''универсальный язык'' {{---}} это язык всех программ пар "программа и их входных данныхеё вход" таких, что программа на которых программа входе возвращает <tex>1</tex>.
Программа Так как в теории вычислимости нету структур данных, то для представления программы и её входных данных можно использовть число вида: <tex>2^{\text{code}} * 3^{\text{input}}</tex>, где <tex>code, \ input</tex> {{---}} это набор строкесть биекция между текстом программы, текстом входных данных и натуральным числом (например, занумеровав которыеможно занумеровать подряд все строки длинны <tex>1</tex>, можем получить биекцию между строками затем все строки длинны <tex>2</tex> и натуральными числамитак далее {{---}} нумерация названий столбцов в <tex>Excel</tex>).
Далее считаем, что входные данные программы и сама программа расположены над одним алфавитом <tex>\Sigma</tex>.
Множество всех рациональных чисел, меньших числа <tex>e</tex> (основания натуральных логарифмов) или <tex>\pi</tex>, разрешимо.
|proof=
Для чисел <tex>e, \ \pi</tex> существуют различные техники нахождения их точного представления, одна их которых описана в статье<ref>[http://www.mathpropress.com/stan/bibliography/spigot.pdf «A Spigot Algorithm for the Digits of Pi»статье] </ref>, таким образом, возможно получить необходимый знак чисел <tex>e, \ \pi</tex> за конечное время.
Десятичное представление рационального числа <tex>r</tex> может быть получено с любой точностью.
{{Утверждение
|statement=
множество Множество тех <tex>n</tex>, для которых в числе <tex>\pi</tex> есть не менее <tex>n</tex> девяток подряд, разрешимо.
|proof=
Предположим, что в числе <tex>\pi</tex> встречается <tex>k</tex> девяток подряд, тогда, логично, что встречается и любое число девяток меньших <tex>k</tex>.
В таком случае, разрешитель будет выглядеть следующим образом:
<tex>p_k(i) {:} </tex>
'''if''' <tex>i \leq k </tex>
'''return''' 1
'''else'''
'''return''' 0
 
Рассмотрим все программы семейства:
<tex>p_0(i) {:} </tex>
<tex>p_1(i) {:} </tex>
'''if''' <tex>i \leq leqslant 1 </tex>
'''return''' 1
'''else'''
<tex>p_2(i) {:} </tex>
'''if''' <tex>i \leq leqslant k </tex>
'''return''' 1
'''else'''
<tex>\dots</tex>
<tex>p_np_k(i) {:} </tex> '''if''' <tex>i \leq n leqslant k </tex>
'''return''' 1
'''else'''
'''return''' 0
 
<tex>\dots</tex>
По доказанному выше, какая-то программа из этого семейства будет разрешителем для искомого множества. Значит, искомое множество разрешимо.
<tex>r(x) {:} </tex>
'''if''' <tex>u(\langle x, x \rangle) == 1 </tex>
'''while''' (''true)''
'''else'''
'''return''' 1
Из предположения о разрешимости универсального языка мы пришли к противоречию.
}}
 
== Примечания ==
 
<references />
== Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA Википедия — Рекурсивный язык]
* [http://www.mathpropress.com/stan/bibliography/spigot.pdf «A Spigot Algorithm for the Digits of Pi»]
 
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/44234»

Навигация