Вопросы по теории языков и МТ

[ShMaxG]

Второй вариант. Такое множество неперечислимо потому что мы не можем проверить это свойство на любых словах?

[Профессор Снэйп]

ShMaxG писал(а):

Второй вариант. Такое множество неперечислимо потому что мы не можем проверить это свойство на любых словах?

Не совсем понял Ваш аргумент, но думаю, Вы не правы. Возможность проверить --- это разрешимость, а перечислимость --- это возможность дождаться некоторого события. Ну, или если угодно, тоже возможность "проверить", но в несколько другом смысле. Разрешимость --- это возможность получить любой из возможных ответов за конечное время, как положительный ответ, так и отрицательный. А перечислимость --- это возможность получить положительный ответ за конечное время, но при этом может оказаться, что отрицательный ответ получить невозможно. Как с проблемой остановки: если МТ останавливается (на пустом входе), то через конечное число шагов мы об этом узнаём, а если нет, то не узнаём никогда.

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

Это интуиция. Если же хотите более-менее строгое решение --- устройте $m$-сводимость дополнения проблемы остановки к множеству МТ, не сдвигающих головку влево в процессе работы. Как это делается, Вам должно быть ясно из уже имеющихся в этой теме примеров. Если не получится --- обращайтесь, поможем

[ShMaxG]

Ага, попробую так. Построим МТ M, которая осуществляет такую m-сводимость. Пусть она следит за некоторой МТ M': если M' останавливается на пустом слове, то М делает шаг влево, иначе - стоит на месте.

[Профессор Снэйп]

ShMaxG писал(а):

Ага, попробую так. Построим МТ M, которая осуществляет такую m-сводимость. Пусть она следит за некоторой МТ M': если M' останавливается на пустом слове, то М делает шаг влево, иначе - стоит на месте.

По-моему, нормально. Хотя можно придраться вот к чему... Что значит, что одна МТ "следит" за другой МТ? Вряд ли можно "следить" за движениями, стоя на месте

Добавлено спустя 9 минут 42 секунды:

Боюсь, что в технической реализации вопрос более сложен, чем кажется. К примеру, если мы в задаче заменим "сдвигает головку влево" на просто "сдвигает головку", то ничего уже не получится. Ибо машины, вообще не сдвигающие головку, представляют из себя просто конечный автомат. Алфавиты-то конечны, как внешний, так и внутренний! Бесконечность памяти на МТ достигается исключительно за счёт бесконечности ленты!!!

Надо начинать вникать в детали. Что за машина, сколько лент, какие команды допустимы?.. Может, кстати, я и ошибся. Всё-таки если машина ни разу не ходит по ленте влево, то получается, что она вообще не обращается к сохраняемым по ходу вычисления данным. Вся память у неё получается сосредоточенной во внутренних состояниях и в символе на текущей ячейке, то есть оказывается конечной. Это очень плохо

Н-да, в натуре ошибся! Вот ведь как первое впечатление от задачи бывает обманчиво!!!

Добавлено спустя 8 минут 9 секунд:

Короче, множество МТ, не сдвигающих головку влево, оказывается не то что перечислимым, а даже разрешимым. Просто потому, что комбинаций "символ в ячейке + состояние головки" конечное число и момент, когда машина либо застывает на месте, либо начинает двигаться вправо, периодически записывая на ленте одно и то же слово, отслеживается за конечное время.

Это, конечно, если у машины всего одна лента. А если лент несколько и движение головки влево на одних лентах допускается, а на других нет, то тут уже Ваше сведение работает.

[ShMaxG]

Сейчас читаю про класс P, причем мы проходим "более узкий класс функций, а именно класс предикатов, функций

$$ f:\sum {^* } \to \left\{ {0,1,*} \right\} $$

, где * - разделитель".
Например, в википедии написано, что язык

$$ L \in P $$

, если для

$$ L $$

существует распознающий его предикат из P. Не понятно, что значит распознающий? Т.е. существует предикат, который равен 1 на словах из языка и 0 на словах не из языка, причем вычисляющийся за полиномиальное время?

Добавлено спустя 3 минуты 49 секунд:

И эквивалентно ли это существованию МТ, на вход которой подается слово, и эта МТ говорит "да" если это слово из этого языка и "нет", если не из этого и время ее работы полиномиально?

[Xaositect]

ShMaxG в сообщении #197788 писал(а):

Например, в википедии написано, что язык

$$ L \in P $$

, если для

$$ L $$

существует распознающий его предикат из P. Не понятно, что значит распознающий? Т.е. существует предикат, который равен 1 на словах из языка и 0 на словах не из языка, причем вычисляющийся за полиномиальное время?

Да

ShMaxG в сообщении #197788 писал(а):

И эквивалентно ли это существованию МТ, на вход которой подается слово, и эта МТ говорит "да" если это слово из этого языка и "нет", если не из этого и время ее работы полиномиально?

Да

[Профессор Снэйп]

ShMaxG писал(а):

Не понятно, что значит распознающий? Т.е. существует предикат, который равен 1 на словах из языка и 0 на словах не из языка, причем вычисляющийся за полиномиальное время?

Ну да, вроде так. Только почему предикат? Функция тогда уж. Характеристическая функция предиката

Теория сложности --- это вообще отдельная песня...

Можно, если не секрет, причину Вашего интереса к вычислимости? Просто хотите разобраться в курсе, который вам читают, или что-то большее?

[ShMaxG]

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

[Профессор Снэйп]

Мне вот что показалось странным. Если брать чистую вычислимость (вычислимость за конечное время, без всякой оценки числа шагов вычисления), то традиционно её "переводят" на натуральные числа. Доказывают сначала, что функция частично рекурсивна тогда и только тогда, когда она вычислима на МТ, а затем продолжают делать всё на натуральном ряде, пользуясь чисто математическими приёмами работы с чрф. На машины почти не ссылаются. Если надо производить алгоритмические преобразования над объектами, отличными от натуральных чисел, используют гёделевскую нумерацию. А у Вас как-то всё через машины...