수리논리학 모형 이론 증명 이론 계산 가능성 이론 집합론 범주론 이산수학 계산 이론 계산 복잡도 이론 암호학 조합론 그래프 이론 확률과 통계 확률론 통계학 확률미적분학 게임 이론 결정이론 원본 주소 " " 분류 : 계산 가능성 이론숨은 분류 : 영어 표기를 포함한 문서 둘러보기 메뉴 개인 도구 로그인하지 않음토론기여계정 만들기로그인 이름공간 문서토론 변수 보기 읽기편집역사 보기 더 보기 검색 둘러보기 대문사용자 모임요즘 화제최근 문서 보기임의 문서로도움말기부 도구 여기를 가리키는 문서가리키는 글의 최근 올리기특수 문서 목록고유 링크문서 정보위키데이터 항목이 문서 인용하기 다른 프로젝트 공용 인쇄 / 내보내기 책 만들기PDF로 다운로드인쇄용 판 다른 언어 日 本 語 / / 中 文 링크 편집 이 문서는 2019년 3월 31일 ( 일 ) 20 : 16에 마지막으로 편집되었습니다. 모든 문서는 크리에이티브 커먼즈 저작자표시 - 동일조건변경허락 3. 0에 따라 사용할 수 있으며, 추가적인 조건이 적용될 수 있습니다. 자세한 내용은 이용 약관을 참고하십시오. 미국 및 다른 국가에 등록되어 있는 Wikimedia Foundation, Inc. 소유의
계산 가능성 이론 - 위키백과, 우리 모두의 백과사전 계산 가능성 이론 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 재귀 이론은 여기로 연결됩니다. 다른 뜻에 대해서는 재귀 이론 ( 동음이의 ) 문서를 참조하십시오. 계산 가능성 이론 ( 可 能 性 理 論, 영어 : computability theory ) 또는 재귀 이론 ( 理 論, 영어 : recursion theory ) 은 수학기초론의 중요한 분야이자 컴퓨터 과학에서는 계산 이론의 한 갈래이다. 계산 가능성 이론의 기초는 가산 집합 상에서 함수의 해를 찾는 문제와 관련이 있다. 1930년대 불완전성 정리와 함께 람다 대수와 튜링 기계라는 계산 모형이 만들어지면서, 어떤 집합이 효율적으로 계산 가능한지의 문제는 실질적으로 그 집합을 효율적으로 계산해 내는 함수를 만들어 내는 것과 같은 일이 되었다. 계산 가능성 이론의 초기 성과는 이들 집합을 계산적으로 동치인 것들로 묶어 위계로 분류한 것이다. 수학적으로 유한히 정의된 함수를 계산 가능성에 따라 분류했을 때 어떤 함수의 계산 가능성 문제를 다른 함수 ( 다른 함수들 ) 의 문제로 환원할 수 있다는 것을 보임으로써, 굳이 알고리즘 자체를 증명에 끌어들이
문제를 다른 함수 ( 다른 함수들 ) 의 문제로 환원할 수 있다는 것을 보임으로써, 굳이 알고리즘 자체를 증명에 끌어들이지 않고도 계산 가능성을 증명할 수 있는 것이다. 이에 따라 대안적인 공리계를 모색하기 위한 이론적 토대가 마련되었고, 수리논리학과 증명론에서 직관주의가 입지를 공고히 했으며, 형 이론과 고차 논리, 자연 연역, 헤이팅 대수의 비약적 발전에 영향을 주었다. 계산 복잡도 이론에서는 계산 가능한 집합을 그 함수의 해를 찾는 효율적인 알고리즘에 의해 소모되는 시공간적 자원의 추세를 토대로 분류한다. 이에 따라 계산 복잡도 이론과 계산 가능성 이론 중 어느 쪽이 상위의 개념인지에 관해 다소 논쟁이 있다. 목차 1 소개 2 계산 모형 3 계산모형의 계산능력 3. 1 유한상태기계의 계산능력 3. 2 내리누름 오토마타의 계산능력 3. 3 튜링 기계의 계산능력 3. 3. 1 정지 문제 3. 3. 2 순환 언어를 넘어서 4 가상의 계산모형 4. 1 무한실행 4. 2 신탁 기계 4. 3 초월계산의 한계 5 계산가능성 이론의 역사 6 같이 보기 7 참고 문헌 소개 [ 편집 ] 컴퓨터 과학의 핵심과제는 컴퓨터로 푸는 문제들을 이해하여 연산장치의 한계를 밝히는
같은 개수가 있는 문자열만 받아들인다는 데서 모순이 된다. 따라서 이 언어는 어떤 유한 상태 기계로도 표현할 수 없으며 따라서 정규 언어가 아니다. 더 일반적인 형태로 보이기 위해서 정규 언어에 대한 펌핑 렘마를 쓰는데, 많은 언어들이 유한 상태 기계로 나타낼 수 없다는 것을 보이는 데 쓰인다. 아마 많은 사람들이 이 결과를 의아하게 생각할 것이다. 이러한 언어를 인식하는 프로그램을 컴퓨터로 작성하는 것이 매우 쉽기 때문이다. 하지만 위에서 데스크톱 PC 등 현존하는 모든 컴퓨터들이 유한 상태 기계라고 말하였다. 이것은 컴퓨터에도 엄연히 컴퓨터의 메모리 용량 같은 제한이 존재하기 때문이다. 문자열의 길이가 길어지면 문자의 개수를 세는 데 컴퓨터의 메모리 용량을 다 쓸 것이고, 결국 바닥나 오버플로우할 것이다. 아무리 많은 문자열을 인식할 수 있다고 해도 결국 인식할 수 없는 문자열이 있다. 이러한 사실들은 정규 언어가 어떻게 데스크톱 PC 등에 적용되는지를 이해할 수 있게 해 준다. 내리누름 오토마타의 계산능력 [ 편집 ] 컴퓨터 과학자들은 내리누름 오토마타로 받아들일 수 있는 언어를 문맥 자유 언어라 정의한다. 이 언어는 문맥 자유 문법으로도 표현할 수 있다. 앞에서'a'와
시간이 주어진다면 다른 계산 모형으로는 할 수 없었던 일들을 할 수 있다. 튜링 기계는 어떤 입력에 대해 영원히 멈추지 않을 수 있다. 만약 튜링 기계가 모든 입력에 대해서 멈추고 결과를 출력한다면 언어를 결정한다라고 하고 그 언어를 순환 언어라 한다. 만약 튜링 기계가 언어의 원소에 대해서는 항상 멈추고 결과를 출력하지만 언어 밖의 문자열에 대해서는 멈추지 않을 수도 있다면 그 언어를 순환 열거 언어라 한다. 튜링 기계로는 많은 일을 할 수 있다. 많은 이들이 튜링 기계 이상의 기계를 만들어내려 노력했지만 모두 실패하였다. 예를 들어 튜링 기계의 테이프 수를 늘려 2 - 3차원 무한 영역으로 확장한다 하더라고 이것은 1차원 테이프로도 구현할 수 있다. 이런 모형들은 튜링 기계보다 더 편리할 수는 있지만 더 강력하지는 않다. 사실상 튜링 기계 이상의 합리적인 계산 모형이 없다는 것을 처치 - 튜링 명제를 통해 추측할 수 있다. 튜링 기계 이상의 기능을 갖는 계산 모형들이 많이 제안되었지만, 대체로 비현실적이거나 비합리적인 것 같다 ( 아래를 참고 ). 튜링 기계는 계산 가능성의 한계에 대한 질문에 답할 수 있는 매우 강력한 도구이다
##S PaaS SaaS 소프트웨어 공학 요구 분석 소프트웨어 설계 컴퓨터 프로그래밍 정형 기법 소프트웨어 테스트 소프트웨어 개발 시스템 아키텍처 컴퓨터 아키텍처 마이크로아키텍처 운영 체제 통신 & 네트워크 컴퓨터 오디오 라우팅 네트워크 토폴로지 암호학 차세대 통신망 데이터베이스 데이터 마이닝 RDBMS SQL NoSQL 오라클 데이터베이스 인공 지능 자동추론 전산언어학 컴퓨터 비전 진화 연산 기계 학습 자연 언어 처리 로봇학 컴퓨터 그래픽 시각화 영상 처리 인간과 컴퓨터 상호 작용 컴퓨터 접근성 사용자 인터페이스 착용 컴퓨터 유비쿼터스 컴퓨팅 가상현실 계산과학 인공생명 생물정보학 인지과학 계산화학 계산론적 신경과학 계산물리학 수치해석학 기호계산 정보보호 암호학 물리 보안 애플리케이션 보안 인터넷 보안 네트워크 보안 해킹 크래킹 vdeh수학의 주요 분야수론 대수적 수론 해석적 수론 대수학 선형대수학 추상대수학 군론 환론 가환대수학 호몰로지 대수학 해석학 미적분학 실해석학 복소해석학 수치해석학 측도론 함수해석학 조화해석학 비표준 해석학 기하학 대수기하학 계산기하학 해석기하학 미분기하학 리만 기하학 위상수학 일반위상수학 대수적 위상수학 미분위상수학 매듭 이론 수학기초론 수리논리학 모형 이론 증명 이론 계산 가능성 이론 집합론 범주론 이산수학 계산 이론 계산 복잡도 이론 암호학 조합론 그래프 이론
##의 한계 [ 편집 ] 이런 기계들이 기존의 한계를 벗어난 것처럼 보여도 다시 각각의 한계를 찾을 수 있다. 이런 기계들이 튜링 기계에 대한 정지 문제를 판정할 수는 있지만 그 기계들 사이의 정지 문제는 결정 불가능하다. 예를 들어 신탁 기계는 임의의 신탁 기계가 멈추는지 아닌지를 판정할 수 없다. 계산가능성 이론의 역사 [ 편집 ] 계산가능성 이론은 일차 논리에 그 뿌리를 두고 있으며, 정지 문제 및 재귀와 관련된 많은 문제들은 불완전성 정리와 밀접하게 연관되어 있다. 다비트 힐베르트와 쿠르트 괴델은 일차논리의 기초를 쌓았다. 계산가능성 이론에 앞서 알론조 처치와 스티븐 콜 클레이니 ( 영어 : Stephen Cole Kleene ) 는 람다 셈법을 연구했다. 앨런 튜링은 현대 전산학의 아버지라 불릴 수 있을 정도로 계산 가능성 이론과 복잡도 이론의 중대한 기틀을 다졌다. 튜링의 가장 유명한 업적은 튜링 기계를 제안하여 판정 문제를 해결한 것이다. 같이 보기 [ 편집 ] 오토마타 이론 추상 기계 결정 불가능한 문제 목록 계산 복잡도 이론 계산 가능성 논리 초월계산 문제 계산 가능성 이론의 주요 논문 참고 문헌 [ 편집 ] Michael Sipser, Introduction to
입력 전체를 수락한다. 내리누름 오토마타 정해지지 않은 크기를 가진 실행 스택을 가졌다는 것을 제외하고는 위의 유한 상태 기계와 거의 같다. 상태 천이는 기존의 기능 외에, 부가적으로 스택에 기호 ( symbol ) 를 추가하거나 수 있으며 스택 위의 기호에 따라 다른 상태로 이동할 수도 있다. 튜링 기계 입력 방식이 실행 테이프 ( tape ) 라는 점을 빼고는 내리누름 오토마타와 유사하다. 실행 테이프는 헤드 ( head ) 를 이동시키는 방식으로 읽고 쓰기를 수행하며 무한히 길다. 튜링 기계는 실제 기계와는 달리 유한성을 고려하지 않지만 컴퓨터 과학에서 가장 중요한 계산 모형이다. 계산모형의 계산능력 [ 편집 ] 앞서 말한 계산 모형들이 어떤 종류의 형식 언어를 표현할 수 있는지에 따라 각 모형의 한계를 알 수 있다. 유한상태기계의 계산능력 [ 편집 ] 컴퓨터 과학자들은 유한 상태 기계 모형을 만족하는 기계가 받아들일 수 있는 언어를 정규 언어라 한다. 유한 상태 기계에서 가능한 상태는 유한개이다. 따라서 어떤 언어가 정규 언어가 아니라는 것을 보이기 위해서는 그 언어를 표현하기 위해 무한개의 상태가 필요하다는 것을 보여야 한다. 예를 들어 a 와 b 를 같
##를 적용할 수 있기 때문이다. 이 상태를 S { displaystyle S } 라 하자. 그리고 상태 S { displaystyle S } 가 처음 나온 때로부터 두 번째 등장할 때까지 읽은'a'의 개수를 d { displaystyle d } 라 하자. 즉, S { displaystyle S } 에서 d 만큼의'a'를 받아들였을 때 다시 S { displaystyle S } 상태가 된다는 것이고 따라서 기계가 ( n d 1 ) { displaystyle ( nd1 ) } 개의'a'문자를 읽든 ( n 1 ) { displaystyle ( n1 ) } 개의'a'를 읽든 최종에는 같은 상태가 된다. 이는 곧 기계가 문자열 x { displaystyle x } 를 받아들인다면, ( n d 1 ) { displaystyle ( nd1 ) } 개의'a'와 ( n 1 ) { displaystyle ( n1 ) } 개의'b'로 구성된 문자열도 받아들인다는 것이다. 이것은 M { displaystyle M } 이'a'와'b'가 같은 개수가 있는 문자열만 받아들인다는 데서 모순이 된다. 따라서 이 언어는 어떤 유한 상태 기계로도 표현할 수
##기 위해서는 그 언어를 표현하기 위해 무한개의 상태가 필요하다는 것을 보여야 한다. 예를 들어 a 와 b 를 같은 개수만큼 포함하는 문자열들의 집합을 생각해 보자. 이 언어가 유한 상태 기계 모형으로 다룰 수 없다는 것을 보이기 위해 그런 기계 M { displaystyle M } 이 있다고 하자. M { displaystyle M } 은 유한하므로 상태의 수를 n { displaystyle n } 개라 할 수 있다. 한편 앞에 a가 ( n 1 ) { displaystyle ( n1 ) } 개, 뒤에 b가 ( n 1 ) { displaystyle ( n1 ) } 개 있는 문자열 x { displaystyle x } 를 생각하자. 기계 M { displaystyle M } 이 문자열 x { displaystyle x } 를 읽어 들이면 문자열'a'를 읽을 때 적어도 한 상태를 두 번 거치게 된다.'a'가 ( n 1 ) { displaystyle ( n1 ) } 개 있고 상태가 n { displaystyle n } 개 있으므로 비둘기집 원리를 적용할 수 있기 때문이다. 이 상태를 S { displaystyle S } 라 하자. 그리고 상태 S {
계산 가능성 이론(計算可能性理論, 영어: computability theory) 또는 재귀 이론(再歸理論, 영어: recursion theory)은 수학기초론의 중요한 분야이자 컴퓨터 과학에서는 계산 이론의 한 갈래이다. 계산 가능성 이론의 기초는 가산 집합 상에서 함수의 해를 찾는 문제와 관련이 있다. 1930년대 불완전성 정리와 함께 람다 대수와 튜링 기계라는 계산 모형이 만들어지면서, 어떤 집합이 효율적으로 계산 가능한지의 문제는 실질적으로 그 집합을 효율적으로 계산해 내는 함수를 만들어 내는 것과 같은 일이 되었다. 계산 가능성 이론의 초기 성과는 이들 집합을 계산적으로 동치인 것들로 묶어 위계로 분류한 것이다. 수학적으로 유한히 정의된 함수를 계산 가능성에 따라 분류했을 때 어떤 함수의 계산 가능성 문제를 다른 함수(다른 함수들)의 문제로 환원할 수 있다는 것을 보임으로써, 굳이 알고리즘 자체를 증명에 끌어들이지 않고도 계산 가능성을 증명할 수 있는 것이다. 이에 따라 대안적인 공리계를 모색하기 위한 이론적 토대가 마련되었고, 수리논리학과 증명론에서 직관주의가 입지를 공고히 했으며, 유형 이론과 고차 논리, 자연 연역, 헤이팅 대수의 비약적 발전에 영향을 주었다. 계산 복잡도 이론에서는 계산 가능한 집합을 그 함수의 해를 찾는 효율적인 알고리즘에 의해 소모되는 시공간적 자원의 추세를 토대로 분류한다. 이에 따라 계산 복잡도 이론과 계산 가능성 이론 중 어느 쪽이 상위의 개념인지에 관해 다소 논쟁이 있다.