Частично рекурсивная функция φ называется потенциально рекурсивной, если существует такая рекурсивная ф-ция f, что φ (x1, x2, …, xn) = f (x1, x2, …, xn) всякия раз, когда значение φ (x1, x2, …, xn) определено. Доказать, что функция μyT1(х, x, y) не является потенциально рекурсивной. (Указание: Если бы существовало рекурсивное продолжение f(x) функции μyT1(х, x, y), то оказалось бы, что предикат ЕyT1(х, x, y) эквивалентен рекурсивному предикату T1(х, x, f(x)). )
Учебник: Мендельсон глава 5 § 3
Комментарий к работе: опираться в основном на учебник Мендельсона (мендельсон э. введение в математическую логику. м.: , 2010 – 320 с.)
Комментарий к работе: наш преподаватель любит что то доказывать максимально непонятными словами и буквами не любит в решении задач использовать много текста