also-gpt2 한테 물어본 불완전성 정리 관련 질문 - 특이점이 온다 마이너 갤러리

특이점이 온다 갤러리
마이너

기술적 특이점에 대해 의논하고 그와 관련된 과학 기술 정보와 소식을 공유하는 갤러리입니다. *갤러리 이름은 동명의 레이 커즈와일의 저서 <특이점이 온다 (The singularity is near)>를 의미합니다.

매니저

특갤용(118wshxhtx5h)

부매니저

ㅇㅇ(hamaster) 부패하는유전자!!!(sansss20…) 은바다(nmra3fmz…)

개설일

2019-08-01

[일반] also-gpt2 한테 물어본 불완전성 정리 관련 질문

ㅇㅇ(116.127) 2024.05.08 07:33:49

조회 178 추천 0 댓글 0

의 답변

정지 문제를 활용한 불완전성 정리의 증명과 괴델의 원래 증명 사이의 본질적인 유사점을 추론하는 것은 흥미로운 작업입니다. 이 둘의 개념적 동형성을 이해하기 위해 각 증명의 핵심적인 단계를 비교해 보고, 공통된 아이디어를 찾아보겠습니다.

### 1. 괴델의 원래 증명 방식

**괴델의 제1 불완전성 정리의 핵심 아이디어**:

- **괴델 번호**:

- 각 수학적 명제와 증명을 자연수로 인코딩하는 방법.

- 이를 통해 '자연수에 대한 문장'으로 수학적 명제와 증명을 표현할 수 있다.

- **자기 참조 (Self-Reference)**:

- 괴델은 특정 명제 \( G \)를 구성하는데, 이 명제는 "이 명제 \( G \)는 \( T \) 체계 내에서 증명할 수 없다"는 의미를 갖는다.

- 이를 위해, 메타-수준의 의미를 체계 내로 끌어오기 위해 자기 참조를 통해 형식 체계 내에서 증명 가능성을 표현한다.

- 구체적으로, '증명 가능성'을 표현하는 판별 함수 \( \mathrm{Provable}(x) \)를 정의하고, 이를 이용해 \( G \)를 구성한다.

- **불완전성 증명**:

- 만약 \( G \)가 체계 \( T \) 내에서 증명 가능하다면, \( G \)에 의해 \( G \)가 증명 가능하지 않다는 모순이 발생한다.

- 따라서 \( G \)는 \( T \) 내에서 증명 불가능하지만 참이다.

### 2. 정지 문제를 이용한 증명 방식

**정지 문제를 활용한 불완전성 증명의 핵심 아이디어**:

- **튜링 완전성**:

- 충분히 강력한 형식 체계는 모든 튜링 계산을 표현할 수 있다. 이를 통해 형식 체계 내에서 정지 문제를 표현할 수 있다.

- **정지 문제의 형식화**:

- 정지 문제의 명제를 형식 체계 내에서 표현할 수 있다.

- 예를 들어, 프로그램 \( P \)에 대해 '프로그램 \( P \)가 정지한다'는 명제를 \( \mathrm{HALT}(P) \)로 나타낸다.

- **자기 참조 (Self-Reference)**:

- 정지 문제의 불가능성 증명에서 사용하는 자기 참조와 유사하게, 자기 참조 프로그램 \( D \)를 정의한다.

- 프로그램 \( D \)는 \( D(D) \)의 결과에 따라 정지 또는 무한 루프에 빠진다.

- 이를 통해, 정지 문제의 불가능성은 형식 체계 내에서 특정 '정지 명제'의 증명 불가능성을 나타낸다.

- **불완전성 증명**:

- 충분히 강력한 형식 체계 \( T \) 내에서, 프로그램 \( P \)의 정지 여부를 표현하는 명제 \( \mathrm{HALT}(P) \)는 항상 증명 가능하지 않다.

- 따라서 \( T \) 내에서 증명 가능하지 않은 참된 명제가 존재한다.

### 3. 두 증명의 본질적 공통점

괴델의 증명과 정지 문제를 이용한 증명 사이의 본질적 공통점은 다음과 같습니다.

1. **자기 참조 (Self-Reference)**:

- **괴델 증명**: 명제 \( G \)가 "이 명제 \( G \)는 증명될 수 없다"는 자기 참조를 갖는다.

- **정지 문제 증명**: 프로그램 \( D \)가 "이 프로그램 \( D \)는 정지할 수 없다"는 자기 참조를 갖는다.

2. **증명 가능성의 표현 (Provability Statement)**:

- **괴델 증명**: 판별 함수 \( \mathrm{Provable}(x) \)를 통해 '증명 가능성'을 체계 내에서 표현한다.

- **정지 문제 증명**: 프로그램의 정지 여부를 나타내는 명제 \( \mathrm{HALT}(P) \)를 통해 '정지 가능성'을 체계 내에서 표현한다.

3. **모순의 사용**:

- **괴델 증명**: \( G \)가 체계 내에서 증명 가능하다면 모순이 발생한다.

- **정지 문제 증명**: \( D(D) \)가 정지 가능하다면 모순이 발생한다.

4. **불완전성의 귀결**:

- **괴델 증명**: 체계 내에서 증명 가능하지 않은 참된 명제가 존재한다.

- **정지 문제 증명**: 체계 내에서 증명 가능하지 않은 참된 정지 명제가 존재한다.

### 결론

괴델의 증명과 정지 문제를 이용한 증명은 모두 충분히 강력한 형식 체계에서 자기 참조를 통해 증명 가능하지 않은 참된 명제가 존재함을 보여줍니다. 두 증명 모두 형식 체계 내에서 자기 참조 구조의 명제를 만들고, 이를 통해 모순을 유도하여 불완전성을 증명합니다. 괴델의 증명이 '증명 가능성'을 이용하는 반면, 정지 문제를 이용한 증명은 '정지 가능성'을 이용하지만, 이 둘은 본질적으로 같은 아이디어를 공유하고 있습니다. 이로써 두 증명의 개념적 동형성을 발견할 수 있습니다.

이게됨

고정닉 0

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	말머리	제목	글쓴이	작성일	조회	추천
2868	설문	힘들게 성공한 만큼 절대 논란 안 만들 것 같은 스타는?	운영자	24/06/10	-	-
477165	일반	소프트웨어 개발에는 코당만 있는게 아님 [24]	ㅇㅇ(210.178)	05.18	278	0
477164	일반	구글<<이새기 ㄹㅇ 치타인거아님? [1]	ㅇㅇ(115.139)	05.18	154	0
477163	일반	학계에 올라온 초인공지능 멸망 논문 [12]	124	05.18	263	0
477162	일반	구글 발표 기획한 사람 줘패야함 [1]	ㅇㅇ(218.154)	05.18	121	0
477161	일반	20일 기대해봐도되나 [2]	ㅇㅇ(14.53)	05.18	77	0
477160	일반	제미니 곱셈잘하네 ㄷㄷ [10]	Moriae	05.18	234	1
477159	일반	ai 발전하는 거 보니 전에 character.ai에서 [6]	나그네	05.18	143	0
477158	일반	API로 탈옥하면 검열 없음?	ㅇㅇ	05.18	76	0
477157	일반	Gpt5, 잼민2울트라, 클로드4 기대된다 [2]	ㅇㅇ	05.18	120	0
477156	일반	개발자 대체 5년도 안 걸릴거 같음 [5]	ㅇㅇ(59.22)	05.18	214	0
477155	일반	씨발 네자릿수 곱셈도 못하는데 AGI? [1]	Moriae	05.18	111	0
477154	일반	잼민이 수학 돌았네 [2]	ㅇㅇ(218.154)	05.18	174	0
477153	일반	gpt 4o한테 키배에서 이기는 법 물어봄 [6]	ㅇㅇ(1.224)	05.18	159	0
477152	일반	특이점이온다2 책이 나온다고? [1]	ㅇㅇ(210.90)	05.18	72	0
477151	일반	잼민이 1.5 pro ㄹㅇ 수학 돌았는데 [10]	ㅇㅇ(125.240)	05.18	382	3
477150	일반	아직 gpt로는 실제 사진을 만화로 표현 못하내	ㅇㄴ(211.222)	05.18	111	0
477149	일반	근데 지금 로컬로 돌아가는 챗봇 있지않나? [1]	ㅇㅇ(118.33)	05.18	89	0
477148	일반	완몰가 만들어도 시간배율은 조심해야되겠네	ㅇㅇ(211.184)	05.18	72	0
477147	일반	지금 무료버전 chatgpt가 4o인거임? [1]	ㅇㅇ(223.38)	05.18	101	0
477146	일반	코파일럿 왜이럼? [2]	Moriae	05.18	149	0
477145	일반	제미니 1.5 후기 레딧에서도 거의 없네 ㅋㅋ [1]	ㅇㅇ(182.209)	05.18	222	1
477144	일반	MS 이번에 발표할 제품	ㅇㅇ(117.20)	05.18	163	0
477143	일반	돈은 안되지만 하고싶은 일을 한다던가 [1]	ㅇㅇ(1.249)	05.18	80	0
477142	일반	NSFW 포함한 검열 없어지긴 해야겠네	고양이망나니	05.18	106	0
477141	일반	아직 agi 2024 5월단은 살아있다 ㅋㅋㅋㅋㅋㅋ [5]	Samus	05.18	242	0
477140	일반	이거 진짜임? [2]	ㅇㅇ(116.36)	05.18	171	0
477139	일반	'특이점이 온다 2' 책 나오는거 알고 있니? [4]	ㅅㅌ(118.235)	05.18	150	0
477138	일반	oai내부에서 알트만 지지층이 9할이 넘었잖아 ㅋㅋㅋ [1]	ㅇㅇ(211.184)	05.18	161	2
477137	일반	만약, 기술보다 정치가 우선한다면? [1]	ㅇㅇ(211.235)	05.18	129	0
477136	일반	지금 분위기 [2]	소소하게	05.18	153	0
477135	일반	에헤이.. 잼민이 수학문제 풀이 올리려 했는데 [7]	ㅇㅇ	05.18	217	1
477134	일반	언어모델한테 단계적으로 계산시키면 곱셈 잘하는거 봤는데	Moriae	05.18	59	0
477133	일반	오지랖 떨어서 미안한데, 대책 없는 백수는 피하는 게 좋다 [8]	ㅇㅇ(210.178)	05.18	264	1
477132	일반	요즘은 그 어느때보다도 오래 살고 싶어지는 시대임	ㅇㅇ(211.184)	05.18	71	0
477131	AI창 AI창작	빙ai로 뽑은 이세계 대한민국 국군.ai [14]	ㅇㅇ	05.18	641	6
477130	일반	옛날에는 다들 뇌 커넥톰이 유일한 답인줄 알음	ㅇㅇ(211.46)	05.18	150	3
477129	일반	또또만 ㅋㅋ	Moriae	05.18	41	0
477128	일반	칙키 축쿠 착카 초코	Moriae	05.18	77	0
477126	일반	ai 스튜디오 검열 해제 어떻게 함? [1]	ㅇㅇ(125.128)	05.18	136	0
477125	일반	초필살 울트라지능을 원해	강석두 (118.235)	05.18	43	0
477124	일반	면직한 사람인데 난 너무 간절하다 [18]	ㅇㅇ	05.18	377	1
477123	일반	초지능이라는게 있을 수 있나 [7]	ㅇㅇ(220.122)	05.18	142	0
477122	일반	근데 초지능 인공이	ㅇㅇ(218.154)	05.18	52	0
477121	일반	어차피 망할거라 상관없다 << 이소리 그만해라 [6]	ㅇㅇ(104.28)	05.18	227	4
477120	일반	미.정갤 새끼들 유입됐나 [7]	ㅇㅇ	05.18	196	3
477119	일반	GPT가 AWS 같은 상시 온라인 서비스가 될 수 있으면 [2]	ㅇㅇ(58.29)	05.18	107	0
477118	일반	죽은 사람 부활은 언제쯤 가능하냐.............? [5]	ㅇㅇ(121.159)	05.18	241	0
477117	일반	'마침내... 고통스러운 삶을 끝낼 수 있겠군...' [3]	ㅇㅇ(211.184)	05.18	198	1
477116	일반	GPT-5는 wild할 것 [3]	ㅇㅇ(112.144)	05.18	348	1
477115	일반	Gtp4o구독하면 [3]	ㅇㅇ(220.121)	05.18	160	0