Помогите, пожалуйста, доказать, что если f(x) - всюду определенная вычислимая функция, то для любого a из множества натуральных чисел множество {x: f(x)=a} - вычислимо?

задан 27 Июн '17 0:50

Это самоочевидное утверждение. Разрешимость множества означает существование алгоритма проверки чисел на предмет принадлежности их этому множеству. Нам дано какое-то x; как проверить свойство? Вычисляем f(x), что всегда можно сделать по условию (то есть вызываем f как "подпрограмму". После этого сравниваем результат с числом a. Тогда if f(x)=a then YES else NO :)

(27 Июн '17 4:47) falcao

@falcao: а если изменить условия так. Если f(x) - частично вычислимая функция, то для любого a из множества натуральных чисел множество {x: f(x) определена и f(x)=а} - вычислимо перечислимо?

(27 Июн '17 10:50) 12345Ann

@12345Ann: это тоже верно, но чуть-чуть по-другому доказывается. Берём вычислимую нумерацию всех пар вида (x,n). Далее перебираем их последовательно, и при работе с парой (x,n) прогоняем вычисление функции f(x) на n шагов (например, на машине Тьюринга). Если за это время получился результат f(x)=a, то число x печатаем.

(27 Июн '17 15:19) falcao

@falcao: поняла, спасибо.

(28 Июн '17 0:52) 12345Ann
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×890
×154

задан
27 Июн '17 0:50

показан
368 раз

обновлен
28 Июн '17 0:52

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

по почте:

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

по RSS:

Ответы

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

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