하이퍼 컴퓨팅

하이퍼 계산 또는 슈퍼 튜링 계산은 튜링 계산이 불가능한 출력을 제공할 수 있는 계산 모델의 집합입니다.예를 들어, 중단 문제를 해결할 수 있는 기계는 하이퍼 컴퓨터일 것입니다. 페아노 산술의 모든 문장을 올바르게 평가할 수 있는 기계도 마찬가지일 것입니다.

Church-Turing 논문은 수학자가 간단한 알고리즘의 유한 집합을 사용하여 펜과 종이로 계산할 수 있는 "계산 가능한" 함수는 튜링 기계에 의해 계산될 수 있다고 말합니다.하이퍼컴퓨터는 튜링 기계가 할 수 없는 함수를 계산하기 때문에 교회-튜링적 의미에서 계산할 수 없습니다.

기술적으로, 무작위 튜링 기계의 출력은 계산할 수 없습니다. 그러나 대부분의 하이퍼컴퓨팅 문헌은 대신 무작위적 계산 불가능 함수가 아닌 결정론적 계산에 초점을 맞추고 있습니다.

역사

튜링 기계를 뛰어넘는 계산 모델은 앨런 튜링(^[1]Alan Turing)이 1938년 박사학위 논문 '질서에 기초한 논리 체계'에서 소개했습니다.본 논문에서는 자연에서 자연으로 단일 임의(비재귀) 함수를 계산할 수 있는 오라클을 사용할 수 있는 수학적 시스템을 조사했습니다.그는 더 강력한 시스템에서도 결정 불가능성이 여전히 존재한다는 것을 증명하기 위해 이 장치를 사용했습니다.튜링의 오라클 기계는 수학적 추상화이며 물리적으로 실현 ^[2]가능하지 않습니다.

상태공간

어떤 의미에서 대부분의 함수는 계산할 수 없습니다. 계산 가능한 함수는 ℵ 0$${\$displaystyle \aleph$ _${0}}$개 있지만, 셀 수 없는 수의 수퍼 튜링 함수가 있습니다($$ ℵ 0$${\$displaystyle$ 2$^{\aleph$ _${0$

모델들

하이퍼컴퓨터 모델은 유용하지만 실현 불가능할 수도 있는 (튜링의 원래 오라클 기계와 같이) 더 신뢰성 있게 "실현 가능한" 덜 유용한 랜덤 함수 생성기(예: 랜덤 튜링 기계와 같이)에 이르기까지 다양합니다.

계산할 수 없는 입력 또는 블랙박스 구성요소

이 섹션은 목록 형식이지만 산문으로 더 잘 읽힐 수 있습니다. 필요한 경우 이 섹션을 변환하여 도움을 줄 수 있습니다. 편집 도움말을 사용할 수 있습니다.(2023년 7월)

계산할 수 없는 또는 화려한 차이틴 상수(정지 문제의 해를 부호화하는 무한한 숫자열을 가진 숫자)에 대한 지식이 입력으로 부여된 시스템은 수많은 유용한 결정할 수 없는 문제를 해결할 수 있습니다; 계산할 수 없는 난수 생성기가 입력으로 부여된 시스템은 무작위 계산할 수 없는 함수를 생성할 수 있습니다.그러나 일반적으로 정지 문제와 같은 "확장" 계산할 수 없는 함수를 의미 있게 해결할 수 없다고 여겨집니다.다음과 같은 다양한 유형의 하이퍼컴퓨터가 무제한으로 존재합니다.

• 튜링이 1939년에 정의한 튜링의 독창적인 오라클 기계들.
• 실제 컴퓨터(일종의 이상화된 아날로그 컴퓨터)는 물리학이 일반적인 실제 변수(계산 가능한 실제 변수뿐만 아니라)를 수용한다면 하이퍼^[4] 계산을 수행할 수 있으며, 이러한 변수들은 어떤 면에서 유용한 (임의가 아닌) 계산을 위해 "이용 가능한" 것입니다.이것은 매우 기이한 물리 법칙(예를 들어 차이틴 상수와 같이 구불구불한 값을 가진 측정 가능한 물리 상수)을 필요로 할 수 있으며, 비록 표준 물리학이 그러한 임의의 정밀도 측정을 이론적으로 불가능하게 만들지만,^[5] 실제 값의 물리적 값을 임의의 정밀도로 측정할 수 있는 능력이 필요할 것입니다.
  • 마찬가지로, Chaitin의 상수가 가중치 함수에 정확히 포함된 신경망은 중단 ^[6]문제를 해결할 수 있을 것이지만 실제 계산에 기반한 다른 하이퍼 계산 모델과 동일한 물리적 어려움을 겪습니다.
• 어떤 퍼지 논리 기반의 "퍼지 튜링 기계"는 정의에 따라 실수로 정지 문제를 해결할 수 있지만, 정지 문제를 해결하는 능력이 기계의 사양에 간접적으로 가정되기 때문에 이는 ^[7][8]기계의 원래 사양에서 "버그"로 간주되는 경향이 있습니다.
  • 마찬가지로, 공정한 비결정론으로 알려진 제안된 모델은 계산할 수 없는 함수의 구술 계산을 우연히 허용할 수 있는데, 이는 일부 그러한 시스템이 정의에 의해 서브시스템이 ^[9][10]영원히 실행되게 하는 거부 입력을 식별할 수 있는 구술 능력을 가지고 있기 때문입니다.
• Dmytro Taranovsky는 오라클로 빠르게 증가하는 기능을 갖춘 튜링 기계를 중심으로 구축된 전통적으로 유한하지 않은 분석 분야의 유한 모델을 제안했습니다.이것과 더 복잡한 모델을 통해 그는 2차 산술에 대한 해석을 할 수 있었습니다.이러한 모델은 이벤트 간 간격이 ^[11]계산할 수 없을 정도로 빠른 속도로 증가하는 물리적 이벤트 생성 프로세스와 같이 계산할 수 없는 입력이 필요합니다.
  • 마찬가지로, 무한 비결정론 모델에 대한 한 비정통적인 해석은 정의상 "행위자"가 정착하는 데 필요한 시간의 길이를 근본적으로 알 수 없으며, 따라서 모델 내에서 계산할 수 없는 긴 ^[12]시간이 걸리지 않는다는 것을 증명할 수 없다고 가정합니다.

"무한 계산 단계" 모델

정확하게 작동하기 위해서, 아래 기계들에 의한 특정 계산들은 문자 그대로 무한하지만 유한한 물리적 공간과 자원을 필요로 합니다. 반면에 튜링 기계에서는 중단되는 어떤 주어진 계산도 유한한 물리적 공간과 자원만을 필요로 합니다.

무한히 많은 단계를 유한한 시간 안에 완료할 수 있는 튜링 머신, 이른바 수퍼태스크로 알려진 위업.무한한 수의 단계를 실행할 수 있는 것만으로는 충분하지 않습니다.수학적 모델 중 하나는 제노 머신(제노의 역설에서 영감을 받은)입니다.제노 머신은 (예를 들어) 1분 안에 첫 번째 계산 단계를 수행하고, ½분 안에 두 번째 단계를 수행하고, ¼분 안에 세 번째 단계는 1분 안에 수행합니다.1 + ½ + ¼ + ¼ + ...을 합하면 됩니다.(기하급수) 기계가 총 2분 동안 무한히 많은 단계를 수행하는 것을 볼 수 있습니다.Shagrir에 따르면, Zeno 기계는 물리적 역설을 도입하고 그 상태는 [0, 2]의 편측 개방 기간 외에는 논리적으로 정의되지 않으므로 ^[13]계산을 시작한 지 정확히 2분 후에 정의되지 않습니다.

시간 여행의 가능성(폐쇄 시간 곡선(CTC)의 존재)이 그 자체로 하이퍼 계산을 가능하게 하는 것은 당연해 보입니다.그러나 CTC는 무한 계산이 필요로 하는 무한한 양의 스토리지를 제공하지 않기 때문에 그렇지 않습니다.그럼에도 불구하고 상대론적 하이퍼 ^[14]계산을 위해 CTC 영역이 사용될 수 있는 시공간이 있습니다.1992년 ^[15]논문에 따르면, 말라멘트-호가스 시공간에서 작동하거나 회전하는^[16] 블랙홀 주위의 궤도에서 작동하는 컴퓨터는 블랙홀 ^[17][18]내부의 관찰자에 대해 이론적으로 비튜링 계산을 수행할 수 있다고 합니다.CTC에 대한 액세스는 일반적으로 튜링이 결정 가능하지만 계산적으로 다루기 어려운 ^[19][20]것으로 간주되는 복잡성 클래스인 PSPACE-완전 문제에 대한 신속한 해결을 허용할 수 있습니다.

양자 모형

일부 학자들은 무한한 상태 중첩을 사용하는 양자 역학 시스템이 계산할 수 ^[21]없는 함수를 계산할 수 있다고 추측합니다.일반 양자 컴퓨터가 PSPACE 축소가 가능하다는 것이 입증되었기 때문에 표준 큐비트 모델 양자 컴퓨터를 사용하면 불가능합니다(다항식 시간에서 실행되는 양자 컴퓨터는 다항식 ^[22]공간에서 실행되는 고전적 컴퓨터에 의해 시뮬레이션 될 수 있음).

"결국 올바른" 시스템

일부 물리적으로 실현 가능한 시스템은 항상 정답으로 수렴하지만, 종종 오답을 출력하여 계산할 수 없을 정도로 긴 시간 동안 오답을 고수하다가 결국 다시 돌아가서 오류를 수정합니다.

1960년대 중반, E Mark Gold와 Hilary Putnam은 귀납적 ^[23]추론의 ^[24]모델을 독립적으로 제안했습니다.이러한 모델은 일부 비재귀적인 숫자 또는 언어 집합(재귀적으로 열거할 수 있는 모든 언어 집합 포함)을 "한계 내에서 학습"할 수 있게 해줍니다. 반면 정의에 따르면 숫자 또는 언어의 재귀적 집합만 튜링 기계에 의해 식별될 수 있습니다.기계는 유한 시간 내에 학습 가능한 집합에서 정답으로 안정화되지만, 재귀적인 경우에만 정답으로 식별할 수 있습니다. 그렇지 않은 경우에는 기계를 영원히 실행하고 정답을 수정하지 않는다는 점에 유의해야 정확성이 확립됩니다.Putnam은 이 새로운 해석을 경험적 술어의 부류로 파악하고, 다음과 같이 진술합니다: "만약 우리가 가장 최근에 생성된 답이 옳다고 항상 '정관'한다면, 우리는 유한한 수의 실수를 저지를 것이지만, 결국 우리는 정답을 얻게 될 것입니다. (그러나 비록 우리가 정답(유한 수열의 끝)에 도달했더라도 말입니다.nce) 우리가 정답을 알고 있는지 확신할 수 없습니다.")^[24] L. K. Schubert의 1974년 논문 "반복된 제한 재귀와 프로그램 최소화 문제"^[25]는 제한 절차를 반복하는 것의 효과를 연구했습니다. 이것은 어떤 산술 술어도 계산할 수 있게 해줍니다.슈베르트는 "직관적으로, 반복되는 한계 식별은 계속해서 성장하는 저차 귀납 추론 기계의 공동체에 의해 집단적으로 수행되는 고차 귀납 추론으로 간주될 수 있습니다."라고 썼습니다.

기호 시퀀스는 시퀀스의 모든 기호를 점진적으로 출력하는 범용 튜링 기계에 유한하고 가능한 비할팅 프로그램이 있는 경우 제한값으로 계산할 수 있습니다.여기에는 σ와 다른 모든 계산 가능한 실수의 dyadic 확장이 포함되지만 계산 불가능한 실수는 여전히 제외됩니다.설명 크기 이론에서 전통적으로 사용되는 '모노톤 튜링 기계'는 이전 출력을 편집할 수 없습니다. 위르겐 슈미드후버가 정의한 일반화된 튜링 기계는 다음과 같이 할 수 있습니다.그는 구성적으로 설명할 수 있는 심볼 시퀀스를 일반화된 튜링 기계에서 실행되는 유한한 non-halting 프로그램으로 정의하여 모든 출력 심볼이 결국 수렴합니다. 즉, 유한한 초기 시간 간격 이후에는 더 이상 변경되지 않습니다.Kurt Gödel(1931)에 의해 처음으로 나타난 한계로 인해, 정지 프로그램에 의해 수렴 시간 자체를 예측하는 것이 불가능할 수 있으며, 그렇지 않으면 정지 문제가 해결될 수 있습니다.슈미드후버(^[26][27]Schmidhuber)는 이 접근법을 사용하여 공식적으로 기술 가능하거나 구성적으로 계산 가능한 우주 또는 모든 것의 구성 이론의 집합을 정의합니다.일반화된 튜링 기계는 스펙커 시퀀스를 평가함으로써 결국 중단 문제의 올바른 해결책으로 수렴할 수 있습니다.

역량분석

많은 하이퍼 컴퓨팅 제안은 오라클이나 어드바이스 기능을 읽을 수 있는 대안적인 방법에 해당합니다.다른 항목에서는 상위 수준의 산술 계층에 액세스할 수 있습니다.예를 들어, 슈퍼태스킹 튜링 기계는, 일반적인 가정 ${\displaystyle {하}_{}^{}}$에서,$Δ10 {\$displaystyle \$Sigma$ _${1}^{0$}} $Δ10 {\displaystyle$ \$Pi$ _${1}^{$0$\}\}$를 포함하는 진리표 차수에서 임의의 술어를 계산할 수 있습니다. 대조적으로, 제한 재귀는, 알려진, 해당 튜링 차수에서 임의의 술어 또는 함수를 계산할 수 있습니다.${\displaystyle {\mathrm{}}_{}^{}}$ ${\$ 골드는 부분 재귀를 제한하는 것이 ${\displaystyle {}_{}^{}}$하게$Δ20$ {\$displaystyle$ \$Sigma$ _${2}^{$0$$}} 술어의 계산을 가능하게 한다는 것을 보여주었습니다.

모델	계산 가능한 술어	메모들	Refs
슈퍼태스킹	${\displaystyle \operatorname {tt} \left(\Sigma _{1}^{0},\Pi _{1}^{0}\right)}$	외부 관찰자에게 의존한	[28]
제한적/제한적 오류	${\displaystyle \Delta _{2}^{0}}$		[23]
반복 제한(k회)	${\displaystyle \Delta _{k+1}^{0}}$		[25]
블럼-셔브-스몰 기계		기존의 계산 가능한 실제 함수와는 비교할 수 없는.	[29]
말라멘트-호가스 시공간	HYP	시공간 구조에 의존하는	[30]
아날로그 순환 신경망	${\displaystyle \Delta _{1}^{0}[f]}$	f는 연결 가중치를 제공하는 조언 함수이며, 크기는 런타임에 의해 제한됩니다.	[31][32]
무한 시간 튜링 기계	${\displaystyle AQI}$	산술 준유도 집합	[33]
고전 퍼지 튜링 기계	${\displaystyle \Sigma _{1}^{0}\cup \Pi _{1}^{0}}$	어떤 계산 가능한 t-norm에 대해서도	[8]
증가 함수 오라클	${\displaystyle \Delta _{1}^{1}}$	단일 시퀀스 모델의 경우 ${\displaystyle {\mathrm{}}_{}^{}}$ ${\$ _${1}^{1}}$은 r.e입니다.	[11]

비평

마틴 데이비스(Martin Davis)는 하이퍼컴퓨팅에 ^[34][35]대한 글에서 이 주제를 "신화"라고 언급하며 하이퍼컴퓨팅의 물리적 실현 가능성에 대한 반론을 제시합니다.그 이론에 대해서는 1990년대에 만들어진 새로운 분야라는 주장에 반대합니다.이 관점은 위에서도 언급한 바와 같이 계산 가능성 이론(해부성의 정도, 함수에 대한 계산 가능성, 실수 및 서수)의 역사에 의존합니다.그의 주장에서 그는 모든 하이퍼컴퓨팅은 "계산 불가능한 입력이 허용된다면 계산 불가능한 출력을 얻을 ^[36]수 있다"는 것 이상의 의미가 없다고 말합니다.

참고 항목

• 디지털 물리학
• 계산의 한계

참고문헌

추가열람

이 추가 읽기 섹션에는 위키피디아의 지침을 따르지 않을 수 있는 부적절하거나 과도한 제안이 포함되어 있을 수 있습니다.적절한 경우 동일한 관점에서 관련성이 적거나 중복되는 출판물은 삭제하고, 균형 잡힌, 주제적인, 신뢰할 수 있는, 주목할 만한 추가적인 독서 제안만 제시할 수 있도록 하십시오.적절한 텍스트를 인라인 소스로 사용하거나 별도의 참고 문헌 기사를 작성하는 것을 고려합니다.(2023년 7월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

• Aoun, Mario Antoine (2016). "Advances in Three Hypercomputation Models" (PDF). Electronic Journal of Theoretical Physics. 13 (36): 169–182.
• Burgin, M. S. (1983). "Inductive Turing Machines". Notices of the Academy of Sciences of the USSR. 270 (6): 1289–1293.
• Burgin, Mark (2005). Super-recursive algorithms. Monographs in computer science. Springer. ISBN 0-387-95569-0.
• Cockshott, P.; Michaelson, G. (2007). "Are there new Models of Computation? Reply to Wegner and Eberbach". The Computer Journal. doi:10.1093/comjnl/bxl062.
• Cooper, S. B.; Odifreddi, P. (2003). "Incomputability in Nature" (PDF). In Cooper, S. B.; Goncharov, S. S. (eds.). Computability and Models: Perspectives East and West. New York, Boston, Dordrecht, London, Moscow: Plenum Publishers. pp. 137–160. Archived from the original (PDF) on 2011-07-24. Retrieved 2011-06-16.
• Cooper, S. B. (2006). "Definability as hypercomputational effect". Applied Mathematics and Computation. 178: 72–82. CiteSeerX 10.1.1.65.4088. doi:10.1016/j.amc.2005.09.072. S2CID 1487739.
• Copeland, J. (2002). "Hypercomputation" (PDF). Minds and Machines. 12 (4): 461–502. doi:10.1023/A:1021105915386. S2CID 218585685. Archived from the original (PDF) on 2016-03-14.
• Hagar, A.; Korolev, A. (2007). "Quantum Hypercomputation—Hype or Computation?*" (PDF). Philosophy of Science. 74 (3): 347–363. doi:10.1086/521969. S2CID 9857468.
• Ord, Toby (2002). "Hypercomputation: Computing more than the Turing machine can compute: A survey article on various forms of hypercomputation". arXiv:math/0209332.
• Piccinini, Gualtiero (June 16, 2021). "Computation in Physical Systems". Stanford Encyclopedia of Philosophy. Retrieved 2023-07-31.
• Sharma, Ashish (2022). "Nature Inspired Algorithms with Randomized Hypercomputational Perspective". Information Sciences. 608: 670–695. doi:10.1016/j.ins.2022.05.020. S2CID 248881264.
• Stannett, Mike (1990). "X-machines and the halting problem: Building a super-Turing machine". Formal Aspects of Computing. 2 (1): 331–341. doi:10.1007/BF01888233. S2CID 7406983.
• Stannett, Mike (2006). "The case for hypercomputation" (PDF). Applied Mathematics and Computation. 178 (1): 8–24. doi:10.1016/j.amc.2005.09.067. Archived from the original (PDF) on 2016-03-04.
• Syropoulos, Apostolos (2008). Hypercomputation: Computing Beyond the Church–Turing Barrier. Springer. ISBN 978-0-387-30886-9.