(no subject)

[pechkin]

В голове - computability. Как, ну как доказать, что рекурсивные языки (существует алгоритм проверки принадлежности каждого слова к языку) замкнуты на итерацию? То есть, можно написать программу, которая будет каждое слово разбивать рекурсивно на части разной длины, перебирая все возможные комбинации подстрок (включая пустую?) и проверяя каждую на принадлежность к языку -- но не слишком ли длинная получится программа (на языке S, описанном в книжке, описанной в одном из недавних постингов Аввы), чтобы не существовало более простого и эффектного решения?

Хайфа. Полнолуние, начинающаяся пыльная буря. Св.Патрик. Майкл, бритый, хороший такой. Молодые новые ребята у него. Должно быть, неплохо играли - опоздал я на два часа. Чертовы таксисты.

Хайфу каждый раз не узнать, все время какой-нибудь новый небоскреб находишь на месте старых домиков. Видимо, действительно, кончились права бывших владельцев, и дома активно сносят. Жаль немного.

В голове - חישוביות, и Алкистис Протопсалти поет стихи Элефтерии Арванитаки на музыку Горана Бреговича.

Comments

[avva.livejournal.com]

То есть, можно написать программу, которая будет каждое слово разбивать рекурсивно на части разной длины, перебирая все возможные комбинации подстрок

Ну да. Пусть будет рекурсивная функция, получающая на входе слово длиной N, перебирающая все возможные подстроки длиной от 1 до N, и для каждой проверяющая принадлежность подстроки к языку, а потом рекурсивно вызывающая себя для того, что осталось.

Пустую подстроку проверять не надо, т.к. если слово подходит по разбивке без неё, то этого достаточно; а если не подходит по разбивке без неё, то и с ней не подойдёт.

Длинно-то оно, может, длинно, но какая разница? Или нужно действительно руками такую программу написать? Тогда сложнее.

Re:

[pechkin.livejournal.com]

Нет, я так решил, что писать не надо.

А вот: есть предикат q(x)=FORALL y p(x, y); он невычислимый; дать пример такого p(x, y) предиката, чтобы был вычислимый. Это, правда, бонус-вопрос.

Re:

[avva.livejournal.com]

"p(x,y) верно, если машина, закодированная числом x, не останавливается за первые y шагов".

[pechkin.livejournal.com]

Вау. Вот, черт побери! как людям приходят в голову такие мысли, и почему они не приходят в голову мне? чем я, черт побери, от них отличаюсь?

Абыдна.