무한비계민주의

Unbounded nondeterminism

컴퓨터 과학에서, 무한 비결정론 또는 무한 불변성은 동시성의 속성으로, 요청이 결국 서비스될 것임을 보증하면서 공유 자원에 대한 분쟁의 조정의 결과로 요청 서비스 지연의 양이 무한정 될 수 있다. 무한비계민주의는 동시성의 부조화 의미론의 발전에 중요한 이슈가 되었고, 후에 하이퍼컴퓨팅의 이론적 개념에 대한 연구의 일부가 되었다.

공정성

무한 비결정론에 대한 논의는 공정성에 대한 논의에 관여하는 경향이 있다. 기본 개념은 기계가 무한히 자주 상태로 들어간다면 그 상태에서 가능한 모든 전환을 취해야 한다는 의미에서 모든 연산 경로는 "공정"해야 한다는 것이다. 이는 요청이 서비스되는 것으로 이어지는 전환이 없는 경우에만 상태 순서가 무한정 허용되기 때문에 가능한 경우 기계가 요청을 서비스하도록 보장할 것을 요구하는 것과 같다. 마찬가지로, 모든 가능한 전환은 결국 무한 계산에서 일어나야 하지만 전환이 일어나기까지 무한한 시간이 걸릴 수 있다. 이 개념은 "공정" 동전을 플립하는 국지적 공정성과 구별되어야 하는데, 이 개념은, 비록 스텝 수가 증가하면, 이것은 거의 확실히 일어나지 않을 것이지만, 결과가 항상 한정된 수의 스텝으로 향하는 것이 가능하다고 이해된다.

끈의 합성에 있어서 공정하거나 무한하지 않은 비결정주의의 역할의 예는 윌리엄 D에 의해 제시되었다. 클링거, 1981년 논문에서. 그는 두 문자열의 "공정한 병합"을 각 문자열의 각 문자가 결국 발생해야 하는 세 번째 문자열로 정의했다. 그리고 나서 그는 두 줄의 모든 공정한 합병을 고려했다. 단일 함수로 가정하여 병합(S, T). 그리고는 병합(merge,1)합병ω(0,1ω)을 주장했는데, 여기서 ⊥은 빈 하천이다. 이제 병합(merge,1ω) = {1}이므로ω 1은ω 병합(0,1ω)의 요소, 즉 모순임에 틀림없다. 그는 다음과 같이 결론지었다.

공정한 병합은 스트림에서 운영되는 비결정론적 데이터 흐름 프로그램으로 기록될 수 없는 것으로 보인다.

무한 비결정론 구현 가능성

Edsger Dijkstra [1976년]은 무한 비결정론으로는 시스템을 구현할 수 없다고 주장했다. 이러한 이유로 토니 호아레[1978년]는 "효율적인 구현은 합리적으로 공정하도록 노력해야 한다"고 제안했다.

비영원성자동화

비결정론적 튜링 기계는 한정된 비결정론만 가지고 있다. 마찬가지로 비결정론(non-eterminism)의 유일한 근원으로서 보호되는 명령을 포함하는 순차적 프로그램도 비결정론(non-eterminism)에 한정되어 있을 뿐이다(Edsger Dijkstra [1976]). 간단히 말해서, 선택 비결정론은 제한되어 있다. Gordon Plotkin은 그의 1976년 논문에서 권력 지형에 관한 증거를 제시했다.

이제 주어진 상태에서 시작되는 비결정적 프로그램 P의 초기 실행 시퀀스 세트가 트리를 형성할 것이다. 분기점은 프로그램의 선택 포인트와 일치할 것이다. 각 선택 지점에는 항상 미세하게 많은 대안만 존재하기 때문에, 트리의 가지 계수는 항상 유한하다. 즉, 나무는 미세하다. 이제 Kőnig의 보조정리에서는 미세한 나무의 가지 하나하나가 유한하다면 나무 자체도 유한하다고 한다. 현재의 경우 이는 P의 모든 실행 순서가 종료되면 실행 순서가 상당히 많다는 것을 의미한다. 따라서 P의 출력 세트가 무한이라면, 반드시 [비단속 연산]을 포함해야 한다.

비결정성 자동화와 비결정성 자동자극 비교

윌리엄 클린저[1981년]는 플롯킨에 의해 위의 증거에 대한 다음과 같은 분석을 제공했다.

이 증거는 어떤 계산 c에 의해 특정 무한 가지의 모든 노드 x에 도달할 수 있다면, 지점의 모든 노드 x를 방문하는 계산 c가 존재한다는 전제에 따라 달라진다... 분명히 이 전제는 논리에서가 아니라 선택지점에 주어진 해석에서 따르게 된다. [배우 모델의 메시지 도착]에서 [메시지 도착]이 제한적인 지연으로 인해 도착 비결정론에 대해 이 전제는 실패한다. 무한가지에 있는 각 노드는 한도가 있는 가지에 놓여 있어야 하지만, 무한가지 자체가 한도가 있는 것은 아니다. 따라서 무한지점의 존재는 반드시 중단되지 않는 연산을 의미하지는 않는다.

무한 비계측성 및 비컴퓨터성

스파안 외 [properties]는 무한 비결정론적 프로그램이 중단 문제를 해결할 수 있다고 주장해 왔다. 이들의 알고리즘은 다음과 같이 정의된 두 부분으로 구성된다.

프로그램의 첫 번째 부분은 두 번째 부분에 자연적인 번호를 요청한다; 그것을 받은 후, 원하는 튜링 기계를 그 많은 스텝에 대해 반복하고, 기계가 아직 정지했는지 여부에 따라 수락 또는 거절한다.

프로그램의 2부는 비결정적으로 요청에 따라 자연 번호를 선택한다. 숫자는 0으로 초기화된 변수에 저장되며, 그런 다음 프로그램은 변수를 증가시킬지, 아니면 요청을 처리할지를 반복적으로 선택한다. 공정성 제약조건은 요청이 결국 서비스될 것을 요구한다. 그렇지 않으면 "변수 증가" 분기만 취해지는 무한 루프가 있기 때문이다. loop)가 있기 때문이다.

분명히 기계가 멈추면 이 알고리즘은 받아들일 수 있는 경로를 가지고 있다. 기계가 정지하지 않으면 프로그램의 두 번째 부분이 어떤 번호를 반환하든 이 알고리즘은 항상 거부된다.

무한 비계측주의를 다루기 위한 인수

Clinger와 Carl Hewitt는[citation needed] [Clinger 1981; Hewitt 1985; Hewitt and Agha 1991; Hewitt 2006b]에 구축된 무한 비계수주의의 속성과 동시 연산 모델(The Actor model)을 개발했다. 이는 위에서 본 바와 같이 Turing Machines에서 구현할 수 없는 연산을 허용한다. 그러나 이 연구자들은 동시 연산 모형이 교회, 클레인, 튜링 등에 의해 정의된 재귀 함수의[citation needed] 등급 밖에 있는 함수를 구현할 수 없다고 강조한다(동시 계산의 독립성 참조).

휴이트 [2006년]는 결정자라 불리는 계산 회로에 어느 정도의 시간이 걸리는지 결정할 수 있는 구속력이 없다고 주장함으로써 무한 비결정론 사용을 정당화했다(전자제품의 전이성 참조). 중재자는 컴퓨터 시계가 외부로부터의 입력(예: 키보드 입력, 디스크 액세스, 네트워크 입력 등)으로 비동기적으로 작동하는 상황을 처리하기 위해 컴퓨터에서 사용된다. 그래서 컴퓨터로 전송된 메시지가 수신되는 데 무한의 시간이 걸릴 수 있고 그 사이에 컴퓨터는 무한의 수의 상태를 통과할 수 있다.

그는 또 전자우편은 우편물이 배달되기 전에 서버에 무한히 저장될 수 있기 때문에 무한정 비계측주의를 가능하게 하며, 인터넷 상의 서버에 대한 데이터 링크도 마찬가지로 무한정 서비스가 중단될 수 있다고 주장했다. 이는 한없는 비결정론 논란을 불러일으켰다.

휴이트의 공정성 분석

휴이트는 공정성의 문제는 부분적으로 세계적인 관점에서 도출된다고 주장했다. 가장 오래된 연산 모델(예: 튜링 머신, 포스트 프로덕션, 람다 미적분 등)은 계산 단계를 나타내기 위해 지구 상태를 이용하는 수학에 기초한다. 각 계산 단계는 계산의 한 글로벌 상태에서 다음 글로벌 상태로 전환된다. 전지구적 상태 접근법은 유한 상태 기계에 대한 오토마타 이론과 비결정적 버전을 포함한 푸시 스택 기계에 대해 계속되었다. 이 모든 모델은 한계 비계측주의의 특성을 가지고 있다: 만약 기계가 초기 상태에서 시작할 때 항상 정지한다면, 기계가 정지할 수 있는 상태 수에 한계가 있다.

휴이트는 글로벌 스테이트 비결정론에서의 선택과 그의 배우 모델의 도착 순서 불변(연관주의) 사이에는 근본적인 차이가 있다고 주장했다. 글로벌 상태 비결정론에서는 "다음" 글로벌 상태를 위해 "선택"이 이루어진다. 도착 순서 불변 상태에서 조정은 각 도착 순서를 무한정 현지 시간으로 결정한다. 지역 중재가 진행되는 동안, 한없는 활동은 다른 곳에서 일어날 수 있다. 글로벌 상태가 없고 결과적으로 "다음" 글로벌 상태에 대해 "선택"할 수 없다.

참조

  • 칼 휴이트, 피터 비숍, 리차드 스타이거. 인공지능 IJCAI 1973을 위한 유니버설 모듈러 배우 형식주의.
  • 로빈 밀너. 프로세스: 로직 콜로키움 1973의 컴퓨터 에이전트 수학적 모델
  • 칼 휴이트 외 1974년 1월, 프로그래밍 언어의 원리에 관한 ACM 심포지엄의 배우 인덕션 및 메타 평가 컨퍼런스 기록.
  • 칼 휴이트 외 Colorque sur la Programmation의 비반복적 제어 구조 Processions of Nonrecursive Control Structures Processions, 1974년 4월.
  • 아이린 그리프. 의사소통 병행 직업의 의미론 MIT EECS 박사 학위 논문. 1975년 8월.
  • 고든 D. 플롯킨. 파워도메인 건설 SIAM 컴퓨팅 저널, 1976년 9월 5:452-487.
  • 에드거 디크스트라 프렌티스 홀 프로그래밍의 규율 1976.
  • 프로그래밍 개념에 대한 공식적인 설명에 관한 IFIP 실무회의의 Carl Hewitt와 Henry Baker 배우 및 연속 기능 진행. 1977년 8월 1일~5일.
  • 길레스 칸과 데이비드 맥퀸. 병렬 프로세스의 코루틴 및 네트워크 IFIP. 1977
  • 헨리 베이커. 실시간 계산을 위한 배우 시스템 MIT EECS 박사 논문. 1978년 1월.
  • 마이클 스미스 파워 도메인 컴퓨터 및 시스템 과학 저널. 1978.
  • 조지 밀른과 로빈 밀너. 동시 프로세스 및 해당 구문 JACM. 1979년 4월.
  • C. A. R. Hoare. 통신 순차 프로세스 CACM. 1978년 8월.
  • 니심 프랑스즈, C. A. R. 호어, 다니엘 레만, 윌렘 드 로에버. 비결정론, 동시성 및 통신의 의미론. 컴퓨터 및 시스템 과학 저널. 1979년 12월.
  • 낸시 린치와 마이클 피셔. Concurrent Computing의 Semantics에서 분산 시스템의 동작에 대해 기술한다. 스프링거-베를라크. 1979.
  • Jerald Schwartz Denotational semantics of Concurrent Computing에서 평행성의 의미론. 스프링거-베를라크. 1979.
  • 윌리엄 웨지 데이터 흐름 교착 상태에 대한 확장적 처리 동시 계산의 의미론 스프링거-베를라크. 1979.
  • 랄프-조한 백. Unbounded Noneterminism 1980의 의미론.
  • 데이비드 박. 공식 소프트웨어 규격에 관한 동계학교의 공정 병행주의 의미론에 관한 연구 스프링거-베를러그, 1980년
  • 다나 스콧 Denotational Semantics란 무엇인가? 컴퓨터 과학을 위한 MIT 연구소 특강연 시리즈. 1980년 4월 17일.
  • 윌리엄 D. 클링거, 배우 의미론 파운데이션스 1981년 6월 MIT 수학 박사 논문.
  • 윌리엄 D. Clinger, 필요에 의한 비결정론적 통화는 LISP와 기능 프로그래밍에 관한 심포지엄의 226-234페이지에 게으르지도 않고 이름도 모른다. 1982년 피츠버그, 펜실베이니아 주
  • Stephen Brookes, Tony Hoare 및 Bill Roscoe A Communication Sequential Process JACM 이론. 1984년 7월.
  • Carl Hewitt, The Challenge of Open Systems Byte 매거진. 1985년 4월. 인공지능의 기초---출처북 케임브리지 대학 출판부에서 다시 출판되었다. 1990.
  • 빌 로스코. 옥스퍼드 대학 컴퓨터 연구소의 기술 단문인 PRG-67 'CSP에 관한 두 논문'에 수록된 CSP의 무한 비결정론. 1988년 7월.
  • Carl Hewitt와 Gul Agha Guarded Horn 조항 언어: 그것들은 연역적이고 논리적인가? 5세대 컴퓨터 시스템에 관한 국제 회의, 옴샤 1988. 도쿄. 또한 MIT의 인공지능 제2권. MIT 프레스 1991.
  • A. W. 로스코: 프렌티스 홀의 동시성 이론과 실천 ISBN0-13-674409-5.
  • 에디스 스파안, 리엔 토렌블리에, 피터 반 엠드 보아스. 비결정론, 공정성 및 기본적 비유. EATCS 게시판, 1989년 37:186-193
  • 데이비드 A. 슈미트, 타이프 프로그래밍 언어의 구조 1994년 메사추세츠 캠브리지의 MIT 프레스
  • 버틀러, M. J.와 모건, C. C. 액션 시스템, 무한궤도 비결정론, 무한궤도 컴퓨팅의 형식적 측면. 1995
  • 토마스 A. 수드캄프, 언어 및 기계. 제2판. 애디슨 웨슬리, 리딩, 미사 1997
  • 루카 아케토와 앤드류 D. 고든(편집자) 대수적 과정 캘컬리: 첫 25년 이상 과정 대수학. 2005년 8월 1일~5일 이탈리아 포를의 베르티노로
  • 스티븐 브룩. 대수적 과정 캘커리에서 CSP 재처리: 첫 25년 이상. 2005년 8월.
  • A. W. 로스코: 동시성의 이론과 실천, 프렌티스 홀, ISBN 0-13-674409-5. 2005년 개정.
  • 칼 휴이트 반복된 논리 프로그래밍의 소멸과 그것이 왜 잘못되고 왜 잘못되었는지, 왜: AI 연구와 응용의 교훈으로 환생할 것인가. 기술 보고서 SS-06-08. AAAI 프레스. 2006년 3월.
  • 칼 휴이트, 헌신이 뭐야? Physical, Organization and Social CONE@AAMAS. 2006년 4월 27일.
  • 토비 오드. 하이퍼 컴퓨팅: 튜링 머신이 arxiv.org에서 계산할 수 있는 것보다 더 많은 컴퓨팅.