Тотальная вычислимая функция

[WalkRigh]

Задача такая: показать существование тотальной вычислимой функции $s(x,y)$, такой что$W_{s(x,y)}=W_x \cup W_y$, для всех $x,y$
Если я правильно понимаю, то тотальная вычислимая функция это примитивно рекурсивная функция, поправьте если я ошибаюсь.
Решение должно быть примерно такое : Возьмем функцию
$f(x,y,z)=1$ , если $z\in W_x $ или $z\in W_y $
$f(x,y,z)$ не определена, в ином случае.
Далее применяя тезис Черча и вычислимость универсальной функции, говорим, что $f$ вычислима и по s-m-n теореме такая функция $s(x,y)$ существует.
У меня есть вопрос по этому доказательству. Как применять тезис Черча вроде понятно: нужно запустить две программы по $x$ и по $y$ и проверять принадлежит ли z $W_x$ или $W_y$, иначе говоря, интуитивный алгоритм мы можем придумать, значит функция МНР вычислима. А как работает универсальная функция?
И будет ли тот же самый подход к задаче работать для доказательства существования такой функции для $E_$s(x,y)$$ $=$ $E_x$\cup $E_y$

[mihaild]

WalkRigh в сообщении #1222567 писал(а):

что $W_$s(x,y)$$ $=$ $W_x$\cup $W_y$,

Поправьте формулу, пожалуйста - непонятно, что вы имели в виду (и откуда куда действует функция?).
Если там предполагалось $W_{s(x, y)} = W_x \cup W_y$ - то что такое $W_x$?

WalkRigh в сообщении #1222567 писал(а):

тотальная вычислимая функция это примитивно рекурсивная функция

Нет, бывают тотальные не примитивно рекурсивные функции.

[Anton_Peplov]

WalkRigh в сообщении #1222567 писал(а):

тотальная вычислимая функция это примитивно рекурсивная функция

Вычислимая = общерекурсивная (что шире, чем примитивно-рекурсивная, пример - функция Аккермана). Тотальная = определенная на всем $\mathbb N$.

[WalkRigh]

mihaild
$W_x$ - область определения одноместной функции вычислимой по программе с номером $x$

[mihaild]

WalkRigh в сообщении #1222567 писал(а):

А как работает универсальная функция?

Уточните вопрос. Как вообще устроена универсальная функция? Это отдельная история.
$s_{mn}$ теорема (не очень понятно, как вы ее применяете) берет уже готовую универсальную функцию $\varphi$ и строит по ней функцию $s$.

WalkRigh в сообщении #1222567 писал(а):

для $E_{s(x,y)}=E_x\cup E_y$

$E_x$ - это, видимо, область значению функции с номером $x$? Тогда да, будет (только функцию, образ которой есть объединение образов, надо будет построить).

(Оффтоп)

WalkRigh в сообщении #1222567 писал(а):

функция МНР вычислима

В смысле вычислима на машине Тьюринга? (первый раз сталкиваюсь с такими обозначениями)

[WalkRigh]

mihaild
Немного непонятно, как использовать здесь универсальную функцию, как её получить и что с ней делать.
А после этого я думал использовать $s-m-n$ теорему для построения нужной функции s.
Или все же здесь можно обойтись без неё?
Просто это единственный способ, который я знаю для построения тотальной вычислимой функции
МНР - машина с неограниченными регистрами.

[mihaild]

Универсальная вычислимая функция уже есть - раз мы говорим о нумерации.
Вам нужно применить $s_{nm}$ теорему к этой универсальной функции (правильно выбрав число фиксируемых и число свободных аргументов), а потом в полученной функции $s$ зафиксировать еще один аргумент, используя построенную функцию $f$.