차이점
이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.
|
튜링완전 [2010-06-08 21:26] lifthrasiir 새로 만듦 |
튜링완전 [2011-05-30 18:25] (현재) |
||
|---|---|---|---|
| 줄 3: | 줄 3: | ||
| [[Alan Turing|Turing]] completeness. [[계산모델]]의 한 분류. 어떤 계산 모델이 [[튜링기계]]로 나타낼 수 있는 [[프로그램]]을 모두 나타낼 수 있고 그 역도 성립한다면 그 모델은 튜링 완전, 즉 튜링 기계와 동일한 능력을 가진다. | [[Alan Turing|Turing]] completeness. [[계산모델]]의 한 분류. 어떤 계산 모델이 [[튜링기계]]로 나타낼 수 있는 [[프로그램]]을 모두 나타낼 수 있고 그 역도 성립한다면 그 모델은 튜링 완전, 즉 튜링 기계와 동일한 능력을 가진다. | ||
| - | 기본적으로 우리가 사용하는 사실상 모든 [[계산]]은 튜링 완전한 모델로 표현 가능하다고 볼 수 있다. 이보다 더 넓은 범위의 개념은 [[초계산]](hypercomputation)이며 실제로 구현할 수 있으리라는 추측도 있긴 하지만 아직 현실적인 얘기는 아니다. | + | 기본적으로 우리가 사용하는 사실상 모든 [[계산]]은 튜링 완전한 모델로 표현 가능하다고 볼 수 있다. 이보다 더 넓은 범위의 개념은 [[하이퍼계산]]이라 부르며 실제로 구현할 수 있으리라는 추측도 있긴 하지만 아직 현실적인 얘기는 아니다. |
| + | ===== 튜링 완전한 모델들 ===== | ||
| + | |||
| + | * [[튜링기계]] (정의에 따라) | ||
| + | * [[타입없는람다대수]] 및 적절한 [[타입시스템]]을 가진 대부분의 [[람다대수]] 변종 ([[처치튜링명제]]에 따라) | ||
| + | * 제한 없는 [[재작성체계]] | ||
| + | * 우리가 일반적으로 사용하는 사실상 모든 일반목적 [[프로그래밍언어]]는 튜링 완전하다. 좀 더 정확하게는: | ||
| + | * 제한 없는 조건부 [[GOTO]] 문과 (필요에 따라 그 크기를 임의로 키울 수 있는) [[메모리]]를 읽고 쓸 수 있는 모델은 튜링 완전하다. | ||
| + | * GOTO 문을 제한 없는 [[while]] 문으로 바꿔도 튜링 완전하다. ("제한이 없다"는 말은 루프가 시작되기 전에 루프가 도는 횟수가 결정되거나 하면 안 된단 소리다.) | ||
| + | * 많은 [[함수형프로그래밍언어]]는 람다 대수와 동형이다. | ||
| + | * 많은 [[난해한프로그래밍언어]]는 위의 조건을 충족하지 않는데도 튜링 완전하게 설계되곤 한다. (이를테면 [[Muriel]] 같은 것) 따라서 이 동네에서는 튜링 완전하면서도 굉장히 예측 불허인 언어를 설계하는 것이 일반적이다. | ||
| + | |||
| + | 그 밖에 보통 튜링 완전하다고 예상하기 쉽지 않은 것들: | ||
| + | |||
| + | * [[Rule 110]]과 [[라이프게임]]을 포함한 각종 [[셀룰러오토마타]] | ||
| + | * [[마인크래프트]] [[레드스톤]] 회로 (...) | ||
| + | |||
| + | {{tag>전산학}} | ||
저작권자 © 1999–2012 강 성훈. 저작권을 약간 가집니다. | 풉;이 뭐냐고요?