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
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×870

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

показан
16 раз

обновлен
22 Май 2:42

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

по почте:

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

по RSS:

Ответы

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

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