하이퍼 계산

Hypercomputation. 흔히 계산튜링 기계로 할 수 있는 일로 정의하곤 하지만 좀 무리를 해서 그보다 넓은 개념을 생각할 수 있는데 이들을 통틀어 이른다. 하이퍼 계산을 할 수 있는 기계를 하이퍼컴퓨터라 부른다.

여러 하이퍼 계산 모델들을 하나로 합칠 수 있는 뭔가 튜링 기계스러운 모델은 아직 없으며, 구현도 아직 어렵다. 몇 가지 가능성을 생각하면:

  • 무한히 많은 명령을 유한한 시간 안에 실행할 수 있는 컴퓨터. 이를테면 제노의역설을 응용해서, 매 명령이 그 이전 명령보다 절반의 시간 안에 끝나는 컴퓨터를 상정하면 이 컴퓨터는 첫 명령이 실행되는 시간의 두 배만큼의 시간 안에 모든 연산을 끝내야 한다. ("제노 컴퓨터"라 부른다)
  • 닫힌시간성곡선(CTC), 즉 출력의 일부가 타임머신을 통해 과거로 돌아가 입력으로 무한히 되먹임되는 컴퓨터는 튜링 기계보다 훨씬 빠르게 계산을 수행할 수 있다. 다만 이는 무한한 메모리를 제공하지 않으므로 한계가 있다.
  • 현재의 큐비트 기반 양자계산은 튜링 기계로 흉내낼 수 있지만, 큐비트를 사용하지 않는 다른 형태의 양자계산 모델은 그렇지 않을 수도 있다.
  • 계산 불가능한 함수의 값(이를테면 카이틴상수 같은 거)을 무한히 긴 입력으로 받을 수 있는, 이를테면 무한한 테이프를 사용하는 튜링 기계나 무한한 정밀도를 가지는 아날로그컴퓨터도 한 가능성이 된다.

도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-05-30 18:25 | 외부 편집기