Разрешима ли проблема равенства примитивно-рекурсивных функций?
Попытки решения:
Определение ПРФ знаю. В гугле как-то быстро ответ на сабж не гуглится.
Если

, и

- ПРФ, то они всюду определены, значит достаточно найти такое

, что

.
В случае если

, можно свести эту проблему к проблеме

, где

.
А хотя вроде просто: достаточно рассмотреть какой-нибудь

, где

- функция Мертенса, она явно ПРФ, а мы даже неалгоритмически до сих пор не можем на вопрос ответить...