НГУ

Форумы НГУ
Текущее время: Сб фев 16, 2019 10:02 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 8 ] 
Автор Сообщение
 Заголовок сообщения: Конструктивные узоры
СообщениеДобавлено: Пт мар 24, 2006 5:08 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Нетрудно придумать машину Тьюринга, которая всё время бежит по ленте вправо и оставляет за собой последовательность 01010101... Или, например, 0101110101110101110... Можно сказать, что она рисует на ленте некоторый узор. В связи с этим две задачки. Одну из них я, кажется, знаю, как решать, другую пока нет.

Узором будем называть любое подмножество A в N. Рассматриваем машины Тьюринга с одной лентой, которые могут рисовать на ней только символы 0 и 1. Считаем, что лента обладает левым краем и бесконечна вправо, в начале она вся заполнена нулями. В самой левой ячейке написан специальный нестираемый символ *, обозначающий начало ленты, в начале работы машины её глазок смотрит на эту ячейку.

(1) Говорим, что узор A конструктивен, если существует машина Тьюринга, которая за счётное число шагов рисует на ленте этот узор в следующем смысле. Если номер ячейки k не лежит в A, то эта ячейка никогда не меняется (и в ней остаётся 0). Если k лежит в A, то в некоторый момент ячейка меняет своё значение с 0 на 1, и после этого тоже больше не меняется. В итоге на ленте появляется узор, в котором ячейки из A равны 1, а остальные - 0.

Задача: описать все конструктивные узоры. В частности, ответить на вопрос, замкнуты ли они относительно объединений, пересечений и дополнений.

(2) Говорим, что узор A предельно-конструктивен, если некоторая машина Тьюринга рисует его так: в процессе её работы значение каждой ячейки меняется только конечное число раз, если k лежит в A, то значение ячейки с номером k в итоге оказывается равным 1, а если не лежит, то 0. Задача аналогична: описать все предельно-конструктивные узоры, выяснить, замкнуты ли они относительно объединений, пересечений и дополнений.

_________________
Не беги от снайпера - умрёшь усталым


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн апр 03, 2006 8:05 pm 
Не в сети
Частый гость

Зарегистрирован: Чт май 27, 2004 6:24 pm
Сообщения: 68
Откуда: Куликов Пётр
эти узоры - они же как бы харфункции, задают нам множество какое-то. Вот как эти множества связаны с рекурсивными?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт апр 04, 2006 12:17 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Jako писал(а):
Эти узоры - они же как бы харфункции, задают нам множество какое-то. Вот как эти множества связаны с рекурсивными?

Легко показать (это задачка для зачёта), что функция f(n,t), которая выдаёт значение ячейки с номером n после шага t, является вычислимой (aka рекурсивной), и даже примитивно вычислимой. Отсюда легко получить оценку: конструктивный узор - в.п. множество, а предельно конструктивный лежит в классе \Delta^0_2.

У меня в начале была гипотеза, что конструктивный должен быть вообще периодичным, но она оказалась весьма далёкой от правды, пример я позже напишу. Сейчас мне кажется, что он должен быть по крайней мере вычислимым, но как это доказывать?

_________________
Не беги от снайпера - умрёшь усталым


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт апр 04, 2006 2:15 pm 
Не в сети
Частый гость

Зарегистрирован: Чт май 27, 2004 6:24 pm
Сообщения: 68
Откуда: Куликов Пётр
любой конечный (то есть с конечным числом 1) - есть не периодический, вроде так? Кстати, коконечный тоже.
А Вы придумали пример бесконечного непериодического, такого что там и 0, и 1 бесконечное число?

Если не секрет, как доказать, что предельно-конструктивный лежит в классе Delta^0_2. Я доказал, что он лежит в классе Sigma^0_2, а вот принадлежность его классу Pi^0_2 что-то у меня не получается так сразу доказать :-?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт апр 06, 2006 2:52 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Под периодическим я понимал узор вида abbb..., где a,b - некоторые слова. Поэтому любой конечный и коконечный тоже периодические.

Jako писал(а):
Если не секрет, как доказать, что предельно-конструктивный лежит в классе Delta^0_2. Я доказал, что он лежит в классе Sigma^0_2...

Пусть f(n,t) - та функция, число n лежит в узоре тогда и только тогда, когда
"существует t0 такое, что для любого t >= t0 f(n,t)=1".
Это \Sigma_2-формула, заменяя 1 на 0, получим противоположное условие.

Пример такой: если B - рекурсивное множество, то B+N+N будет конструктивным узором, где A+B+C определяется подобно сумме A+B: множество чисел 3t для t из A, 3t+1 для t из B, 3t+2 для t из C. То есть никакой периодичностью тут и не пахнет, класс весьма сложен. :(

Чтобы это доказать, нужно сначала решить такую задачу: пусть у нас есть машина Тьюринга с тремя лентами, имеющими левый край и бесконечными вправо. Напомним, что у такой машины есть три глазка, по одному на каждой ленте. На вход она получает три символа - то, что видят её глазки. Сообразуясь со своим состоянием, она меняет его, меняет символы под глазками и сдвигает каждый из них влево или вправо.

Пусть первая лента находится в режиме "read only", на ней в начале пишется произвольное число k как ряд из 1. Вторая и третья в начале заполнены 0, машина, как и в случае с конструктивными узорами, может лишь менять в них 0 на 1, но не наоборот. На третьей ленте должен в конце работы быть написан ответ f(k), поэтому на ней тоже особо не разработаешься. А вторую можно использовать как рабочую, для промежуточных вычислений. Тогда на такой машине можно вычислить любую ч.р.ф. f(k).

Если это доказано, то работу такой машины можно промоделировать как построение узора B+N+N. Числа вида 3t+1 используем как ленту, на которой ведём промежуточные вычисления, она в процессе работы постепенно заполняется 1. На "ленте" 3t пишем множество B: последовательно вычисляем, лежит ли 0 в B, лежит ли 1,2,3 и т.д. А ленту 3t+2 используем как набор указателей к ленте 3t: в начале она пуста; если мы уже выяснили принадлежность чисел 0,...,k к B, то её первые k+1 клеток уже заполнены 1, и когда мы определили принадлежность k+1 к B, то идём, пишем 1 в её клетку номер k+1, и если k+1 лежит в B, то заодно ставим 1 на ленту 3t в соответсвующее место.

В итоге лента 3t+2 тоже заполнится 1.

_________________
Не беги от снайпера - умрёшь усталым


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт апр 06, 2006 3:34 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Предыдущее замечание можно обобщить так: если A вычислимо и содержит подмножество вида m+tk, где m,k постоянны, а t из N, то A - конструктивный узор.

_________________
Не беги от снайпера - умрёшь усталым


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн апр 17, 2006 8:36 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Неправда оказалась, что они вычислимы.

Пусть у нас есть некое устройство, которое выдаёт вычислимую последовательность, состоящую из команд N и P. Будем строить множество A, следуя этим командам в следующем смысле. Заводим счётчик c(t) с натуральными значениями.

Шаг 0. Множество A пусто, c(0)=0.
Шаг t+1. Считываем очередную команду. Если это N, то полагаем c(t+1)=c(t), A не меняем. Если P, то ищем наибольший x<=c(t), ещё не лежащий в A, и добавляем его к A, c(t+1)=c(t). Если такого x нет, то A не изменяется.

Ясно, что A - в.п. множество. Назовём их специальными. Легко показать, что A+N является конструктивным узором для любого специального A: в ячейках 4t+1 ведём вычисления, порождая последовательность команд, в ячейках 4t+3 ставим указатели, имитирующие рост c(t), а в 2t - строим A.

С другой стороны, A вовсе не обязано быть вычислимым. Хотя не любое в.п. множество является специальным, можно доказать, что для любого в.п. B найдётся специальное A, эквивалентное ему по Тьюрингу. Тем самым тьюринговы степени конструктивных узоров - все в.п. степени. В частности, получаем, что конструктивные узоры не замкнуты относительно дополнений.

Что-то не везёт мне на верные гипотезы. Попробую ещё раз: любой бесконечный конструктивный узор содержит подмножество вида m+tk, t из N.

_________________
Не беги от снайпера - умрёшь усталым


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн апр 17, 2006 8:38 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Для тех, кто мало знаком с машинами Тьюринга, можно указать забавную интерпретацию конструктивных узоров - задачу о покраске забора.

У нас есть забор, состоящий из досок, у него есть левый край, а правый уходит за горизонт. Забор красит маляр, которого мы снабдили инструкцией, состоящей из конечного числа пронумерованных карточек. На карточке номер 20 маляр может, например, прочитать: если доска перед тобой ещё не покрашена, покрась её, сделай шаг влево и возьми карточку 17; если же покрашена, то останься на месте и возьми карточку 12.

Вопрос: какого сорта узоры можно таким образом создать на заборе? :)

_________________
Не беги от снайпера - умрёшь усталым


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB