(no subject)

[pechkin]

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

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

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

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

Comments

Re:

[avva.livejournal.com]

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

[pechkin.livejournal.com]

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

Абыдна.