2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Тотальная вычислимая функция
Сообщение05.06.2017, 23:06 


27/12/15
23
Задача такая: показать существование тотальной вычислимой функции $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$

 Профиль  
                  
 
 Re: Тотальная вычислимая функция
Сообщение05.06.2017, 23:11 
Заслуженный участник
Аватара пользователя


16/07/14
9263
Цюрих
WalkRigh в сообщении #1222567 писал(а):
что $W_$s(x,y)$$ $=$ $W_x$\cup $W_y$,
Поправьте формулу, пожалуйста - непонятно, что вы имели в виду (и откуда куда действует функция?).
Если там предполагалось $W_{s(x, y)} = W_x \cup W_y$ - то что такое $W_x$?
WalkRigh в сообщении #1222567 писал(а):
тотальная вычислимая функция это примитивно рекурсивная функция
Нет, бывают тотальные не примитивно рекурсивные функции.

 Профиль  
                  
 
 Re: Тотальная вычислимая функция
Сообщение05.06.2017, 23:16 
Заслуженный участник
Аватара пользователя


20/08/14
8679
WalkRigh в сообщении #1222567 писал(а):
тотальная вычислимая функция это примитивно рекурсивная функция
Вычислимая = общерекурсивная (что шире, чем примитивно-рекурсивная, пример - функция Аккермана). Тотальная = определенная на всем $\mathbb N$.

 Профиль  
                  
 
 Re: Тотальная вычислимая функция
Сообщение05.06.2017, 23:20 


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

 Профиль  
                  
 
 Re: Тотальная вычислимая функция
Сообщение05.06.2017, 23:44 
Заслуженный участник
Аватара пользователя


16/07/14
9263
Цюрих
WalkRigh в сообщении #1222567 писал(а):
А как работает универсальная функция?
Уточните вопрос. Как вообще устроена универсальная функция? Это отдельная история.
$s_{mn}$ теорема (не очень понятно, как вы ее применяете) берет уже готовую универсальную функцию $\varphi$ и строит по ней функцию $s$.
WalkRigh в сообщении #1222567 писал(а):
для $E_{s(x,y)}=E_x\cup E_y$
$E_x$ - это, видимо, область значению функции с номером $x$? Тогда да, будет (только функцию, образ которой есть объединение образов, надо будет построить).

(Оффтоп)

WalkRigh в сообщении #1222567 писал(а):
функция МНР вычислима
В смысле вычислима на машине Тьюринга? (первый раз сталкиваюсь с такими обозначениями)

 Профиль  
                  
 
 Re: Тотальная вычислимая функция
Сообщение05.06.2017, 23:55 


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

 Профиль  
                  
 
 Re: Тотальная вычислимая функция
Сообщение06.06.2017, 00:27 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Утундрий


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group