Пусть $%A,B\subseteq N$% ($%N$% - натуральные числа). Будем писать $%A\le_m B $%, если существует тотальная вычислимая функция $%f:N\to N$% такая что $%x\in A\iff f(x)\in B$% для всех $%x$%.

Теперь пусть $%A+B=\{2n|n\in A\}\cup \{2n+1 | n\in B\}$%.

  • Докажите, что $%A\le_m A+B$%.
  • Докажите, что если $%A\le_m C, B\le_m C$%, то $%A+B\le_m C$%

Для первого подойдет ли функция $%f: n\mapsto 2n$%? Если $%n\in A$%, то $%f(n)=2n\in A+B$%. А если $%n\notin A$%, то $%f(n)=2n\notin A$% потому что $%2n\notin \{2n|n\in A\}$% и $%2n\notin \{2n+1| n\in B\}$%. Эта функция вычислима потому что она примитивно рекурсивная (умножение - примитивно рекурсивно).

Для второго у меня идея такая. Пусть $%f$% - свидетель того, что $%A\le_m C$% и пусть $%g$% - свидетель того, что $%B\le_m C$%. Построим $%h$% - свидетель $%A+B\le_m C$%.

Пусть $%x\in A+B$%. Если $%x\in\{2n:n\in A\}$%, то $%h(x)=f(n)$%. Если $%x\in \{2n+1:n\in B\}$%, то $%h(x)=g(n)$%. Но как определить $%h$% на остальных числах? И почему эта функция будет вычислимой?

задан 19 Окт '19 3:50

@logic: тут, по-моему, все рассуждения самые естественные. Ничего неожиданного в этих примерах нет.

Функцию h в конце надо определить как h(x)=f(x/2) при чётных x и h(x)=g((x-1)/2) при нечётных. Её вычислимость очевидна как на формальном уровне, так и на содержательном.

(19 Окт '19 3:59) falcao

Если говорить о вычислимости на содержательном уровне, то алгоритм, вычисляющий h такой? Он принимает х и проверяет для каждого натурального числа у до х, верно ли, что х=2у. Если такое у находится, то он выдает f(x/2). Если нет, то g((x-1)/2). Как тут используется вычислимость f и g?

(21 Окт '19 21:06) logic

@logic: проверка x на чётность (или нахождения частного и остатка) реализуется не обязательно таким способом. Обычно используют рекурсию. Но это не принципиально.

Вычислимость f и g используется понятно где -- ведь прежде чем значение f(x/2) или g((x-1)/2) будет выдано, его надо вычислить при помощи подпрограммы, вычисляющей f или g. В принципе, здесь сама конструкция h возможна для любых функций, но нас интересует случай, когда она вычислима.

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

Ваш ответ

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

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

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

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

отмечен:

×32

задан
19 Окт '19 3:50

показан
234 раза

обновлен
21 Окт '19 22:03

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

по почте:

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

по RSS:

Ответы

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

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