alt text

Какие могут быть контрпримеры?

1) Приходит в голову функция деления. Программа, вычисляющая её, работает по такому принципу: принимает x,y и для каждого k=0,1,2,...,y проверяет, верно ли x+..+x (k раз) = y. Это так?

2) Рассмотрим функцию $%f: N\to N$% которая переводит x в 1 если программа х останавливается на входе х и в 0, если не останавливается. Это тотальная невычислимая функция. Так?

3) Эта функция вычисляется такой программой: принимается х и выдается f(x).

4) Рассмотрим функцию $%f:N-\{0\}\to N$%, которая переводит x в 1 если программа х останавливается на входе х и в 0, если не останавливается. Это не тотальная и не вычислимая функция. Да?

alt text

1) Верно? Потому что это композиция вычислимых функций (сложение, константа, f)

2) Верно? f определена iff f+1 определена (?). Чтобы получить программу, вычисляющую f, берем программу, вычисляющую f+1, и дописываем инструкцию "вычесть 1" если g(x) определено перед выводом результата.

3) Верно? Если f не определена, то и g не определена. Если f определена, то g(x) не определена iff f(x)=0. То есть можно модифицировать программу для f таким образом: если f(x) определено, запускаем проверку, равно ли f(x) нулю. Если да, зацикливаемся, если нет, выводим f(x)-1.

4) Неверно? Потенциальная программа для f принимала бы х, и в частности должна была бы зациклиться, если f(x) не определено. Но мы можем только проверить, определено ли f(x)-1. Если оно не определено, то f(x) всё ещё может быть определено (и равно нулю). То есть нет способа проверить, определено ли f(x)? Это верно? Если да, есть ли более формальное объяснение?

задан 22 Май 2:07

Очень плохо отвечать на такие вопросы. Надо долго вчитываться, хотя большинство утверждений -- "мусорные".

Вторую задачу обсуждать почти нечего. Пункт 4 там неверен потому, что мы не умеем распознавать свойство f(x)=0 для вычислимых функций. Остальное там очевидно.

По первой задаче: в пункте 1 годится что угодно. Самое простое f(x)=0 при x>=1 и f(0) зацикливается. В пункте 3 выдаётся не f(x), а константа. В пункте 4 нужен другой пример: функция выдаёт 0 если машина x остановилась и не выдаёт ничего, если не остановилась.

(22 Май 2:42) falcao

"В пункте 4 нужен другой пример: функция выдаёт 0 если машина x остановилась и не выдаёт ничего, если не остановилась." А разве эта функция является невычислимой? Принимается х, запускается машина х. Если она остановилась, выдается 0, а если нет то программа работает бесконечно.

(1 Окт 7:32) logic

@logic: надо было взять функцию, которая принимает значение 0 на работающей бесконечно долго машине x, и не останавливающейся, если машина останавливается. Такая функция уже не вычислима.

Здесь очень легко совершить ошибку, потому что голову всё время приходится держать в напряжении. Лично меня такие тесты изматывают. Пользы от них нет (так как нет нового знания), а вред очевиден. Скажем, если меня часами начать спрашивать таблицу умножения (чему равно 7x4), то после нескольких часов я начну говорить неправильные ответы :)

(1 Окт 19:08) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×928

задан
22 Май 2:07

показан
98 раз

обновлен
1 Окт 19:08

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru