2014 dxdy logo

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

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




 
 Барендрегт, опред. 2.2.7 (вычислимость и н.ф.)
Сообщение06.08.2019, 17:12 
Аватара пользователя
В книжечке Барендрегта есть такое определение: функция $\lambda$-определима, если есть такой $F$, что $F\left\lceil n_1 \right\rceil ... \left\lceil n_k \right\rceil = \left\lceil m \right\rceil$. $m$, соответственно, значение функции на $n_1,...,n_k$. А когда $F\left\lceil n_1 \right\rceil ... \left\lceil n_k \right\rceil$ не имеет нормальной формы, то на этих $n_1,...,n_k$ функция не определена.
Это, типа, связывание лямбды с рекурсивными функциями.
Вопрос, а куда девается случай, когда $F\left\lceil n_1 \right\rceil ... \left\lceil n_k \right\rceil$ имеет нормальную форму, но только она не $\left\lceil m \right\rceil$?

 
 
 
 Re: Барендрегт, опред. 2.2.7 (вычислимость и н.ф.)
Сообщение07.08.2019, 02:48 
Такой $F$ не имеет отношения к делу. Определение гласит "функция вычислима, если есть программа $F$, которая выдаёт значение функции на тех аргументах, где функция определена и зацикливается на тех, где функция не определена". Если программа $F$ на каких-то аргументах выдаёт другие значения (чем данная функция), то к вычислимости этой функции она отношения вообще не имеет.

 
 
 
 Re: Барендрегт, опред. 2.2.7 (вычислимость и н.ф.)
Сообщение07.08.2019, 05:11 
Аватара пользователя
Ясно, спасибо.

 
 
 [ Сообщений: 3 ] 


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