초복귀 알고리즘

Super-recursive algorithm

계산가능성 이론에서 초복구 알고리즘은 튜링 기계보다 더 강력한, 즉 계산이 더 많은 일반 알고리즘의 일반화다.이 용어는 마크 버긴(Mark Burgin)에 의해 소개되었는데, 그의 책 "초복귀 알고리즘"은 그들의 이론을 발전시키고 몇 가지 수학 모델을 제시한다.튜링 기계와 기존의 알고리즘의 다른 수학적 모델은 연구자들이 재귀 알고리즘과 그들의 계산의 특성을 찾을 수 있게 해준다.이와 유사한 방법으로 유도 튜링 기계와 같은 초복구 알고리즘의 수학 모델을 통해 연구자들은 초복구 알고리즘과 그 계산의 특성을 찾을 수 있다.

Burgin, as well as other researchers (including Selim Akl, Eugene Eberbach, Peter Kugel, Jan van Leeuwen, Hava Siegelmann, Peter Wegner, and Jiří Wiedermann) who studied different kinds of super-recursive algorithms and contributed to the theory of super-recursive algorithms, have argued that super-recursive algorithms can be used to disprove the C허치-튜링 논문, 그러나 이 관점은 수학계 내에서 비판받아 왔고 널리 받아들여지지 않고 있다.

정의

버긴(2005:13)은 튜링 머신에서 구현할 수 있는 알고리즘에 대해 재귀 알고리즘이라는 용어를 사용하며, 보다 일반적인 의미로 알고리즘이라는 단어를 사용한다.그 다음에 초복귀 알고리즘 클래스는 "어떤 튜링 기계로도 계산할 수 없는 기능을 계산하는 것이 가능한 알고리즘 클래스"(Burgin 2005: 107)이다.

초복구 알고리즘은 일반 계산과 일반 알고리즘의 관계와 유사한 방식으로 하이퍼컴퓨팅과 밀접한 관련이 있다.계산은 과정인 반면 알고리즘은 그러한 과정에 대한 유한한 건설적 설명이다.따라서 초복귀 알고리즘은 "재복귀 알고리즘으로는 실현할 수 없는 컴퓨터 프로세스(입출력 프로세스 포함)"를 정의한다. (Burgin 2005: 108)보다 제한된 정의는 하이퍼컴퓨팅이 슈퍼태스크를 해결하도록 요구한다(Copeland 2002; Hagar 및 Korolev 2007 참조).

초복귀 알고리즘도 초복귀 알고리즘보다 일반적인 알고리즘 체계와 관련이 있다.버긴은 (2005년: 115년) 초복구 알고리즘과 알고리즘이 아닌 알고리즘 체계를 명확히 구분할 필요가 있다고 주장한다.이러한 구분 하에서, 어떤 종류의 하이퍼컴퓨팅은 초복구 알고리즘(예: 유도 튜링 머신)에 의해 얻어지는 반면, 다른 유형의 하이퍼컴퓨팅은 알고리즘 스키마(예: 무한 시간 튜링 머신)에 의해 지시된다.이것은 초복구 알고리즘에 대한 작업이 하이퍼컴퓨팅과 어떻게 관련되는지 설명하고 그 반대의 경우도 설명한다.이 주장에 따르면 초복구 알고리즘은 하이퍼컴퓨팅 프로세스를 정의하는 한 가지 방법일 뿐이다.

예

초복구 알고리즘의 예는 다음과 같다(Burgin 2005: 132).

  • 재귀함수 제한 및 부분재귀함수 제한(E.M. Gold 1965)
  • 시행착오 술어(Hilary Putnam 1965)
  • 귀납 추론 기계(Carl Smith)
  • 유도 튜링 기계, 튜링 기계의 계산과 유사한 연산을 수행하고 제한된 수의 스텝(Mark Burgin) 후에 결과를 산출하는 유도 튜링 기계(Mark Burgin)
  • 튜링 기계의 계산과 유사한 계산을 수행하는 튜링 기계의 한계값. 그러나 최종 결과는 중간 결과의 한계값이다(Mark Burgin).
  • 시행착오 기계(Ja).힌티크카와 A.무타넨 1998)
  • 일반 튜링 기계(J. Schmidhuber)
  • 인터넷 기계(반 리우웬, J, 비더만, J.)
  • DNA를 사용하여 함수의 가치를 생산하는 진화적 컴퓨터(Darko Roglic)
  • 퍼지 연산(Jiri Wiedermann 2004)
  • 진화 튜링 머신(Eugene Eberbach 2005)

알고리즘 체계의 예는 다음과 같다.

  • 임의의 경계가 있는 튜링 머신(Alan Turing)
  • 트랜스커시브 연산자(Borodynanskii and Burgin)
  • 실제 숫자로 계산하는 기계들(L. Blum, F.Cucker, M. Shub, S. Smale 1998)
  • 실수에 기반한 신경망(Hava Siegelmann 1999)

실제적인 초복구 알고리즘의 예는 버긴의 책을 참조하십시오.

유도 튜링 기계

유도 튜링 기계는 중요한 종류의 초복구 알고리즘을 구현한다.유도 튜링 기계는 초기 상태가 주어졌을 때 잘 정의된 일련의 연속 상태를 통해 진행되어 결국 최종 결과를 제공하는 작업을 완료하기 위한 명확한 지시 목록이다.유도 튜링 기계와 일반 튜링 기계의 차이는 일반 튜링 기계는 그 결과를 얻었을 때 반드시 정지해야 하는 반면, 어떤 경우에는 유도 튜링 기계는 그 결과를 얻은 후 멈추지 않고 계속 계산을 할 수 있다.클레네는 이름 계산 절차나 알고리즘(Kleene 1952:137)에 의해 멈추지 않고 영원히 실행될 수 있는 절차를 호출했다.클렌은 또한 그러한 알고리즘이 결국 "어떤 물체"를 표시해야 한다고 요구했다(Kleene 1952:137).버긴은 유한한 스텝 수 뒤에 결과가 나타나기 때문에 귀납 튜링 기계에 의해 이러한 조건이 충족된다고 주장한다.귀납 튜링 기계는 최종 산출물이 생산될 때 정지하도록 지시될 수 없는 이유는 경우에 따라 귀납 튜링 기계가 결과를 어느 단계에서 얻었는지 알 수 없기 때문이다.

단순 귀납 튜링 기계는 슈미두버의 일반 튜링 기계, 힐라리 푸트남의 시행착오 술어, 금의 부분 재귀 기능 제한, 힌티크카·무타넨의 시행착오 기계(1998) 등 다른 연산 모델과 동등하다.보다 진보된 귀납 튜링 기계는 훨씬 더 강력하다.유도 튜링 기계의 계층 구조는 산술적 계층 구조의 임의 집합에서 멤버십을 결정할 수 있다(Burgin 2005).다른 동등한 연산 모델과 비교했을 때, 간단한 유도 튜링 기계와 일반 튜링 기계는 물리적 기계에 완전히 기반을 둔 컴퓨팅 오토마타의 직접 구조를 제공한다.이와는 대조적으로 시행착오 술어, 재귀함수 제한, 부분 재귀함수 제한은 조작에 대한 공식 규칙이 있는 기호의 통사적 시스템만 나타낸다.단순 귀납 튜링 기계와 일반 튜링 기계는 튜링 기계가 부분 재귀 기능 및 람다 미적분학과 관련이 있기 때문에 부분 재귀 기능 및 시행착오 술어를 제한하는 것과 관련이 있다.

유도 튜링 기계의 비할정 연산은 무한 시간 연산과 혼동해서는 안 된다(예:Potgieter 2006년 참조).첫째, 유도 튜링 기계의 일부 연산은 중단된다.기존의 튜링 기계의 경우와 같이, 어떤 정지 연산들은 결과를 제공하는 반면, 다른 것들은 그렇지 않다.그것이 멈추지 않더라도, 귀납 튜링 기계는 때때로 출력을 생산한다.이 출력이 변경을 멈추면, 연산 결과로 간주된다.

일반 튜링 기계와 간단한 유도 튜링 기계 사이에는 두 가지 주요한 차이점이 있다.첫 번째 구분은 단순한 귀납 튜링 기계도 기존의 튜링 기계보다 훨씬 더 많은 일을 할 수 있다는 것이다.두 번째 구분은 기존의 튜링 기계가 결과를 얻었을 때 항상 (최종 상태에 도달하여) 결정하는 반면, 간단한 유도 튜링 기계는 (일반 튜링 기계로 계산할 수 없는 것을 "컴퓨팅"할 때 등) 경우에 따라 이러한 결정을 내릴 수 없다는 것이다.

슈미두버의 일반화된 튜링 기계

기호 시퀀스는 시퀀스의 모든 기호를 점진적으로 출력하는 범용 튜링 기계에 유한하고 가능한 비할팅 프로그램이 있는 경우 한계에서 계산 가능하다.이것은 π의 디아디드 확장을 포함하지만 대부분은 유한한 프로그램으로 설명할 수 없기 때문에 여전히 대부분의 실수는 제외한다.쓰기 전용 출력 테이프가 있는 기존의 튜링 기계는 이전 출력을 편집할 수 없다. 위르겐 슈미두버에 따르면 일반화된 튜링 기계는 작업 테이프뿐만 아니라 출력 테이프도 편집할 수 있다.그는 구조적으로 서술 가능한 기호 시퀀스를 일반화된 튜링 기계에서 실행되는 유한한 비할링 프로그램을 가진 것으로 정의하며, 따라서 출력 기호는 결국 어떤 유한한 초기 시간 간격 후에 더 이상 변하지 않는다.Schmidhuber(2000, 2002년)는 이 접근방식을 사용하여 공식적으로 서술 가능하거나 건설적으로 계산 가능한 우주 또는 모든 것의 건설적 이론의 집합을 정의한다.일반화된 튜링 기계와 간단한 유도 튜링 기계는 재귀 알고리즘에 가장 가까운 두 종류의 초재귀 알고리즘이다(Schmidhuber 2000).

교회-튜링 논문과의 관계

재귀 이론의 Church-Turing 논문은 알고리즘이라는 용어의 특정한 정의에 의존한다.버긴은 재귀 이론에서 일반적으로 사용되는 것보다 더 일반적인 정의를 바탕으로 귀납 튜링 기계와 같은 초재귀 알고리즘이 교회-튜링 논문을 반증한다고 주장한다.그는 또한 초복구 알고리즘이 이론적으로 양자 알고리즘을 사용하는 것보다 훨씬 더 큰 효율성 이득을 제공할 수 있다는 것을 증명한다.

버긴의 초복귀 알고리즘 해석은 수학계의 반대에 부딪혔다.한 비평가는 논리학자 마틴 데이비스인데, 그는 버긴의 주장이 "수십 년 동안" 잘 이해되어 왔다고 주장한다.데이비스 주,

"현재 비판은 이러한 문제의 수학적인 논의에 관한 것이 아니라 현재와 미래의 물리적 시스템에 관한 오해의 소지가 있는 주장에 관한 것이다."(Davis 2006: 128)

데이비스는 산술적 계층의 2 수준을 설정하는 버긴의 주장에 대해 다음과 같이 말하며 연산 가능하다고 이의를 제기한다.

"계산 결과가 유용하기 위해서는 적어도 그것이 실제로 추구하는 결과라는 것을 인식할 수 있어야 한다는 것이 일반적으로 이해된다."(Davis 2006: 128)

참고 항목

참조

  • Blum, L, F. Cucker, M. Shub 및 S. Smale, Complexity and Real Computing, Springer Publishing 1998
  • 버긴, 마크 (2005), 슈퍼 리커버리 알고리즘, 컴퓨터 과학의 모노그래프, 스프링거. ISBN0-387-95569-0
  • Copeland, J. (2002) 하이퍼 컴퓨팅, 마인드 및 머신, v. 12, 페이지 461–502
  • Davis, Martin(2006), "The Church-Turing Statement: 합의와 반대"라고 말했다.Procedures, Computability in European 2006.컴퓨터 과학 강의 노트, 3988 페이지 125–132
  • Eberbach, E. (2005) "진화 계산 이론 제시", BioSystems 82, 1-19
  • 금, E.M. 재귀 제한J. 심브. 로그 10 (1965), 28-48.
  • Gold, E. Mark (1967), Language Identification in the Limit (PDF), vol. 10, Information and Control, pp. 447–474
  • Hagar, A., Korolev, A. (2007) "Quantum Hypercomputation - Hype 또는 Computing?"
  • 힌티크카, 자, 무타넨….Dordrecht, 페이지 174–188, 1998, "수학의 언어, 진실 및 논리"에서 계산성의 대안 개념
  • Kleene, Stephen C. (1952), Introduction to Metamathematics (First ed.), Amsterdam: North-Holland Publishing Company.
  • Peter Kugel, 2005년 11월 ACM의 Communications of the ACM, Volume 48, Value 11, 2005년 11월
  • Petrus H. Potgieter, "Zeno 기계와 하이퍼 컴퓨팅", 이론 컴퓨터 과학, 제358권, 제1권(2006년 7월) 페이지 23~33
  • 힐러리 푸트남, "Trial and Error 술어와 Mostowski 문제에 대한 해결책"제30권, 제1호(1965), 제49-57권
  • Darko Roglic, "진화가능성의 초복구 알고리즘에 기초한 보편적 진화 컴퓨터"
  • Hava Siegelmann, Neural Networks 및 Analog Computing: Turing Limit를 넘어서, Birkhauser, 1999, ISBN 0817639497
  • 튜링, A. (1939) 순서형, 프로크에 기초한 논리 체계. 론드. 수학. Soc, 제2경, v. 45: 161-228
  • 판 리우웬, J.와 비더만, J. (2000a) 튜링 장벽 파괴: 인터넷의 경우, 테크놀로지.프라하 체코 과학 아카데미 컴퓨터 과학 연구소 보고서
  • Jiji Wiedermann, 고전 퍼지 튜링 기계의 초 튜링 컴퓨팅 성능과 효율 특성, 이론 컴퓨터 과학, 제317권, 제1-3호, 2004년 6월
  • 지지 비더만과 얀 반 리우웬, "진화하는 인공 생물 시스템의 새로운 계산 잠재력", AI 커뮤니케이션, v. 15, no. 4, 2002

추가 읽기

  • Akl, S.G., 유니버설 컴퓨터의 신화를 불식시키기 위한 세 개의 백배수, 병렬 처리 문자, 16권, 2006년 9월 3권, 381쪽 – 403쪽.
  • Akl, S.G., The myth of universal computation, in: Parallel Numerics, Trobec, R., Zinterhof, P., Vajtersic, M., and Uhl, A., Eds., Part 2, Systems and Simulation, University of Salzburg, Salzburg, Austria and Jozef Stefan Institute, Ljubljana, Slovenia, 2005, pp. 211 – 236
  • Angluin, D, Smith, C. H. (1983) 귀납적 추론:이론과 방법, 계산. 조사, v. 15, 3, 페이지 237–269
  • Appsïtis, K, Arikawa, S, Freivalds, R, Hirowatari, E, Smith, C. H. (1999) 재귀적 실질 가치 함수의 귀납 추론에 대하여, 이론 컴퓨터 과학, 219(1-2): 3-17
  • 보디, M, 딘, T. 1989."시간 의존적 계획 문제 해결".기술보고서: 브라운대학교 CS-89-03
  • Burgin, M. "재귀 및 귀납 알고리즘의 알고리즘 복잡성", 이론 컴퓨터 과학, v. 317, No. 1/3, 2004, 페이지 31–60
  • 버긴(Burgin)과 클링거(Klinger)는 A.기계 학습, 이론 컴퓨터 과학의 경험, 세대 및 한계, v. 317, No. 1/3, 2004, 페이지 71–91
  • EBERbach, E, Wegner, P, "Beyond Turing Machine", EATCS Bulletin of the European Association for theory Computer Science (EATCS Bulletin, 2003년 10월 81, 279-304년)
  • S. 질베르스타인, 인텔리전트 시스템에 언제 어디서나 알고리즘을 사용하는 "AI 매거진", 17:73-83, 1996

외부 링크