[일반] 미친 개구리 함수 질문

[익명(118.235)]

어떤 n에 대해 FF(n)의 값을 증명할 수 없다는데

현실적으로는 불가능하더라도 n개의 상태를 가진 모든 튜링 머신을 전수 조사해서 최대 쉬프트 횟수를 구하면 이론적으로는 유한한 시간 내에 값을 구할 수 있는거 아님?

아니면 증명 불가능하다는게 그냥 비구성적인 증명이 불가능하다는 것임?

[ultraproduct(ultraproduct)]

그래서 최대 시프트 값을 어떻게 구하겠다고?

[익명(118.235)]

모든 튜링머신을 만들어서 돌려보기

[ultraproduct(ultraproduct)]

무한한 메모리를 가진 걸 어떻게 만들게?

[익명(118.235)]

정지하는 튜링 머신이 유한 번의 연산을 하면서 무한한 메모리를 사용할 수가 있음?

[익명(121.166)]

튜링머신의 기본 전제가 무한메모리야

[익명(118.235)]

그건 아는데 정지하는 튜링머신이 '실제로' 사용하는 메모리는 유한할테니 실제로 돌려볼 수 있겠다 라는 말이었음

[ultraproduct(ultraproduct)]

그건 어디까지나 결과론적인 이야기고, 더군다나 밑댓에사 지적한 것처럼 멈춘다는 건 어떻게 확인하려고?

[ultraproduct(ultraproduct)]

얼마나 많은 메모리를 쓰게 될지도 모르는데 유한하게 만들면 조금은 흉내낼 수 있는, 그러나 튜링 머신은 아닌 무언가일 뿐임

[ㄱㄱ(106.102)]

메모리보다는 시간이 문제일듯한데... 손으로 시뮬레이션 하는거면 그냥 종이 많이 사용하면 되니 무한한 메모리 구현가능함

[ㄱㄱ(106.102)]

소프트웨어적으로도 네트워크 잘 이용해서 무한한 메모리 구현가능함. 물론 뭐 우주에 입자가 유한개니까 정말 무한한건 아니긴하겠지만

[ㄱㄱ(106.102)]

원글에 "현실적으로 불가능하더라도 이론적으로" 라는 말이 있었는데 이 말의 해석에 따라서 무한 메모리가 구현가능할수도 있고 불가능할수도 있겠네

[ultraproduct(ultraproduct)]

네가 구현 못한다는 거 잘 적어 줬네

[익명(121.166)]

그게 정지하는지는 어케 알거임

[익명(118.235)]

그러네

[익명(121.166)]

좀더 얘기하자면 정지문제 자체가 본질적으로 불완정성 정리랑 같음

[익명(118.235)]

"끝나는 튜링머신중" 찾는 값이니까 대충 돌리면 뭐가 끝나고 안끝나는지 알기 어렵지

[성적표보여줘(2giyoung)]

현실적으로 불가능하더라도 뭐 튜링기계보다 뛰어난 계산능력을 가진 "오라클"이 있으면 FF(n)을 구할 수 있겠지 근데 문제는 그건 인간의 계산능력을 벗어난다는게 튜링-처치 명제고...

[성적표보여줘(2giyoung)]

Hypercomputation 같은거 궁금하면 찾아보던지

[익명(211.222)]

원칙적인추론방법으로종결불가능