계산 이론

DALL-E 2에 의해 생성된 튜링 기계의 시각적 표현

이론적인 컴퓨터 과학과 수학에서, 계산 이론은 알고리즘을 사용하여 계산 모델에서 어떤 문제를 해결할 수 있는지, 얼마나 효율적으로 해결할 수 있는지 또는 어느 정도(예: 대략적인 해와 정확한 해)를 다루는 분야입니다.이 분야는 오토마타 이론과 형식 언어, 계산 가능성 이론과 계산 복잡성 이론의 세 가지 주요 분야로 나뉘는데, 이러한 분야들은 "컴퓨터의 기본적인 능력과 한계는 무엇인가?"^[1]라는 질문에 의해 연결된다.

계산의 엄격한 연구를 수행하기 위해, 컴퓨터 과학자들은 계산 모델이라고 불리는 컴퓨터의 수학적 추상화를 연구합니다.사용되고 있는 모델은 여러 가지가 있지만, 가장 일반적으로 검토되는 것은 튜링 ^[2]기계입니다.컴퓨터 과학자들은 튜링 기계를 연구한다. 왜냐하면 튜링 기계는 공식화하기가 간단하고, 분석되고 결과를 증명하기 위해 사용될 수 있고, 그리고 많은 사람들이 생각할 수 있는 가장 강력한 "합리적인" 계산 모델을 나타내기 때문이다(처치-튜링 ^[3]논문 참조).잠재적으로 무한한 메모리 용량이 실현 불가능한 속성인 것처럼 보일 수 있지만 튜링 기계에 의해 해결되는 결정 가능한^[4] 문제는 항상 한정된 양의 메모리만을 필요로 할 것이다.그래서 원칙적으로 튜링 기계로 해결할 수 있는 모든 문제는 한정된 양의 메모리를 가진 컴퓨터로 해결할 수 있다.

역사

계산 이론은 컴퓨터 과학 분야에서 모든 종류의 모델을 창조한 것으로 간주될 수 있다.그러므로 수학과 논리가 사용된다.지난 세기에 그것은 독립적인 학문 분야가 되었고 수학과 분리되었다.

계산 이론의 선구자들로는 라몬 룰, 알론조 처치, 쿠르트 괴델, 앨런 튜링, 스티븐 클린, 로사 페테르, 존 폰 노이만, 클로드 섀넌이 있다.

나뭇가지

오토마타 이론

문법.	언어들	오토마톤	생산규칙(제약)
타입 0	재귀적 열거 가능	튜링 기계	$\alpha \rightarrow \beta$ $\alpha \rightarrow \beta$ β ({ $displaystyle \alpha \right$ 화살표 \ $controll })$ ( $\alpha \rightarrow \beta$ 없음)
타입 1	문맥 의존형	선형 유계 비결정적 튜링 기계	$\displaystyle \alpha A\beta \오른쪽 화살표 \alpha \gamma \beta }$
타입 2	콘텍스트 프리	비결정론적 푸시다운 오토마톤	$(\displaystyle A\오른쪽 화살표\gamma)$
타입 3	규칙적인.	유한 상태 오토마톤	${\style A\오른쪽 화살표 a}$ 그리고. $(\style A\오른쪽 화살표 aB 표시)$

오토마타 이론은 추상적인 기계(또는 더 적절하게는 추상적인 '수학적인' 기계나 시스템)와 이러한 기계를 사용하여 해결할 수 있는 계산 문제를 연구하는 것입니다.이 추상적인 기계들은 오토마타라고 불립니다.오토마타는 어떤 것이 스스로 무언가를 하고 있다는 것을 의미하는 그리스어 αμαα에서 유래했다.오토마타 이론은 또한 형식 언어 이론과 ^[5]밀접하게 관련되어 있는데, 오토마타는 종종 그들이 인식할 수 있는 형식 언어의 클래스에 의해 분류되기 때문이다.오토마톤은 무한 집합일 수 있는 형식 언어의 유한한 표현일 수 있습니다.오토마타는 계산기계의 이론모델로 사용되며 계산가능성에 대한 증명에 사용됩니다.

형식 언어 이론

Chomsky 계층에서 설명하는 포함 항목 설정

언어이론은 언어를 알파벳에 대한 연산 집합으로 기술하는 수학의 한 분야이다.오토마타는 정식 언어를 생성하고 인식하는 데 사용되기 때문에 오토마타 이론과 밀접하게 관련되어 있습니다.공식 언어에는 몇 가지 클래스가 있으며, 각 클래스는 이전 언어보다 더 복잡한 언어 사양을 허용합니다.촘스키 계층 ^[6]및 각각을 인식하는 오토마타 클래스에 대응합니다.오토마타가 계산 모델로 사용되기 때문에 계산해야 하는 문제에 대해서는 형식 언어가 권장되는 사양 모드입니다.

계산가능성 이론

계산가능성 이론은 주로 컴퓨터 상에서 문제를 해결할 수 있는 정도에 대한 문제를 다룬다.정지 문제는 튜링^[7] 기계로 해결할 수 없다는 진술은 계산 가능성 이론에서 가장 중요한 결과 중 하나로, 튜링 기계를 사용하여 공식화하기가 쉽고 해결할 수 없는 구체적인 문제의 한 예이기 때문이다.계산가능성 이론의 대부분은 정지된 문제의 결과에 기초한다.

계산 가능성 이론의 또 다른 중요한 단계는 라이스의 정리였는데, 이것은 부분 함수의 모든 사소한 특성들에 대해 튜링 기계가 그 특성으로 ^[8]부분 함수를 계산하는지 여부를 결정할 수 없다는 것이다.

계산 가능성 이론은 튜링 모델에 ^[9]환원 가능한 계산 모델만을 연구하는 제약을 없애는 재귀 이론이라고 불리는 수학 논리학과 밀접하게 관련되어 있습니다.재귀 이론을 연구하는 많은 수학자들과 계산 이론가들은 그것을 계산 가능성 이론이라고 부를 것이다.

계산 복잡도 이론

복잡도 클래스 간의 관계 표현

복잡성 이론은 컴퓨터로 문제를 해결할 수 있는지 여부뿐만 아니라 문제를 얼마나 효율적으로 해결할 수 있는지도 고려합니다.시간 복잡도와 공간 복잡도의 두 가지 주요 측면이 고려됩니다. 시간 복잡도와 공간 복잡도는 각각 계산을 수행하는 데 필요한 단계 수와 계산을 수행하는 데 필요한 메모리 양입니다.

주어진 알고리즘이 얼마나 많은 시간과 공간을 필요로 하는지 분석하기 위해 컴퓨터 과학자들은 문제를 해결하는 데 필요한 시간이나 공간을 입력 문제 크기의 함수로 표현합니다.예를 들어, 긴 번호 목록에서 특정 번호를 찾는 것은 번호 목록이 커질수록 더 어려워집니다.목록에 n개의 숫자가 있다고 하면 목록이 정렬되거나 색인화되지 않은 경우 원하는 번호를 찾기 위해 모든 번호를 확인해야 할 수 있습니다.따라서 우리는 이 문제를 해결하기 위해 컴퓨터가 문제의 크기를 선형적으로 증가시키는 많은 단계를 수행해야 한다고 말합니다.

이 문제를 단순화하기 위해, 컴퓨터 과학자들은 빅 O 표기법을 채택했습니다. 빅 O 표기법은 기계 구조의 특정 측면을 고려할 필요가 없고, 오히려 문제가 커짐에 따른 점근적 행동만 고려하도록 하는 방식으로 함수를 비교할 수 있게 합니다.따라서 앞의 예에서는 이 문제를 해결하려면 O $)\displaystyle$ O $(n)$ 단계가 $O(n)$ $O(n)$ 하다고 할 수 있습니다.

아마도 모든 컴퓨터 공학에서 가장 중요한 미해결 문제는 NP로 표기된 특정한 광범위한 종류의 문제들이 효율적으로 해결될 수 있는지에 대한 질문일 것이다.이것은 복잡도 클래스 P와 NP에서 더 자세히 논의되며, P 대 NP 문제는 클레이 수학 연구소가 2000년에 발표한 7개의 밀레니엄 상 문제 중 하나이다.공식 문제 설명은 튜링상 수상자인 스티븐 쿡에 의해 주어졌습니다.

계산 모델

튜링 기계 외에도, 다른 동등한 계산 모델(교회–튜링 논문 참조)이 사용되고 있다.

람다 미적분: 계산은 초기 람다 식(또는 함수와 해당 입력을 분리하려는 경우 두 개)과 베타 감소를 한 번 적용하여 각각 이전 항에서 추론한 유한 수열의 람다 항으로 구성됩니다.
조합논리: 는 ${\$ \ $displaystyle$ \ $lambda }$ - calculus $\lambda$ 와 많은 유사점을 가지지만 중요한 차이점도 있습니다(예를 들어 고정점 콤비네이터 Y는 조합 로직에서는 정상형이지만 ${\$ \ $displaystyle$ \ $lambda$ } - calculus $\lambda$ 에는 없습니다).조합 논리는 큰 야망을 가지고 개발되었다: 역설의 본질을 이해하고, 수학의 기초를 더 경제적으로 만들고, 변수의 개념을 없앤다.
μ입자 함수: 계산은 mu-supergency 함수, 즉 정의 시퀀스, 임의의 입력 값 및 입력 및 출력과 함께 정의 시퀀스에 나타나는 일련의 재귀 함수로 구성됩니다.따라서 재귀 $f(x)$ f $)$ { $displaystyle$ f $(x)}$ 의 $f(x)$ $g(x)$ 정의 시퀀스에 $g(x)$ g( $)$ { $displaystyle$ g $(x)}$ 및 $h(x,y)$ y $)$ { $displaystyle$ h $(x,y$ )}가 $h(x,y)$ 나타나면 'g(5)=7' 또는 'h(3,2)=10' 형식의 용어가 표시될 수 있습니다.이 시퀀스의 각 엔트리는 기본 함수를 적용하거나 구성, 원시 재귀 또는 μ 재귀를 사용하여 위의 엔트리를 따라야 합니다.예를 들어 $f(x)=h(x,g(x))$ f ( $f(x)=h(x,g(x))$ ) $=$ ( $f(x)=h(x,g(x))$ , $f(x)=h(x,g(x))$ ( $f(x)=h(x,g(x))$ ) { $displaystyle$ f $(x$ )= $h(x,g(x)}$ $f(x)=h(x,g(x))$ 일 $f(x)=h(x,g(x))$ , 'f(5)=3'이 나타나려면 'g(5)=6' 및 'h(5,6)=3'와 같은 용어가 위에 표시되어야 합니다.최종 항이 입력에 적용되는 재귀 함수의 값을 제공하는 경우에만 계산이 종료됩니다.
마르코프 알고리즘: 문법과 같은 규칙을 사용하여 기호 문자열을 조작하는 문자열 재작성 시스템
등록기: 이론적으로 흥미로운 컴퓨터의 이상화입니다.몇 가지 종류가 있습니다.대부분의 경우, 각 레지스터는 자연수(무제한 크기)를 보유할 수 있으며, 명령은 간단하며(및 수가 적음), 예를 들어 감소(조건부 점프와 결합) 및 증가(및 정지)만 존재한다.(튜링 기계에서 볼 수 있는) 무한(또는 동적으로 성장하는) 외부 저장소의 부족은 그 역할을 괴델 번호 매기기 기술로 대체함으로써 이해할 수 있다: 각 레지스터가 자연수를 보유하고 있다는 사실은 복잡한 것(예를 들어 시퀀스 또는 매트릭스 등)을 적절한 거대한 자연수로 나타낼 수 있는 가능성을 가능하게 한다.표현과 해석의 모호성은 이러한 기법의 숫자 이론적인 기초에 의해 확립될 수 있다.

일반적인 계산 모델 외에도 일부 단순한 계산 모델은 특수하고 제한된 애플리케이션에 유용합니다.예를 들어 정규 표현은 사무실 생산성 소프트웨어에서 프로그래밍 언어까지 많은 컨텍스트에서 문자열 패턴을 지정합니다.수학적으로 정규식과 동등한 또 다른 형식주의인 유한 오토마타는 회로 설계 및 문제 해결에서 사용됩니다.문맥이 없는 문법은 프로그래밍 언어 구문을 지정합니다.비결정론적 푸시다운 오토마타는 문맥이 없는 문법과 동등한 또 다른 형식주의이다.원시 재귀 함수는 재귀 함수의 정의된 하위 클래스입니다.

다른 계산 모델에는 다른 작업을 수행할 수 있는 기능이 있습니다.계산 모델의 힘을 측정하는 한 가지 방법은 모델이 생성할 수 있는 형식 언어의 클래스를 연구하는 것입니다. 이러한 방법으로 촘스키 언어의 계층 구조를 얻을 수 있습니다.

레퍼런스

^ Michael Sipser (2013). Introduction to the Theory of Computation 3rd. Cengage Learning. ISBN 978-1-133-18779-0. central areas of the theory of computation: automata, computability, and complexity. (Page 1)
^ Hodges, Andrew (2012). Alan Turing: The Enigma (The Centenary ed.). Princeton University Press. ISBN 978-0-691-15564-7.
^ Rabin, Michael O. (June 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View.
^ Donald Monk (1976). Mathematical Logic. Springer-Verlag. ISBN 9780387901701.
^ Hopcroft, John E. and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. 3rd ed. Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9.
^ Chomsky hierarchy (1956). "Three models for the description of language". Information Theory, IRE Transactions on. IEEE. 2 (3): 113–124. doi:10.1109/TIT.1956.1056813.
^ Alan Turing (1937). "On computable numbers, with an application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. IEEE. 2 (42): 230–265. doi:10.1112/plms/s2-42.1.230. S2CID 73712. Retrieved 6 January 2015.
^ Henry Gordon Rice (1953). "Classes of Recursively Enumerable Sets and Their Decision Problems". Transactions of the American Mathematical Society. American Mathematical Society. 74 (2): 358–366. doi:10.2307/1990888. JSTOR 1990888.
^ Martin Davis (2004). The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed). Dover Publications. ISBN 978-0486432281.

추가 정보

컴퓨터 과학자를 위한 교과서

(이 영역에는 많은 교과서가 있습니다.이 목록은 필연적으로 불완전합니다.)

홉크로프트, 존 E ., 제프리 D. Ulman (2006년).오토마타 이론, 언어 및 계산 소개 애디슨-웨슬리입니다ISBN 978-0-321-45536-9 필드의 표준 레퍼런스 중 하나.
Linz P (2007). An introduction to formal language and automata. Narosa Publishing. ISBN 9788173197819.
Michael Sipser (2013). Introduction to the Theory of Computation (3rd ed.). Cengage Learning. ISBN 978-1-133-18779-0.
Eitan Gurari (1989). An Introduction to the Theory of Computation. Computer Science Press. ISBN 0-7167-8182-4. Archived from the original on 2007-01-07.
Hein, James L. (1996) 계산 이론.서드베리, 매사추세츠주: 존스 & 바틀렛.ISBN 978-0-86720-497-1 컴퓨터 공학부 2학년 학생에게 적합한 온화한 현장 소개.
테일러, R. 그레고리(1998).계산 및 형식 언어 모델.뉴욕: 옥스포드 대학 출판부.ISBN 978-0-19-510983-2 고급 학부생 또는 초급 대학원생에게 적합한 보기 드문 교재입니다.
루이스, F.D. (2007)이론 컴퓨터 과학의 기본 공식 언어, 오토마타 및 문법에 관한 주제를 다루는 교과서입니다.결과에 대한 증거를 제공하기보다는 결과와 그 적용에 대한 개요를 제시하는 데 중점을 두고 있는 것으로 보입니다.
마틴 데이비스, 론 시갈, 일레인 JWeyuker, Computability, Complexity, and Languages: 이론 컴퓨터 공학의 기초, 제2판, Academic Press, 1994, ISBN 0-12-206382-1.프로그램 의미론 및 정량화 이론을 포함한 대부분의 다른 입문서보다 광범위한 주제를 다룹니다.대학원생을 대상으로 하고 있습니다.

(와이어) 수학적 관점에서 계산가능성 이론에 관한 서적

하틀리 로저스 주니어(1987년).재귀함수와 유효계산성의 이론, MIT 출판.ISBN 0-262-68052-1
를 클릭합니다S. Barry Cooper (2004). Computability Theory. Chapman and Hall/CRC. ISBN 1-58488-237-9..
Carl H. Smith, 계산 이론에 대한 재귀적 소개, Springer, 1994, ISBN 0-387-94332-3.컴퓨터 공학 대학원생에게 적합한 짧은 교과서입니다.

역사적 관점

를 클릭합니다Richard L. Epstein and Walter A. Carnielli (2000). Computability: Computable Functions, Logic, and the Foundations of Mathematics, with Computability: A Timeline (2nd ed.). Wadsworth/Thomson Learning. ISBN 0-534-54644-7..

외부 링크

MIT의 계산 이론
하버드 계산 이론
계산 가능성 논리 - 대화형 계산 이론입니다.이 주제에 대한 주요 웹 소스입니다.

[Sipser-3rd-1] Michael Sipser (2013). Introduction to the Theory of Computation 3rd. Cengage Learning. ISBN 978-1-133-18779-0. central areas of the theory of computation: automata, computability, and complexity. (Page 1)

[Hodges-2012-2] Hodges, Andrew (2012). Alan Turing: The Enigma (The Centenary ed.). Princeton University Press. ISBN 978-0-691-15564-7.

[3] Rabin, Michael O. (June 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View.

[Monk1976-4] Donald Monk (1976). Mathematical Logic. Springer-Verlag. ISBN 9780387901701.

[hopcroft-ullman-5] Hopcroft, John E. and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. 3rd ed. Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9.

[6] Chomsky hierarchy (1956). "Three models for the description of language". Information Theory, IRE Transactions on. IEEE. 2 (3): 113–124. doi:10.1109/TIT.1956.1056813.

[7] Alan Turing (1937). "On computable numbers, with an application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. IEEE. 2 (42): 230–265. doi:10.1112/plms/s2-42.1.230. S2CID 73712. Retrieved 6 January 2015.

[8] Henry Gordon Rice (1953). "Classes of Recursively Enumerable Sets and Their Decision Problems". Transactions of the American Mathematical Society. American Mathematical Society. 74 (2): 358–366. doi:10.2307/1990888. JSTOR 1990888.

[davis-9] Martin Davis (2004). The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed). Dover Publications. ISBN 978-0486432281.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

v t 수학
역사 타임라인 개요 리스트 용어집
기초	범주론 정보 이론 수리논리 수학 철학 집합론 유형 이론
대수학	추상적인 가환성 초등 군론 선형 멀티라인 유니버설 호몰로지
분석.	미적분학. 실제 분석 복잡한 분석 초복잡한 분석 미분 방정식 기능 분석 고조파 분석 측정 이론
디스크리트	조합 그래프 이론 순서론
기하학.	대수적 분석 산술 차동 디스크리트 유클리드 유한
수론	산술 대수적 수론 해석수 이론 디오판토스 기하학
토폴로지	일반 대수적 차동 기하학 호모토피 이론
응용의	공학 수학 수리생물학 수리 화학 수리 경제학 수리금융 수리 물리학 수리심리학 수리사회학 수리통계학 확률 통계 정보 시스템 사이언스 제어 이론 게임 이론 운용 조사
계산	컴퓨터 공학 계산 이론 계산 복잡도 이론 수치 분석 최적화 컴퓨터 대수학
관련 토픽	비공식 수학 레크리에이션 수학 수학과 미술 수학 교육
수학 포털 카테고리 공통 위키프로젝트

v t 컴퓨터 공학
주의: 이 템플릿은 대략 2012 ACM Computing Classification System에 준거하고 있습니다.
하드웨어	프린트 기판 주변기기 집적회로 대규모 통합 시스템온칩(SoC) 소비전력(친환경 컴퓨팅) 전자 설계 자동화 하드웨어 액셀러레이션
컴퓨터 시스템 구성	컴퓨터 아키텍처 임베디드 시스템 실시간 컴퓨팅 신뢰성
네트워크	네트워크 아키텍처 네트워크 프로토콜 네트워크 컴포넌트 네트워크 스케줄러 네트워크 퍼포먼스 평가 네트워크 서비스
소프트웨어 구성	통역사 미들웨어 가상 머신 운영 체제 소프트웨어 품질
소프트웨어 표기법 및 도구	프로그래밍 패러다임 프로그래밍 언어 컴파일러 도메인 고유의 언어 모델링 언어 소프트웨어 프레임워크 통합 개발 환경 소프트웨어 구성 관리 소프트웨어 라이브러리 소프트웨어 저장소
소프트웨어 개발	제어 변수 소프트웨어 개발 프로세스 요건 분석 소프트웨어 설계 소프트웨어 구축 소프트웨어 도입 소프트웨어 엔지니어링 소프트웨어 유지보수 프로그래밍팀 오픈 소스 모델
계산 이론	계산 모형 격식어 오토마타 이론 계산가능성 이론 계산 복잡도 이론 논리 의미론
알고리즘	알고리즘 설계 알고리즘 분석 알고리즘 효율 랜덤화 알고리즘 계산기하학
컴퓨팅의 수학	이산 수학 확률 통계 정보 수학 소프트웨어 정보 이론 수학적 해석 수치 분석 이론 컴퓨터 공학
정보 시스템	데이터베이스 관리 시스템 정보 스토리지 시스템 엔터프라이즈 정보 시스템 소셜 정보 시스템 지리정보시스템 의사결정지원시스템 공정관리시스템 멀티미디어 정보 시스템 데이터 마이닝 디지털 라이브러리 컴퓨팅 플랫폼 디지털 마케팅 월드 와이드 웹 정보 검색
보안.	암호화 형식적인 방법 보안 서비스 침입 탐지 시스템 하드웨어 보안 네트워크 보안 정보 보안 응용 프로그램 보안
인간과 컴퓨터의 상호 작용	상호작용 설계 소셜 컴퓨팅 유비쿼터스 컴퓨팅 시각화 접근성
동시성	동시 컴퓨팅 병렬 컴퓨팅 분산 컴퓨팅 멀티스레딩 멀티프로세서
인공지능	자연어 처리 지식 표현 및 추론 컴퓨터 비전 계획 및 스케줄링 자동화 검색 방법론 제어방법 인공지능의 철학 분산형 인공지능
기계 학습	지도 학습 비지도 학습 강화 학습 멀티태스킹 학습 교차 검증
그래픽스	애니매이션 렌더링 이미지 조작 그래픽스 처리 장치 혼합현실 가상현실 이미지 압축 솔리드 모델링
응용 컴퓨팅	전자상거래 엔터프라이즈 소프트웨어 계산 수학 계산물리학 계산화학 계산생물학 계산사회과학 계산공학 컴퓨터 헬스케어 디지털 아트 전자 출판 사이버 전쟁 전자투표 비디오 게임 워드프로세서 운용 조사 교육용 테크놀로지 문서 관리
카테고리 개요 위키프로젝트 공통

Search