Показать, что функции частично рекурсивны

@Argenta · Регистрация: 29.11.2017

Author24 — интернет-сервис помощи студентам

В самом задании написано : рассмотреть действие μ для получения обратных функций. А уже ниже: показать, что они частично рекурсивны. Вот мне нужно это доказать, то есть построить в конечное число шагов функцию из базисных функций, с помощью операций суперпозиции, примитивной рекурсии, μ оператора. Но они уже представлены в виде μ оператора. Что тут нужно делать?
a) d(x,y)= μz [y + z = x]
b) q(x,y)=μz [y * z = x]
c) sqrt(x) =μy [y ² = x]
d) log_ax = μy [a ^y = x]

@3D Homer · 19.11.2018, 21:17

Может быть, нужно еще показать, что функции под μ частично рекурсивны.

Я согласен, что частичная рекурсивность этих функций очевидна. На самом деле, естественные продолжения этих функций примитивно рекурсивны. Я имею в виду, например, q'(x, y), возвращающую z, если yz = x, и 0, если такого z не существует.

@Argenta 3 / 3 / 2 Регистрация: 29.11.2017 Сообщений: 126
		1
	Показать, что функции частично рекурсивны 19.11.2018, 19:49. Показов 1394. Ответов 1 Метки нет (Все метки) В самом задании написано : рассмотреть действие μ для получения обратных функций. А уже ниже: показать, что они частично рекурсивны. Вот мне нужно это доказать, то есть построить в конечное число шагов функцию из базисных функций, с помощью операций суперпозиции, примитивной рекурсии, μ оператора. Но они уже представлены в виде μ оператора. Что тут нужно делать? a) d(x,y)= μz [y + z = x] b) q(x,y)=μz [y * z = x] c) sqrt(x) =μy [y ² = x] d) log_ax = μy [a ^y = x] 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,661
	19.11.2018, 21:17	2
	Сообщение было отмечено Argenta как решение Решение Может быть, нужно еще показать, что функции под μ частично рекурсивны. Я согласен, что частичная рекурсивность этих функций очевидна. На самом деле, естественные продолжения этих функций примитивно рекурсивны. Я имею в виду, например, q'(x, y), возвращающую z, если yz = x, и 0, если такого z не существует. 1

Показать, что функции частично рекурсивны

Решение