Есть два определения универсальной функции:

  • Это частичная вычислимая функция $%U:N\times N\to N$% такая что для всех частичных вычислимых функций $%f:N\to N$% существует программа $%p\in N$% такая что для всех $%x\in N$% верно $%f(x)=U(p,x)$%.

  • Это частичная вычислимая функция $%U:N\times N\to N$% такая что для всех $%x,y\in N$%, верно $%U(x,y)=\phi_x(y)$% если $%\phi_x(y)$% определена и $%U(x,y)$% неопределена если $%\phi_x(y)$% неопределена. (Через $%\phi_x$% обозначена функция, определяемая программой $%x$%)

Во-первых, следует ли из первого определения, что p - это одна из программ, вычисляющих f?(То есть верно ли, что $%f(x)=\phi_p(x))$%?) Об этом же ничего не сказано?

Во-вторых, (даже если принять положительный ответ на первый вопрос) почему эти определения эквивалентны? В первом порядок кванторов такой $%\forall \exists \forall$%, а во втором такой: $%\forall\forall$%. Почему это "одно и то же"?

задан 23 Май 1:08

изменен 23 Май 1:09

@logic: нужно идти от смысла. Начинать надо с мысли о том, чего мы хотим от U. Тогда будет понятнее.

В первом случае, строго говоря, p -- это не программа, а её номер. Тогда говорится, что среди функций вида U(p,x) все (частично) вычислимые будут получаться.

Во втором случае уже принято, что всякая функция вычисляется некоторой программой, и программы занумерованы числами. Тогда требуем, чтобы U(p,x) давала p-ю программу вычисления (с совпадением областей определения и значений на ней).

Плохо то, что обозначения в разных определениях не согласованы -- буквы приходится менять по ходу дела.

(23 Май 2:40) falcao

То есть определения не эквивалентны?

И я не понял, как из такого описания вывести ответ на первый вопрос.

(23 Май 2:55) logic

Определения в содержательном смысле эквивалентны. Они разным языком описывают одно и то же. Это значит, что классы вычислимых функций там и там совпадают.

На содержательном уровне p есть номер программы, которая вычисляет f(x). Тут надо иметь в виду, что во втором определении уже позаботились о нумерации программ -- без этого не имеет смысла определение ф_p. Ведь такая нумерация может быть по-разному организована.

А содержательно, "срезы" U содержат все (частичные) вычислимые функции одного аргумента, вот и всё. Оба текста про это.

(23 Май 3:08) falcao

А как из первого определения следует, что p - это номер программы, вычисляющей f? Там же не сказано, что U(p,x) - это результат применения программы с номером p к аргументу х. Там просто сказано, что f(x) равно какой-то абстрактной функции U(p,x).

(26 Май 2:50) logic

@logic: а что такое вообще программа? Она может быть написана на очень многих языках. Каков критерий, что она подходит? Он только один: это эффективная вычисляющая процедура, возвращающая на любом входе значения данной функции. Тогда её можно называть этим словом.

В первом определении U есть вычисляющая процедура. Подставим туда p в качестве первого аргумента. Получим процедуру, вычисляющую f(x). Значит, f(x) вычислима, а частный случай вычисления никто не мешает назвать "программой" (с номером p). Там суть только в том, что ВСЕ вычислимые единым алгоритмом U порождаются.

(26 Май 2:57) falcao

Но как из определения-то следует, что U - вычисляющая процедура? Если я знаю только это определение, откуда мне узнать, что U(p,-) будет вычислять соответствующую f(x)? Это становится понятным только после прочтения доказательства теоремы о существовании U, откуда следует, что U(p,-) вычисляет функцию с номером p. Но что-то не видно, чтобы это следовало из определения.

(26 Май 3:10) logic

@logic: я не понимаю причину этих вопросов. Читаем начало определения:

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

Вы видите разницу между вычислимой функцией и вычисляющей процедурой? Я -- не вижу.

Понятно, что U(p,-) вычисляет какую-то функцию f(x). Суть только в том, что "срезы" по разным p дадут ВСЕ вычислимые функции. В этом случае U можно назвать универсальной. Заметьте, что при таком подходе у функций вообще нет никаких номеров. А факт существования из определения, разумеется, не следует-- мы вводим только требование, а остальное доказывается отдельно.

(26 Май 3:23) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×928

задан
23 Май 1:08

показан
112 раз

обновлен
26 Май 3:23

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

по почте:

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

по RSS:

Ответы

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

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