← logic 게시판

이 문제 재밌어 보이네요

바보(180.67) 2020-10-04 21:05 추천 0

https://math.stackexchange.com/questions/3838920/formalizing-the-number-n-leq-ell-varphin-in-pa

'PA 안에서 집합 $gif.latex? %5cleft%5c{ n %5cleq l : %5cvarphi %5cleft( n %5cright) %5cright%5c}$ 의 원소의 개수를 encoding하라'가 문제에요.

댓글 5

l-n+1 ~ l+1

익명(58.230) 2020-10-05 02:38
답글
?

바보(180.67) 2020-10-05 11:29
f(0)=0, f(l+1)=f(l)+(phi(l)이면 1 아니면 0) 주고 f(l+1) 보면 되겠네요. 인코딩은 뭐 적당히 β같은거 쓰고.

ㅁㅁ(111.239) 2020-10-05 16:00
답글
제가 잘 몰라서 여쭙는데, phi가 recursive할 필요는 없나요?

바보(180.67) 2020-10-05 17:46
답글
이미 phi가 PA서 표현이 됐다는 전제 하엔 recursive 상관없이 f(n) 정의는 끝난 거죠. 대신 계산을 못하겠죠.

ㅁㅁ(111.239) 2020-10-06 01:00