2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: Множество проблемы остановки
Сообщение22.04.2012, 14:56 
Доброго времени суток.
К сожалению, пришлось оторваться от изучения этого вопроса на 2 недели. На данный момент возвращаюсь к нему. Не могли бы Вы сказать, насколько правильны мои рассуждения относительно алгоритма Тарского-Куратовского?
Итак, проблема тотальности заключается в том, чтобы по некоторому номеру $x$ определить, существует ли момент времени $t$, что для любого набора $\overline{y}$, функция $\varphi_x(y)$ вычислится в этот момент. Или же, вычисляет ли программа с гёделевым номером $x$ всюду определённую функцию $\varphi_x$?
Получаем, что множество проблемы тотальности эквивалентно множеству индексов всюду определенных функций.
Таким образом, мы можем рассматривать
$A = \{x:\varphi_x$ - всюду определена$\}$ или же
$A = \{x:W_x = N\}$.
Применим алгоритм Тарского-Куратовского:
$x \in A \leftrightarrow \varphi_x$ - всюду определена $\leftrightarrow$
$\leftrightarrow \forall{y} [y  \in W_x] \leftrightarrow$
$ \leftrightarrow \forall{y} [\exists{t} T_1(x,y,t)]$.
Имеем предваренную форму с видом префикса $\forall \exists$. Множество $A$ входит в арифметическую иерархию, $A \subseteq \pi_2$.

 
 
 [ Сообщений: 16 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group