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

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

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

매니저

특갤용(118wshxhtx5h)

부매니저

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

개설일

2019-08-01

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

ㅇㅇ(116.127) 2024.05.08 07:33:49

조회 164 추천 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 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	말머리	제목	글쓴이	작성일	조회	추천
2861	설문	어떤 상황이 닥쳐도 지갑 절대 안 열 것 같은 스타는?	운영자	24/05/20	-	-
480610	일반	GPT5가 나온다면 채소 뭐 까지 기대함? [7]	슈퍼130클럽	05.22	197	0
480609	일반	AI PC 별거 아닌줄 알았는데 [1]	ㅇㅇ(59.26)	05.22	162	0
480607	일반	지금 gpt 서버 맛이 간 건가? [2]	ㅇㅇ(39.119)	05.22	170	0
480606	일반	gpt 서버 터졌다 이기	ㅇㅇ(180.69)	05.22	133	0
480605	일반	GPT5에 해피엔딩이 존재할 수 있냐?	ㅇㅇ(180.230)	05.22	122	0
480604	일반	Gpt가 알려주는 디시 밈 [7]	ㅇㅇ(122.203)	05.22	314	0
480603	일반	파이썬 코딩 여러개 써보니까 [2]	자애	05.22	152	0
480602	일반	특이점은 진짜 각종 사회문제 해결 치트키 같음. [2]	ㅇㅇ	05.22	150	0
480601	일반	역노화 보급되면 국가 차원에서 [1]	ㅇㅇ(211.184)	05.22	81	1
480600	일반	특이점에대한 희망을 잃어간다.. [6]	ㅇㅇ(1.236)	05.22	188	1
480598	일반	근데 환각 때문에 인간 필요하긴 함	ㅇㅇ(103.237)	05.22	45	0
480597	일반	gpt4o 음성기능 나오면... 신음소리 내는 방법 알려줌 [5]	ㅇㅇ(121.159)	05.22	272	0
480596	일반	자연어로 말하면 바로 프로그램짜서 돌려주는건 없음? [13]	ㅇㅇ(125.143)	05.22	176	0
480595	일반	지피티 서버 터진듯 [1]	고양이기체설	05.22	149	0
480593	일반	초정렬이 머임? [7]	ㅇㅇ(118.35)	05.22	162	0
480590	일반	gpt 잘되는데?방금 음성대화도 함	U갤러(182.219)	05.22	71	0
480589	일반	인류 역사 뭔가 너무 착착 맞게 진행되는거같지않냐?? [14]	ㅇㅇ	05.22	313	0
480588	일반	gpt 터졌다. 무력감이 느껴진다. [5]	a(121.169)	05.22	220	2
480587	일반	아 왜 통피 금지야	ㅇㅇ	05.22	38	0
480586	일반	지금 지피티 나만 안되냐	ㅇㅇㅇ(210.97)	05.22	55	0
480585	일반	씹덕인데 나만의 비서 있으면 얼마나 좋을까 [1]	ㅇㅇ(182.230)	05.22	106	0
480584	일반	지피티 개똑디하네 [1]	■x	05.22	176	1
480583	일반	지금 사람들이 크게 간과하고 있는거 [5]	ㅇㅇ(117.20)	05.22	294	2
480581	일반	3.5쓰고있었는데 업데이트하니 4.0이라고함. 님들도 그럼?	U갤러(182.219)	05.22	100	0
480579	일반	만약 과거로의 시간여행이 가능하거나 특이점이 와서 [3]	마가다(222.108)	05.22	115	0
480578	일반	어우 이미지 올리는거 횟수끝나버림	ㅇㅇ	05.22	36	0
480577	일반	근데 진짜 확기적으로 변할수있는 시기는 언제임? [4]	ㅇㅇ(211.48)	05.22	112	0
480576	일반	갤러리, X 돌아다니다보면 충격임 [4]	ㅇㅇ(59.26)	05.22	272	0
480575	일반	Will AI doctors be better than human doc	ㅇㅇ(1.251)	05.22	39	0
480574	정보/ 정보/뉴스	진짜 보이스 기능 존나 멀었네.. [4]	ㅇㅇ(119.77)	05.22	380	1
480572	일반	AI로 완전히 놀고 먹는 시대가 온다는건 틀렸지 [17]	시작	05.22	399	1
480571	일반	씨발 [5]	ㅇㅇ	05.22	153	0
480570	일반	Ai 스트리머 하는사람들 많아질거 같다	ㅇㅇ(121.131)	05.22	132	0
480569	일반	챗지피티한테 사진올려도됨? [3]	ㅇㅇ	05.22	152	0
480568	일반	요즘 아이돌들 유튜브에 자주 봄 [1]	dadfsfsdf(121.178)	05.22	80	0
480567	일반	방금 놀라운 사실 발견헀다 [4]	ㅇㅇ(117.20)	05.22	205	0
480566	일반	'AI로 모두 놀고 먹을 수 있음'에 화난 인간들이 많은건 신기하지않음? [11]	ㅇㅇ(180.230)	05.22	354	4
480565	일반	전시안이 이렇게 구현되는구나라는 생각을 했다. [5]	e/linear	05.22	204	2
480564	일반	프롬프트 엔지니어는 뭐였을까 [15]	ㅇㅇ(118.39)	05.22	226	0
480563	일반	실베 씨팔련 일부러 저러나 왜 ㅈ같은거만 올림? [2]	ㅇㅇ(211.179)	05.22	141	4
480560	일반	이짤 너무 절묘한듯 [5]	ㅇㅇ(211.46)	05.22	327	0
480559	일반	gpt5가 그렇게 먼 얘기는 아님	ㅇㅇ(121.183)	05.22	63	1
480558	역노화	10년안에 역노화 나오면다면 진짜 50~60년대생들은... [1]	ㅇㅇ	05.22	306	0
480557	일반	근데 GPT5 공개 멀었는거 확정아니냐?? [1]	ㅇㅇ(203.251)	05.22	153	0
480556	일반	프로그래밍은 이제 곧 아무나 할듯 [3]	ㅇㅇ(58.29)	05.22	211	0
480555	일반	프론트엔드가 가장 먼저 대체될 것 같네	agi2024	05.22	116	2
480554	일반	한국이 과도기 잘 넘길 이유 [6]	세입압	05.22	188	0
480553	일반	요즘은 선형충들이 특이점을 두려워하고있단게 느껴짐 [1]	ㅇㅇ(125.143)	05.22	107	1
480552	일반	gpt는 확실히 말로 멕이는 법을 좀 아노 ㅋㅋ [2]	ㅇㅇ	05.22	214	2
480551	일반	유럽여행 3달간 거의 매일 여자랑 잤는데 [7]	ㅇㅇ(1.251)	05.22	412	0