2014 dxdy logo

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

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




 
 Разрешимость равенства примитивно-рекурсивных функций
Сообщение20.07.2017, 21:56 
Разрешима ли проблема равенства примитивно-рекурсивных функций?
Попытки решения:
Определение ПРФ знаю. В гугле как-то быстро ответ на сабж не гуглится.
Если $f\neq g$, и $f,g$ - ПРФ, то они всюду определены, значит достаточно найти такое $n$, что $f(n)\neq g(n)$.
В случае если $f=g$, можно свести эту проблему к проблеме $h=0$, где $h=f-g$.

А хотя вроде просто: достаточно рассмотреть какой-нибудь $f(n)=\mathrm{sg} (M(n)-\sqrt{n})$, где $M(n)$ - функция Мертенса, она явно ПРФ, а мы даже неалгоритмически до сих пор не можем на вопрос ответить...

 
 
 [ 1 сообщение ] 


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