알고리즘 특성화

알고리즘 특성화는 단어 알고리즘을 공식화하려는 시도다. 알고리즘에는 일반적으로 허용되는 공식 정의가 없다. 연구자들은^[1] 이 문제에 대해 적극적으로 연구하고 있다. 이 글에서는 "알고리즘" 개념의 "성격"을 좀 더 자세히 소개할 것이다.

정의의 문제

지난 200년 동안 알고리즘의 정의는 연구자들이 이 용어를 고정시키려고 노력함에 따라 더욱 복잡하고 상세해졌다. 사실, "알고리즘"에는 두 가지 이상의 종류가 있을 수 있다. 그러나 대부분의 사람들은 알고리즘이 한정된 규칙 집합을 가진 구별 가능한 기호(숫자 수)의 조작에 의해 다른 "입력" 정수 - 임의적이고 무한하며 또는 범위가 제한되지만 여전히 가변적인 "입력 매개변수"에서 "출력" 정수를 생성하기 위한 일반화된 프로세스를 정의하는 것과 관련이 있다는 데 동의한다.사람은 종이와 연필로 공연할 수 있다.

공식 수학 및 일상 생활에서 가장 일반적인 숫자 관리 체계는 (1) 종이와 연필로 사람이 계산한 재귀 함수, (2) 튜링 기계 또는 그 튜링 동등물(원시 등록 기계 또는 "카운터 머신" 모델, 무작위 액세스 기계 모델(RAM), 저장 프로그(Random-access machine-Prog)이다.램 머신 모델(RASP) 및 그 기능에 상응하는 "컴퓨터".

우리가 "산술"을 할 때 우리는 정말로 초등학교에서 배운 속기 알고리즘의 "재발 기능"을 사용해서 계산하고 있다. 예를 들어, 덧셈과 뺄셈을 한다.

우리가 손으로 계산할 수 있는 모든 "재귀적 기능"은 기계에 의해 계산될 수 있고, 그 반대의 경우(계산 대 계산의 단어 사용)는 주목할 만하다. 그러나 이러한 동등성은 모든 계산/컴퓨팅을 포함한다는 논제(검증되지 않은 주장)와 함께 특정 알고리즘의 정의에서 튜링 등가 기계를 사용하는 데 왜 그렇게 많은 역점을 두었는지, 그리고 왜 "알고리즘"의 정의 자체가 종종 "튜링 머신"을 다시 언급하는지를 나타낸다. 이것은 스테판 클린의 성격화에서 더 자세히 논의된다.

다음은 좀 더 유명한 특성화(Kleene, Markov, Knuth)와 새로운 요소, 즉 정의를 더욱 확장하거나 보다 정확한 정의에 기여하는 요소들의 요약이다.

[ 수학적 문제와 그 결과는 공간의 두 점으로 간주될 수 있으며, 해법은 단계 순서나 이들을 연결하는 경로로 구성된다. 용액의 품질은 경로의 기능이다. 경로에 대해 정의된 속성이 둘 이상 있을 수 있다(예: 길이, 형상의 복잡성, 일반화 용이성, 난이도 등). ]

촘스키 계층 구조

「단순 알고리즘」이라는 개념의 「성격」에 대해서는 더 많은 공감대가 형성되어 있다.

모든 알고리즘은 형식적인 언어로 명시되어야 하며, "단순성 개념"은 언어의 단순성에서 비롯된다. 촘스키 (1956) 계층 구조는 격식어 언어를 생성하는 격식어 계통의 격납 계층 구조다. 프로그래밍 언어와 추상기계의 분류에 사용된다.

촘스키 계층 구조 관점에서 알고리즘을 (무제한보다) 간단한 언어로 지정할 수 있다면, 이런 종류의 언어로 특징지어질 수 있고, 그렇지 않으면 전형적인 "무제한 알고리즘"이다.

예: M4와 같은 "일반적인 목적" 매크로 언어는 제한되지 않지만(Turing complete), C 전처리기 매크로 언어는 그렇지 않기 때문에 C 전처리기에서 표현된 알고리즘은 "단순 알고리즘"이다.

복잡성 클래스 간의 관계를 참조하십시오.

양호한 알고리즘의 특징

다음은 Scheider와 Gersting(1995)에서 논의한 바와 같이 잘 정의된 알고리즘의 바람직한 특성이다.

• 모호하지 않은 운영: 알고리즘은 구체적이고 개략적인 단계를 가져야 한다. 단계는 각 단계에서 수행할 작업을 정확하게 명시할 수 있을 정도로 정확해야 한다.

• 정렬 상태: 알고리즘에서 수행되는 정확한 작동 순서를 구체적으로 정의해야 한다.
• 타당성: 알고리즘의 모든 단계가 가능해야 한다(효과적으로 계산할 수 있다고도 알려져 있다).
• 입력: 알고리즘은 잘 정의된 입력 집합을 수용할 수 있어야 한다.
• 출력: 알고리즘은 출력으로 어떤 결과를 생성하여 정확성을 추론할 수 있어야 한다.
• 정밀도: 알고리즘은 제한된 수의 지시 후에 종료되어야 한다.^[2]

바람직한 특정 알고리즘의 속성은 공간 및 시간 효율성, 일반성(즉, 많은 입력을 처리할 수 있는 능력) 또는 결정론을 포함한다.

1881년 존 벤의 W. 스탠리 제본스의 논리 기계 1870년에 대한 부정적 반응

1870년 초에 스탠리 제본스는 삼단논법이나 다른 논리 형식을 분석하기 위한 "논리적 기계"(Jevons 1880:200)를 제시했다. 예를 들어, 부울 방정식으로 축소된 주장. 쿠투랏(1914년)이 "논리 피아노의 일종 [,] ... 전제를 나타내는 동등성들 ...은 타자기의 그것과 같은 키보드에서 "연주"된다. ... 모든 전제가 "놀이"되었을 때, 패널은 합이 1인 유권자들, 즉 논리적 전체인 유권자들만 보여준다. 이 기계적인 방법은 BENN의 기하학적 방법보다 장점이 있다..."(1914:75)

제본스의 현대 논리학자 존 벤은 "현재 알려져 있거나 발견될 가능성이 있는 어떤 경쟁도 논리 기계라는 이름을 가질 자격이 없는 것 같다"(이태학적으로 덧붙여서, 벤 1881:120)고 말하면서 흥분하지 않았다. 그러나 "알고리즘"이라는 개념에 역사적으로 이용된 것은 "그렇지 않으면 필연적인 노동을 피할 수 있게 함으로써 정말 값진 목적을 달성할 수 있다"는 기계에 대한 그의 부정적인 반응에 대한 그의 설명이다.

(1) "먼저 정확한 논리적 언어로 된 우리 자료의 문장이 있다.",

(2) "그 다음, 두 번째로, 우리는 엔진과 함께 작동하기에 적합한 형태로 이러한 진술을 제시해야 한다 – 이 경우 각 제안이 기본적인 거부로 축소된다."

(3) "세 번째로, 그러한 감소 후에 우리 시설의 결합 또는 추가 처리가 있다."

(4) "결국 결과를 해석하거나 읽어야 한다. 이 마지막은 일반적으로 기술과 명석함에 대한 많은 개방성을 낳는다.

그는 "이러한 단계 중 세 번째 단계 외에는 어떤 기계도 우리를 돕기를 바랄 수 없다는 것을 알 수 없다. 그래서 이런 종류의 어떤 것이 정말로 논리 엔진의 이름을 받을 만한 가치가 있는지 매우 의심스러워 보인다"고 결론짓는다.(1881:119–121항).

1943년, 1952년 스티븐 클린의 특성화

이 절은 주제에 대한 중요성 때문에 다른 것들보다 더 길고 상세하다: 클레네는 모든 종류의 모든 계산/컴퓨팅(모든 종류의, 총합성)을 (i) 5개의 "1차 재귀 연산자"와 (ii) mu-operator라고 불리는 하나의 특수 연산자를 사용하여 동등하게 계산할 수 있다고 처음으로 제안했다. 튜링 기계 또는 동등한 모델의 동작

게다가, 그는 이들 중 어느 것이라도 알고리즘의 정의로 서게 될 것이라고 말했다.

뒤에 나오는 단어에 먼저 맞서는 독자는 당연히 혼란스러울 수 있으므로 간단한 설명이 순서다. 계산은 손으로, 계산은 튜링 기계(또는 동등한 것)에 의해 이루어진다. (때로는 저자가 말을 슬쩍하고 바꿔 쓰기도 한다.) "함수"는 "논란"이나 "변수"라고 불리는 자연수(그러나 0을 포함한 계수 숫자만 포함)를 넣고 하나의 비음수 정수(개념적으로 "답변"이라고 함)를 빼는 "입출력 상자"라고 생각할 수 있다. "기능 상자"를 "일반 재귀"를 사용하여 손으로 계산하거나 튜링 기계(또는 동등한 기계)에 의한 컴퓨팅으로 계산하는 작은 남자로 생각해 보십시오.

"효과적으로 계산 가능한/컴퓨팅 가능한"은 보다 일반적이며 "어떤 절차, 방법, 기법에 의해 계산 가능한/컴퓨팅 가능한"을 의미한다. 어쨌든..." "일반적인 재귀"는 오늘날 "재귀"라고 불리는 클레네의 글쓰기 방식이었다. 그러나 "원초적 재귀" 즉, 5명의 재귀적 운영자를 이용하여 계산하는 "원초적 재귀"는 드문 경우에만 필요한 여섯 번째, 추가의 뮤 운영자에 대한 접근성이 결여된 작은 재귀 형태다. 따라서 대부분의 생명은 "1차적 재귀 기능"만을 요구하는 생활을 계속한다.

1943년 "합성 1호", 1952년 "교회의 논문"

1943년 클레네는 교회의 논문으로 알려지게 된 것을 다음과 같이 제안했다.

"합성 1호. 모든 효과적으로 계산할 수 있는 함수(효과적으로 결정 가능한 술어)는 일반 재귀적이다."(Kleene이 1943년에 처음 진술했다(Davis의 274페이지, ed. Underdibleable; 또한 Kleene(1952) p.300에 문자 그대로 나타난다.

요컨대, 어떤 기능을 계산하기 위해서 필요한 유일한 수술은 (기술적으로, 공식적으로) "일반" 재귀의 6개 원시 연산자(요즘에는 뮤 재귀함수의 연산자라고 부른다)이다.

이에 대한 클레네의 첫 번째 진술은 "12"라는 섹션 제목 아래 있었다. 알고리즘 이론". 그는 나중에 그의 텍스트(1952)에서 다음과 같이 그것을 증폭시켰다.

"합성 I과 그 반대는 자연수의 함수(predicate)의 경우에 대한 계산(결정) 절차 또는 알고리즘의 개념에 대한 정확한 정의를 제공한다."(301 페이지, 강조를 위해 추가된 굵은 얼굴)

(그가 "결정"과 "predicate"라는 단어를 사용하는 것은 계산가능성의 개념을 수학적 "증명"에서 일어나는 것과 같은 더 일반적인 기호 조작으로 확장시킨다.

이것은 들리는 것만큼 위압적이지 않다 – "일반적인" 재귀는 추가 뮤 오퍼레이터와 함께 원시 재귀 함수의 다섯 "운영자"로부터 우리의 일상적인 산술 연산을 필요에 따라 만드는 한 가지 방법일 뿐이다. 실제로 클레네는 원시 재귀 함수의 13가지 예를 제시하고 볼로스-부르그네스-제프리는 몇 가지 더 추가하며, 그 대부분은 독자에게 친숙할 것이다(예: 덧셈, 뺄셈, 곱셈과 나눗셈, 지수화, CASE 함수, 결합 등). 목록은 몇 가지 일반적인 원시 재귀 함수를 참조한다.

왜 원시-재귀 기능보다는 일반-재귀 기능인가?

Kleene et al. (cf §55 General recursive functions p. 270 in Kleene 1952) had to add a sixth recursion operator called the minimization-operator (written as μ-operator or mu-operator) because Ackermann (1925) produced a hugely growing function—the Ackermann function—and Rózsa Péter (1935) produced a general method of creating recursive functions using 칸토어의 대각선 주장, 이 두 가지 중 어느 것도 5개의 원시-재귀 함수 연산자에 의해 설명할 수 없었다. Ackermann 기능과 관련하여:

"...어느 의미에서 원시적 재귀도 아닌 재귀함수의 계산 알고리즘의 길이는 어떤 원시적 재귀함수의 값보다 인수에 따라 더 빨리 커진다."(1935년) <미답지 않은 재귀함수>의 246페이지에 추가 연산자의 필요성에 관한 각주 13을 더하여 굵은 글씨로 추가했다.

그러나 뮤 오퍼레이터의 필요성은 드물다. 클렌의 공통적인 계산 리스트에서 위와 같이, 사람은 아커만의 기능(예: 초특급)에 의해 생성되는 몬스터 넘버를 마주칠 염려 없이 원초적인 재귀함수를 행복하게 계산하며 그들의 삶을 살아간다.

1952년 "튜링의 논문"

튜링의 이론은 튜링 머신 모델과 그 등가물에 의한 "모든 계산 가능한 함수"의 계산 가능성을 가설을 세운다.

효과적인 방법으로 이것을 하기 위해, 클레네는 "전체 기능"과 "부분 기능" 둘 다의 "기능"이라는 개념으로 허용함으로써, 망을 더 넓게 주조함으로써 "컴퓨팅"이라는 개념을 확장했다. 총함수는 모든 자연수(0을 포함한 양의 정수)에 대해 정의된 함수다. 부분 함수는 일부 자연수에 대해 정의되지만 전부는 아니다. "일부"의 사양은 "일부" 앞에 와야 한다. 따라서 "부분함수"의 포함은 함수의 개념을 "완벽하지 않은" 함수로 확장한다. 전체 및 부분 기능은 손으로 계산하거나 기계로 계산할 수 있다.

예:

"기능": "공통 감산 m - n" 및 "추가 m + n" 포함

"부분 함수": "공통 감산" m - n은 자연수(양수 정수와 0)만 입력으로 허용될 때 정의되지 않는다 – 예: 6 - 7은 정의되지 않는다.

전체 함수: "추가" m + n은 모든 양의 정수와 0에 대해 정의된다.

이제 우리는 "컴퓨팅"에 대한 클레네의 정의를 형식적인 의미로 관찰한다.

정의 : "부분함수 φ은 그것을 계산하는 기계 M이 있다면 계산이 가능하다." (Kleene (1952) 페이지 360)

"화질 2.5. n-ari 함수 f(x₁, ..., x_n)는 다음과 같은 튜링 기계 Z가 존재하는 경우 부분적으로 계산할 수 있다.

f(x₁, ..., x_n) = ψ_Z⁽ⁿ⁾(x₁, ..., [x_n)

이 경우에 우리는 [기계] Z가 f를 계산한다고 말한다. 덧붙여 f(x₁, ..., x_n)가 총함수라면, 계산가능" (Davis (1958) 페이지 10)이라고 한다.

그래서 우리는 튜링의 논문에 도착했다:

"자연스럽게 계산 가능하다고 여겨지는 모든 기능은 그의 기계에 의해 계산될 수 있다." (클레네(1952) 페이지 376)

비록 클렌은 다른 사람들이 가지고 있는 "컴퓨팅 기능"의 예를 보여주지는 않았지만. 예를 들어, 데이비스(1958)는 튜링에게 상수, 후계자 및 신원 함수에 대한 표를 제공하며, 원시 재귀 함수의 5개 연산자 중 3개 연산자:

튜링 기계로 계산 가능:

추가(한 피연산자가 0인 경우에도 상수 함수임)

증분(소처리기 기능)

공통 뺄셈(x ≥ y인 경우에만 정의됨). 따라서 "x - y"는 부분 계산 가능한 함수의 예다.

적절한 뺄셈 x┴y (위에서 정의한 바와 같이)

ID 함수: 각 i에 대해 U_Zⁿ = ψ_Zⁿ(x₁, ..., x_n) 함수가 존재하여 인수 집합에서 x를_i 추출(x_1n, ..., x)

곱하기

Boolos-Burgess-Jeffrey(2002)는 Turing 기계에 대한 산문적 설명으로 다음을 제공한다.

더블링: 2p

패리티

덧셈

곱하기

카운터 기계와 관련하여 Turing 기계와 동등한 추상 기계 모델:

Abacus 기계에 의한 계산 가능 예(cf Boolos-Burgess-Jeffrey(2002))

덧셈

곱하기

지수: (알고리즘의 흐름도/블록 다이어그램 설명)

주판 기계(Boolos-Burgess-Jeffrey(2002) 및 카운터 기계(Minsky 1967)에 의한 연산성의 시연:

6개의 재귀 함수 연산자:

1. 영함수
2. 후계 함수
3. 아이덴티티 함수
4. 구성함수
5. 원시재귀(유도)
6. 최소화

주판/대역 기계 모델이 재귀 기능을 시뮬레이션할 수 있다는 사실은 다음과 같은 증거를 제공한다: 어떤 기능이 "기계 계산 가능"인 경우, 그것은 "부분 재귀에 의한 손 계산 가능"이다. 클레네의 정리 XXIX :

"테오렘 XXIX: "모든 계산 가능한 부분함수 φ은 부분 재귀성..."(원본의 이탤릭체, 페이지 374).

그 역은 그의 정리 XXVIII로 나타난다. 이러한 것들이 함께 클린의 정리 XXX라는 등가성의 증거를 형성한다.

1952년 교회-튜링 논문

그의 정리를 통해 XXX Kleene은 교회논문과 튜링논문의 두 "이들"이 동등하다는 것을 증명한다. (Kleene은 오직 두 논문의 진실만을 가설을 세울 수 있을 뿐이며, 그는 증명하지 못했다.)

정리 XXX: 다음과 같은 부분함수의 클래스... 구성원이 같다: (a) 부분 재귀 함수, (b) 계산 가능한 함수..."(p. 376)

"부분적 재귀함수"의 정의: "부분함수 φ은 [부분함수] ψ₁₁, ...ψ에서_n φ을 재귀적으로 정의하는 방정식 E의 시스템이 있다면 [부분함수] ψ, ...ψ_n" (p. 326)

따라서 Kleene의 정리 XXX에 의해: 입력 번호로부터 숫자를 만드는 방법, 즉 손으로 계산하거나 튜링 기계 또는 동등한 것으로 계산한 회수 함수 중 어느 하나가 "효과적으로 계산할 수 있는/계산 가능한 함수"로 귀결된다. 만약 우리가 모든 계산/컴퓨팅이 어느 한 방법으로든 동등하게 이루어질 수 있다는 가설을 받아들인다면, 우리는 클레네의 정리 XXX(균등성)와 교회-튜링 논문("모든"의 가설)을 모두 수용한 것이다.

반대 의견서: "알고리즘에 더 많은 것이 있다..."블라스·구레비치(2003)

'처치-튜링 논문'에서 처치의 논문과 튜링의 논문을 분리하는 개념은 클레네(1952년)뿐만 아니라 블라스-구레비치(2003년)에서도 나타난다. 그러나 합의사항도 있지만 의견 차이도 있다.

"...우리는 알고리즘의 개념이 그만큼 잘 이해된다는 클레네와 의견이 다르다. 사실 요즘 알고리즘의 개념은 튜링 시절보다 더 풍부하다. 그리고 현대 및 고전적 다양성의 알고리즘이 있으며, 예를 들어, 튜링의 분석에서 직접적으로 다루지 않고, 그들의 환경과 상호작용하는 알고리즘, 추상적인 구조, 기하학적 알고리즘 또는 보다 일반적으로 비분해 알고리즘" (Blass-Gurevich(2003) 페이지 8, 굵은 얼굴 추가)

1954년 A. A. 마르코프 주니어의 성격묘사

안드레이 마르코프 주니어(1954)는 알고리즘의 다음과 같은 정의를 제공했다.

"1. 수학에서 "알고리즘"은 다양한 초기 데이터에서 원하는 결과로 이어지는 계산 과정을 정의하는 정확한 처방으로 일반적으로 이해된다."

"다음 세 가지 특징은 알고리즘의 특징이며 수학에서 그 역할을 결정한다.

"a) 재정상의 여지가 없는 처방전의 정확성, 그리고 그 보편적 이해성 - 알고리즘의 확실성;

"b) 주어진 한계 내에서 변할 수 있는 초기 데이터로 시작할 가능성 - 알고리즘의 일반성;

"c) 적절한 초기 데이터(알고리즘의 결정성)로 최종적으로 얻어지는 원하는 결과를 얻기 위한 알고리즘의 방향. (p.1)

그는 이 정의가 "수학적 정밀도를 가장하지 않는다"(p.1)고 인정했다. 1954년 그의 모노그래프는 알고리즘을 더 정확하게 정의하려는 시도였다. 그는 그의 결과적 정의인 "정상" 알고리즘을 "재귀함수의 개념과 동일하다"(p.3)고 보았다. 그의 정의에는 다음과 같은 4가지 주요 구성요소가 포함되었다(제2장 3페이지 63ff).

"1. 각 단계마다 [대체] 규칙 중 하나에 따라 수행되는 별도의 초등 단계... [처음에는 주었음]

"2. ... 지역 자연의 단계... [알고리즘이 관찰된 단어/심볼의 왼쪽 또는 오른쪽으로 특정 개 이상의 기호를 변경하지 않을 경우]

"3. 대체 공식에 대한 규칙... [그는 이러한 알고리즘의 목록을 "계략"이라고 불렀다.]

"4. ..."즉, 구별 가능한 "최종/최종" 상태 또는 상태를 구별하는 수단"

마르코프는 입문서에서 알고리즘을 보다 정확하게 정의하려는 노력의 "수학의 전체 중요성"이 "수학을 위한 건설적 기초의 문제와 관련"될 것이라고 보았다(2페이지). 이언 스튜어트(cf 백과사전 브리태니카)도 "...건설적 분석은 컴퓨터 과학과 같은 알고리즘 정신에 있다"는 비슷한 신념을 공유하고 있다.". 건설적인 수학과 직관주의를 더 자세히 보자.

구별성 및 위치: 두 개념 모두 튜링(1936–1937)과 함께 처음 등장했다.

"새로 관측된 사각형은 컴퓨터가 즉시 인식할 수 있어야 한다 [sic: 컴퓨터가 1936년에 사람이었습니다.] 즉시 관측된 정사각형 중 가장 가까운 정사각형으로부터의 거리가 일정한 고정량을 초과하지 않는 정사각형만 될 수 있다고 가정하는 것이 타당하다고 생각한다. 새로 관측된 각 정사각형이 이전에 관측된 정사각형 중 하나의 L 정사각형 안에 있다는 것을 그대로 두자."(Turing (1936) 페이지 136 (Davis Ed) 알 수 없음)

지역성은 구레비치와 간디(1980)의 작품에서 두드러지게 나타난다. 간디의 "제4의 메커니즘 원리"는 "지역 인과관계 원리"이다.

"우리는 이제 우리 원칙의 가장 중요한 것에 도달했다. 튜링의 분석에서 조치가 기록의 한정된 부분에만 의존한다는 요건은 인간의 제한에 기초했다. 우리는 이것을 지역 인과관계의 원리라고 부르는 물리적 한계로 대체한다. 그것의 정당성은 효과와 신호의 유한한 전파 속도에 있다: 현대 물리학은 먼 거리에서 즉각적인 작용의 가능성을 거부한다.(J. Barwise 등지의 Gandy (1980) 페이지 135).

1936년, 1963년, 1964년 괴델의 특성화

1936: 쿠르트 괴델의 다소 유명한 인용구는 <불복음> 82–83페이지에 실린 마틴 데이비스가 번역한 <증거의 길이에 대하여>의 논문에서 "원래 독일 출판물의 증거에 추가된 리마크"에 등장한다. 클레네, 구레비치, 간디 등 다수의 저자들이 다음을 인용했다.

"따라서, "컴퓨팅"의 개념은 어떤 확실한 의미 "절대적"에 있는 반면, 실질적으로 다른 모든 익숙한 변성 개념(예: 검증 가능, 정의 가능 등)은 그들이 정의되는 시스템에 상당히 본질적으로 의존한다."(p. 83)

1963: 1963년 8월 28일자 그의 유명한 논문에 추가된 "주"에서 괴델은 (각주에) "공식 시스템"이 "원칙적으로 그 안에서 추론하는 특징적인 성질을 가지고 있다는 그의 신념은 기계장치로 완전히 대체될 수 있다"(반 헤이제노르트의 616쪽)고 기술하고 있다. ". . . . "A. M. 튜링의 작업으로 인해 형식 시스템의 일반적 개념에 대한 정확하고 의심의 여지 없이 적절한 정의를 내릴 수 있으며, 이제 완전히 일반적인 버전의 이론 6호와 XI가 가능하다." (616 페이지) 1964년 다른 작품에 대한 노트에서 그는 같은 의견을 더 강하고 상세하게 표현한다.

1964: 1964년 날짜의 포스트스크립트(Postscriptum)에서 괴델은 1934년 봄 고등연구소에 제출한 논문에서 "공식 시스템"은 기계화할 수 있는 시스템이라는 확신을 증폭시켰다.

"나중의 진보의 결과, 특히 A. M. 튜링의 작업으로 인해 형식 시스템의 일반적 개념에 대한 정확하고 의심할 여지 없이 적절한 정의가 이제 주어질 수 있게 되었다." 튜링의 작업은 "기계적 절차"(별명 "알고리즘" 또는 "계산 절차" 또는 "완료적 결합 절차")의 개념에 대한 분석을 한다.절차(al procedure)"). 이 개념은 "튜링 머신"의 개념과 동등한 것으로 나타난다.* 공식 시스템은 단순히 공식을 생산하기 위한 기계적인 절차로 정의될 수 있으며, 이를 증명 가능한 공식이라 한다. . . . . (Martin Davis Ed의 페이지 72). 불해독성: 39페이지, loc. cit.)에 나오는 "불해독성 수학적 시스템의 불해독성 제안"에 대한 "후기"

*는 괴델이 앨런 튜링(1937)과 에밀 포스트(1936)의 논문을 인용한 후 다음과 같은 흥미로운 진술을 하는 각주를 나타낸다.

"그러나 우리의 목적에 훨씬 덜 적합한 이전의 계산능력에 대한 동등한 정의에 대해서는 알론조 교회, Am. J. 수학, 제58권(1936)[불해독 페이지 100-102]에 수록된 내용을 참조하라."

교회의 정의는 소위 "재기"와 "람다 미적분"(즉, λ 정의 가능한 기능)을 포함한다. 그의 각주 18에는 괴델과 '유효한 석회화성'과 '재발성'의 관계에 대해 논의했으나, 독자적으로 '효과적인 석회화성'과 '결정성'에 의문을 제기했다고 적혀 있다.

"우리는 이제 양의 정수의¹⁸ 재귀 함수(또는 양의 정수의 defin-defined 함수의 λ-defined 함수의 개념으로 그것을 확인함으로써 양의 정수의 유효 계산 가능한 함수의 개념 . .을 정의한다.

"지금 정의한 의미에서는 효과적으로 계산할 수 있는 양의 정수의 모든 기능에 대해 그 값의 계산을 위한 알고리즘이 존재한다는 것은 이미 지적된 바 있다.

"반대로 그것은 진실이다. . .." (p. 100, The Underdibleabled)

이것으로부터 나타날 것이고, 다음은 괴델에 관한 한 튜링 기계는 충분했고 람다 미적분은 "거의 덜 적합했다"는 것이다. 그는 계속해서 인간 이성의 한계와 관련하여, 배심원단은 여전히 배제되어 있다는 점을 강조한다.

("어떤 알고리즘과 동등하지 않은 유한 비기계적 절차**가 존재하는지 여부에 대한 질문은 "공식 시스템"과 "기계적 절차"의 정의의 적절성과 전혀 관련이 없다.) (p. 72, loc. cit)

"(각주에 제시된 보다 일반적인 의미의 이론과 절차에 대해서는) 상황이 다를 수 있다. 추신에 언급된 결과는 인간 이성의 힘에 대한 어떤 한계도 정립하지 않고 오히려 수학의 순수한 형식주의의 잠재력에 대한 것이라는 점에 유의한다.) (p. 73 loc. cit)

각주 **: "즉, 그 의미에 기초하여 추상적인 용어를 사용하는 것과 같은 것. 다이얼 12(1958), 페이지 280" (이 각주는 72페이지, loc. cit에 표시됨).

1967년 민스키의 특성화

민스키(1967)는 대놓고 "알고리즘은 효과적인 절차"라고 주장하며 그의 텍스트에서 "알고리즘"이라는 단어를 더 이상 사용하지 않으려고 한다. 사실 그의 지수는 "알고리즘, 효과적인 절차의 동의어" (p. 311)에 대해 그가 느끼는 감정을 분명히 한다.

이어 "후기에 [유효한 절차]라는 용어를 쓰겠다. 용어들은 대략 동의어지만, 특히 '알고리즘'(원본의 이탈리아어, 페이지 105)에 대해 다른 맥락에서 사용되는 여러 가지 의미의 음영이 있다.

다른 작가(아래 크누스 참조)는 "유효한 절차"라는 단어를 사용한다. 이것은 사람을 다음과 같이 의아하게 만든다. 민스키의 "유효한 절차"의 개념은 무엇인가? 그는 먼저 다음과 같이 시작한다.

"...순간부터 순간까지 정확히 어떻게 행동해야 하는지 알려주는 일련의 규칙들"(페이지 106)

그러나 그는 이것이 비판의 대상이 된다는 것을 인정한다.

"…규칙의 해석은 어떤 사람이나 대리인에게 맡겨져 있다는 비판"(p. 106)

그의 세련됨? "규칙의 문장과 함께 그것들을 해석하는 메커니즘의 세부사항을 명시한다." 그는 "각각의 개별 절차에 대해 이 과정을 다시 해야 한다"는 "합리적으로 균일한 규칙 준수 메커니즘의 가족"을 식별하고자 한다. 그의 "형식"은 다음과 같다.

"(1) 행동수칙의 집합이 표현되어야 하는 언어, 그리고

"(2) 언어로 된 문장을 해석하여 각 지정된 프로세스의 단계를 수행할 수 있는 단일 기계" (이태리학 원문, 모두 이 107쪽을 인용)

그러나 결국 그는 "주관적인 측면이 남아 있다"고 우려한다. 다른 사람들은 특정 절차를 효과적이라고 불러야 하는지에 대해 동의하지 않을 수 있다."(107쪽)

그러나 민스키는 변하지 않았다. 그는 즉시 "Turing's Analysis of Computing Process"(그의 5.2장)를 소개한다. 그는 이른바 튜링의 논문을 인용한다.

"자연스럽게 효과적인 절차라고 할 수 있는 모든 과정은 튜링 기계에 의해 실현될 수 있다."(p. 108.)(민스키는 이것을 보다 일반적인 형태로 "교회의 논문"이라고 말한다.)

"튜링의 주장" (그의 5.3장)을 분석한 후, 그는 튜링, 교회, 클레네, 포스트, 스물리얀의 "많은 직관적 공식의 동일성"을 관찰한 결과, 우리는 정말로 여기에 '객관적' 또는 '절대적' 개념이 있다고 생각하게 된다. Rogers [1959]의 설명에 따르면 다음과 같다.

"이런 의미에서, 효과적으로 계산할 수 있는 기능의 개념은 수학의 기초에서 현대 작업에 의해 생성된 몇 안 되는 '절대' 개념 중 하나이다."(민스키 페이지 111 로저스, 하틀리 주니어(1959)를 인용하여) 튜링 머신 연산성의 현재 이론, J. SIAM 7, 114-130.)

1967년 로저스의 특징

그의 1967년 재귀적 기능과 효과적인 계산가능성의 이론에서 하틀리 로저스는 대략 "알고리즘"을 "... . 상징적 입력에 적용되고, 그러한 입력에 대해 결국 상응하는 상징적 출력" (p. 1)으로 특징짓는다. 그런 다음 그는 계속해서 "근사적이고 직관적인 용어"라는 개념을 10개의 "특징"을 가지고 있으며, 그 중 5개는 "사실상 모든 수학자들이 [수능]에 동의할 것"이라고 주장한다(p. 2). 나머지 5개는 "*1 ~ *5보다 명확하지 않고, 일반적인 합의가 덜 될 수도 있다"(3페이지)고 주장한다.

5 "불확실성"은 다음과 같다.

• 1 알고리즘은 크기가 유한한 명령어 집합이다.
• 2 유능한 컴퓨터 에이전트가 있다.
• 3 "계산 단계에서 단계를 만들고, 저장하고, 검색하는 기능이 있다"
• 4 #1 및 #2 주어진 경우, 에이전트는 연속적인 방법이나 아날로그 장치를 사용하지 않고 "단계적 단계적 패션"으로 계산한다.
• 5 컴퓨팅 에이전트는 "예를 들어, 주사위 등 무작위 방법이나 장치에 의존하지 않고" 계산을 진전시킨다(각주에서는 #4와 #5가 정말 동일한지 궁금해).

그가 토론할 나머지 5개는 다음과 같다.

• 6 입력 크기에 고정된 제한 없음,
• 7 지침서 세트의 크기에 고정된 제한 없음,
• 8 사용 가능한 메모리 저장 용량에 대해 고정된 제한이 없음,
• 9 컴퓨팅 에이전트의 용량 또는 능력에 대한 고정 유한 경계(로저스는 포스트-튜링 기계 또는 카운터 기계와 유사한 간단한 메커니즘을 예로 들어 설명한다)
• 계산의 길이에 대한 10 A 바운드는 "우리가 '시간초'라는 아이디어를 가져야 한다. 계산하는 데 얼마나 걸릴 것인가?" ( 페이지 5). 로저스는 "일부 한정된 수의 스텝 후에만 연산이 종료된다. 우리는 이 숫자를 추정할 선험적 능력을 고집하지 않는다."(5 페이지)를 요구한다.

1968년, 1973년 크누스의 특징

Knuth(1968, 1973년)는 알고리즘의 요건으로 널리 받아들여지는 5가지 특성 목록을 제공했다.

1. 정밀도: "알고리즘은 항상 한정된 단계 수 ... 매우 유한한 수, 합리적인 수"
2. 명확성: "알고리즘의 각 단계는 정확하게 정의되어야 하며, 수행할 조치는 각 경우에 대해 엄격하고 명확해야 한다."
3. 입력: "...알고리즘이 시작되기 전에 처음에 주어지는 수량. 이러한 입력은 지정된 객체 집합에서 취함"
4. 출력: "...입력 관련 지정 수량"
5. 효과 : "...알고리즘에서 수행될 모든 연산은 원칙적으로 종이와 연필을 사용하는 사람에 의해 정확하고 유한한 시간 내에 수행될 수 있을 정도로 충분히 기초적이어야 한다."

크누스는 두 개의 자연수(cf) 중 가장 큰 공통점(cf)을 결정하기 위한 유클리드 알고리즘을 예로 제시한다. Knuth Vol. 1 페이지 2).

크누스는 알고리즘에 대한 그의 설명은 직관적으로 명확할 수 있지만, 형식적인 엄격함이 결여되어 있다는 것을 인정한다. 왜냐하면, "정확하게 정의"라는 것이 정확히 무엇을 의미하는지, 또는 "충분히 기본적"이라는 의미 등이 명확하지 않기 때문이다. 그는 그의 "신비한 혼합물"을 위해 그가 "기계 언어"라고 부르는 것을 상세히 정의하는 그의 첫 번째 책에서 이러한 방향으로 노력한다.세계 최초의 다불포화 컴퓨터" (pp. 120ff) 그의 책에 있는 많은 알고리즘은 MIX 언어로 쓰여져 있다. 그는 또한 나무 다이어그램, 흐름도, 상태 다이어그램도 사용한다.

알고리즘의 "좋은 점", "최상의" 알고리즘: 크누스는 "실제로 우리는 알고리즘을 원할 뿐만 아니라 좋은 알고리즘을 원한다"고 말한다. 그는 알고리즘의 선함의 몇 가지 기준은 알고리즘을 수행하기 위한 단계 수, "컴퓨터에 대한 적응성, 그 단순성과 우아함 등"이라고 제안한다.같은 계산인데, 어떤 계산이 "최상"인가? 그는 이러한 종류의 조사를 "알고리즘 분석: 알고리즘을 부여하여 성능 특성을 결정한다"라고 부른다(모두 이 단락: Knuth Vol. 1 페이지 7 참조).

1972년 스톤 특성화

스톤(1972년)과 크누스(1968년, 1973년)는 동시에 스탠포드 대학의 교수였기 때문에 그 정의에 유사성이 있다고 해도 놀랄 일이 아니다.

"요약하면... 알고리즘을 각 규칙이 효과적이고 확실하며 시퀀스가 유한한 시간에 종료되도록 일련의 작업을 정밀하게 정의하는 규칙으로 정의한다."(볼드페이스 추가, 페이지 8)

스톤은 무엇이 "효과적인" 규칙을 구성하는가에 대한 자세한 논의 때문에 주목할 만하다. – 그의 로봇 또는 사람-행동하는 로봇은 그 안에 어떤 정보와 능력을 가지고 있어야 하며, 그렇지 않다면 "알고리즘"에서 정보와 능력을 제공해야 한다.

"사람들이 알고리즘의 규칙을 따르려면 규칙을 공식화해서 로봇 같은 방식으로, 즉 생각할 필요 없이... 그러나 [2차 방정식을 푸는 방법, 그의 예]라는 지시사항을 산술 연산을 할 줄 알지만 제곱근을 추출할 줄 모르는 사람에 의해 복종해야 한다면, 알고리즘의 정의를 충족시키기 위해 제곱근을 추출하는 일련의 규칙도 제공해야 한다."(4-5)

게다가, "...모든 지시서가 우리가 타당하다고 생각하는 것 이상의 능력을 로봇에게 요구할 수도 있기 때문에, 모든 지시사항이 받아들여지는 것은 아니다." 그는 이 질문에 직면한 로봇의 예를 들며 "Henry 8a a King of England?"라고 하며, "그렇다면 1을, 그렇지 않으면 0을 인쇄하는 것이지만, 로봇은 이전에 이 정보를 제공받지 못했다. 그리고 더 나쁜 것은, 이 로봇이 아리스토텔레스가 영국 왕이었는지, 그리고 이 로봇에게 다섯 개의 이름만 제공되었는지를 묻는다면, 어떻게 대답해야 할지 모를 것이다. 따라서 다음과 같다.

"허용 가능한 지침 순서에 대한 직관적인 정의는 로봇이 명령을 준수할 수 있도록 각 지침을 정확하게 정의하는 것이다."(6 페이지)

스톤은 튜링 머신 모델(Turing machine model)을 소개한 뒤, 기계의 지시사항인 5개 튜플 세트는 "튜링 머신 프로그램(Turing machine program)"이라고 밝혔다. 그 직후 그는 "튜링 머신의 컴퓨터화는 다음과 같이 기술되어 있다"고 말한다.

"1. 테이프 알파벳

"2. [입력] 파라미터가 테이프에 표시되는 형태

"3. 튜링 기계의 초기 상태

"4. 튜링 기계가 정지할 때 테이프에 [출력]이라고 대답하는 형식

"5. 기계 프로그램"(이탈리아 추가, 페이지 10)

'계산'에 필요한 것에 대한 이 정밀한 처방은 블라스와 구레비치의 작품에서 어떤 일이 뒤따를 것인가 하는 정신에 있다.

1995년 소어의 특성화

"연산은 우리가 프로그램, 절차 또는 알고리즘이라 불리는 고정된 규칙 집합에 따라 입력이라 불리는 처음 주어진 개체로부터 일련의 단계를 거쳐 이 단계들의 끝에 도달하는 과정이다. 알고리즘은 입력에서 출력으로 진행되는 규칙 집합으로서, 각 연속적인 단계를 명확하게 결정하면서 정확하고 확실해야 한다. 계산가능성의 개념은 원칙적으로 계산에 의해 지정될 수 있는 물체와 관련이 있다. . . . . . (원래 굵은 체형의 생명체 추가 페이지 3)

2000년 베를린스키의 특징

1960년대 중반 프린스턴대 학생이었던 데이비드 베를린스키는 알론조 교회(cf 페이지 160)의 학생이었다. 그의 2000년 책 "알고리즘의 도래": 아이디어에서 컴퓨터로 300년의 여정은 알고리즘의 다음과 같은 정의를 포함하고 있다.

"논리학자의 목소리로 다음과 같이 말했다.

"알고리즘은

한정된 절차,

고정된 상징적 어휘로 쓰여진

정확한 지시에 따라

별개의 단계로 움직인다. 1, 2, 3, . . . . .

그 집행을 위해서는 통찰력이 필요없고 영리하고

직감, 지능, 또는 근면성,

곧 끝날 것이다."(원문, p. 16ii)

2000, 2002년 구레비치의 특성화

구레비치 2000을 주의 깊게 읽으면 실제로 "알고리즘"이 계산을 하는 "튜링 머신" 또는 "포인터 머신"이라고 믿는다는 결론을 내리게 된다. "알고리즘"은 기계의 동작을 안내하는 기호 표일 뿐만 아니라 특정 입력 매개변수 세트가 주어진 계산을 수행하는 기계의 한 인스턴스일 뿐 아니라 전원을 끈 상태에서 적절하게 프로그램된 기계도 아니다. 오히려 알고리즘은 기계의 기능을 실제로 계산하는 기계다. 구레비치는 바로 나와서 이렇게 말하지 않기 때문에 이 결론 위에 (추론?)이 언급된 바와 같이 분명히 논쟁의 여지가 있다.

" . . . . 모든 알고리즘은 튜링 기계에 의해 시뮬레이션될 수 있다 . 프로그램을 시뮬레이션 할 수 있고 따라서 튜링 기계에 의해 정확한 의미를 부여할 수 있다." (p. 1)

" 흔히 순차 알고리즘의 개념을 공식화하는 문제는 교회[1936]와 튜링[1936]에 의해 해결되었다고 생각한다. 예를 들어, 새비지[1987]에 따르면 알고리즘은 튜링 기계에 의해 정의된 계산 과정이다. Church와 Turing은 순차 알고리즘의 개념을 공식화하는 문제를 해결하지 못했다. 대신에 그들은 계산 가능한 함수의 개념에 대한 (다르지만 동등한) 공식화를 주었고, 알고리즘에는 그것이 계산하는 함수보다 더 많은 것이 있다. (이탈리아 추가 페이지 3)

"물론 알고리즘과 계산 가능한 함수의 개념은 밀접하게 관련되어 있다. 정의상 계산 가능한 함수는 알고리즘에 의해 계산 가능한 함수다. ( 페이지 4)

블라스와 구레비치 2002에서 저자들은 "Quisani"("Q")와 "Outhors" (A) 사이의 대화를 호출하여 이안니스 모쇼바키스를 호일로 이용, 거기서 바로 나와 다음과 같이 단호하게 진술한다.

"가: 이견을 국지화하려면 먼저 두 가지 합의점을 언급하자. 첫째로, 누구의 정의에 의해서도 분명히 알고리즘인 것들이 있다. 튜링 머신, 순차 시간 ASM [추상 상태 머신] 등. 둘째, 다른 극단에서는 어떤 것을 계산하는 방법에 대해 아무런 지시도 주지 않기 때문에, 누구의 정의에 따른 알고리즘으로 간주되지 않는 사양들이다. 문제는 알고리즘으로 계산하기 위해 정보가 얼마나 상세해야 하는가에 관한 것이다.…. 모쇼바키스는 선언적 규격이라고만 부를 몇 가지를 허용하고, 아마도 알고리즘이라고 하는 것에 대해 "이행"이라는 단어를 사용할 것이다.(가독성을 위해 가입한 단락, 2002:22)

"이행"이라는 단어를 이렇게 사용함으로써 문제의 핵심을 바로 알 수 있다. 논문 초기의 Q는 모쇼바키스에 대한 그의 독서를 다음과 같이 기술하고 있다.

"...[H]e는 아마도 [구레비치는 마이크로소프트에서 일한다]는 당신의 실무적인 작업이 알고리즘보다는 구현을 더 생각하게 한다고 생각할 것이다. 그는 기계로 구현을 식별하려는 의지가 꽤 있지만 알고리즘은 좀 더 일반적인 것이라고 말한다. 요컨대 알고리즘은 기계라고 하고 모스코바키스는 그렇지 않다고 한다."(2002:3)

그러나 저자들은 여기서 "알고리즘과 기계에 집착한다"고 말하고 독자는 다시 혼란에 빠졌다. 우리는 더쇼비츠와 구레비치 2007년까지 기다려야 다음 각주의 말을 들을 수 있다.

" . . 그럼에도 불구하고 모쇼바키스의 관점을 받아들인다면 그것은 우리가 특성화하기 위해 설정한 알고리즘의 "이행"이다."(cf 각주 9 2007:6)

2003년 블래스와 구레비치의 특성화

이 구간은 확장이 필요하다. 추가하면 도움이 된다. (2008년 6월)

Blass와 Gurevich는 그들의 작업이 Turing 기계와 포인터 기계, 특히 Kolmogorov-Uspensky 기계(KU 기계), Schönnagage Storage Modification Machines(SMM), Knuth가 정의한 오토마타 연결에 대한 고려에서 진화했다고 설명한다. 간디와 마르코프의 작품도 영향력 있는 선행자로 묘사된다.

Gurevich는 알고리즘에 대한 '강력한' 정의를 제공한다(볼드페이스 추가):

"...그의 논문에 찬성하는 튜링의 비공식적인 주장은 더 강한 논제를 정당화한다: 모든 알고리즘은 튜링 기계에 의해 시뮬레이션될 수 있다...실제로 보면 어처구니없을 것이다...[그럼에도 불구하고] [c]어떤 알고리즘도, 얼마나 추상적이든, 일반화된 기계에 의해 모델링될 수 있도록 튜링 기계를 하나로 일반화한다?...그러나 이와 같이 일반화된 튜링 기계가 존재한다고 가정해 보자. 그들의 상태는 어떤가?... 일차 주문 구조... 모든 경우에 있어서 특정한 작은 명령 집합으로 충분하다... 국가의 진화로서 계산하는 것은 비결정론적일 수 있다... 그들의 환경과 상호작용을 할 수 있다... 병렬 및 다중 에이전트... 동적인 의미론... [그들의 작품의 두 가지 밑바탕은:] 튜링의 논문 ...[그리고] [타르스키 1933]의 (첫 번째 순서) 구조의 개념" (구레비치 2000, 페이지 1-2)

국가의 진화로서 계산하는 위의 구절은 튜링 기계 프로그램으로서의 "알고리즘"인 크누스와 스톤(Knuth and Stone)의 정의와 현저하게 다르다. 오히려 튜링이 전체 구성(Cf Turing의 정의, Undervibleable, 페이지 118)이라고 부른 것에 해당하며, 현재 명령(상태)과 테이프의 상태를 모두 포함한다. [cf Kleene(1952) 페이지 375에서 그는 6개의 기호가 있는 테이프의 예를 보여준다. 다른 모든 사각형은 공백이며, 결합된 테이블 테이프의 상태를 Gödel화하는 방법.

알고리즘 예에서 우리는 주의 진화를 직접 본다.

1995 – Daniel Dennett: 알고리즘 프로세스로서의 진화

철학자 대니얼 데넷은 1995년 저서 다윈의 위험한 아이디어에서 알고리즘적 과정으로서의 진화의 중요성을 분석한다. Dennett는 알고리즘의 세 가지 주요 특징을 식별한다.

• 기판 중립성: 알고리즘은 그 논리 구조에 의존한다. 따라서 알고리즘이 발현되는 특정한 형태는 중요하지 않다(Dennett의 예는 긴 분할이다: 종이, 양피지, 컴퓨터 화면, 또는 네온 조명이나 스카이라이터에서 동등하게 잘 작동한다). (51)
• 기반 무신경: 알고리즘 프로세스의 최종 산출물이 아무리 복잡하더라도 알고리즘의 각 단계는 비지향적이고 기계적인 장치에 의해 수행될 수 있을 만큼 충분히 단순하다. 알고리즘은 그것을 유지하거나 운용하기 위해 "브레인"을 필요로 하지 않는다. "표준 교과서 유추에 따르면 알고리즘은 초보자 요리사가 따르도록 고안된 종류의 요리법이다."(51쪽)
• 보장된 결과: 알고리즘이 올바르게 실행되면 항상 동일한 결과를 생성하게 된다. "알고리즘은 바보 같은 레시피다."(51

Dennett이 "다윈에 따르면, 진화는 알고리즘 과정이다."(p. 60)라고 결론짓는 것은 이러한 분석에 근거한다.

하지만, 이전 페이지에서 그는 훨씬 더 많은 일을 했다.^{[according to whom?]} "알고리즘으로서의 과정"이라는 제목의 그의 장의 맥락에서 그는 다음과 같이 말한다.

"하지만 그렇다면... 알고리즘적 과정으로 간주될 수 있는 것에 대한 제한은 전혀 없을까? 대답은 NO인 것 같다; 원하면 추상적인 수준에서 어떤 과정이라도 알고리즘적 과정으로 다룰 수 있다.…. 어리둥절하다고 생각되는 것이 [오션] 모래알의 균일성이나 [성질-강철] 칼날의 강도라면, 알고리즘적 설명은 당신의 호기심을 충족시켜 줄 것이다. 그리고 그것은 진실일 것이다.

"알고리즘의 생산물이 아무리 인상적이라 할지라도, 기본 과정은 항상 지능적인 감시의 도움 없이 서로 이어지는 일련의 개별적인 [sic] 무신경한 단계들로 구성된다; 그것들은 정의상 '자동화: 자동화의 작용'이다."(59)

위의 내용으로부터 Dennett이 관찰자가 없는 물리적인 세계 자체가 본질적으로 알고리즘(컴퓨팅)이라고 말하는 것인지 아니면 기호 처리 관찰자가 관찰에 "의미"를 추가하는 것인지 불분명하다.

2002년 John Searle은 Dennett의 성격화에 명확한 주의사항을 추가했다.

대니얼 데넷은 강력한 인공지능을 지지하는 사람이다: 알고리즘의 논리적 구조가 마음을 설명하기에 충분하다는 생각이다. 중국 방 사고 실험의 창시자인 존 서얼은 "합성세[즉, 논리구조]만으로는 의미론적 내용[즉, 의미]에 충분하지 않다"(Searle 2002, 페이지 16)고 주장한다. 즉, 기호의 "의미"는 그것을 사용하는 정신에 상대적이다; 알고리즘, 즉 논리적인 구성 그 자체는 정신에 불충분하다.

Searle은 알고리즘(컴퓨팅) 과정이 자연에 내재되어 있다고 주장하는 사람들(예: 우주론자, 물리학자, 화학자 등)에게 주의를 준다.

연산 [...]은 관찰자-상대적이며, 이는 계산이 기호 조작의 관점에서 정의되기 때문이지만, '기호'의 개념은 물리학이나 화학의 개념이 아니다. 어떤 것은 그것이 사용되거나, 취급되거나, 또는 상징으로 간주될 때만 상징이다. 중국 방 논거는 의미론이 구문에 내재되어 있지 않다는 것을 보여주었다. 그러나 이것이 보여주는 것은 구문이 물리학에 내재되어 있지 않다는 것이다.] [...] 어떤 것은 그것에 상징적인 해석을 할당하는 어떤 관찰자, 사용자 또는 대리인에게만 상대적인 상징이다 [...] 당신은 어떤 것에든 계산적 해석을 할당할 수 있다. 그러나 만약 "의식이 본질적으로 계산적인가?"라고 묻는다면, 답은: 아무것도 본질적으로 계산적인 것이 아니다. [중점을 위해 추가된 이탤릭체] 계산은 어떤 현상에 대해 계산적 해석을 부과하는 일부 에이전트나 관찰자에 관해서만 존재한다. 이것은 명백한 점이다. 10년 전에 봤어야 했는데 못 봤어.

— John Searle, Searle 2002, p. 17

2002: 튜링 머신 계산의 Boolos-Burgess-Jeffrey 사양

추가 알고리즘 "m+n"에 적용된 이 사양 방법의 예는 알고리즘 예제를 참조하십시오.

Boolos-Burgess-Jeffrey(2002) (pp. 31–32)의 예는 알고리즘의 완전한 사양에서 요구되는 정밀도를 보여준다. 이 경우, m+n이라는 두 개의 숫자를 추가한다. 그것은 위의 스톤 요구사항과 유사하다.

(i) 그들은 계산에서 "숫자 형식"의 역할을 논의했고 숫자를 나타내기 위해 "수평 표기법"을 선택했다.

"확실히 계산은 어떤 명언으로는 다른 명언보다 실제적으로 더 어려울 수 있다... 하지만... 원칙적으로 다른 표기법으로 하는 것은 가능하다, 단순히 데이터를 번역하는 것만으로... 계산가능성에 대해 엄격하게 정의된 개념을 형성하기 위해, 단음절 또는 집계 표기법을 사용하는 것이 편리하다."(25-26)

(ii) 예를 시작할 때 그들은 계산에 사용할 기계를 튜링 기계로 지정한다. 그들은 이전에 튜링 머신이 5-튜플이 아닌 4-튜플이 될 것이라고 (p. 26) 명시했다. 이 컨벤션에 대한 자세한 내용은 튜링 머신을 참조하십시오.

(iii) 이전에 저자들은 테이프 헤드의 위치가 스캔한 기호의 오른쪽에 있는 첨자로 표시되도록 명시했다. 이 컨벤션에 대한 자세한 내용은 튜링 머신을 참조하십시오. (다음에서는 강조하기 위해 굵은 얼굴을 추가한다.

"우리는 입력이나 인수가 기계에 어떻게 표현되어야 하는지, 출력이나 값이 어떻게 표현되어야 하는지를 명시하면서 튜링 기계에 의해 계산 가능한 것이 수치 함수가 무엇인지에 대한 공식적인 정의를 내리지 않았다. 양의 정수에서 양의 정수까지의 k-place 함수에 대한 우리의 사양은 다음과 같다.

"(a) [초기번호 형식:] 인수₁ m, ...m_k, ...는 그 획수의 블록에 의해 단음 [단일] 표기법으로 표시되며, 각 블록은 다음 블록에서 한 개의 공백으로 분리된다.

예: 3+2, 111B11

"(b) [초기 헤드 위치, 초기 상태:] 초기에는 기계가 테이프에서 가장 왼쪽 1을 스캔하여 초기 상태인 상태 1이 된다.

예: 3+2, 1111B11₁

"(c) [성공적인 연산 - 정지:] 계산될 함수가 처음에 테이프에 나타난 인수에 n 값을 할당하면, 결국 스트로크 블록이 들어 있는 테이프에서 기계가 정지하고, 그렇지 않으면 공백이 된다...

예: 3+2, 11111

"(d) [성공적인 연산 -- Stop:] 이 경우 [c] 기계는 테이프에서 가장 왼쪽 1의 스캔을 중지한다...

예: 3+2, 11111_n

"(e) [실패한 연산 -- 비표준 숫자 형식의 정지 또는 정지 실패:] 계산되는 함수가 처음에 테이프에 나타난 인수에 값을 할당하지 않으면 기계는 절대 정지하지 않거나 일부 비표준 구성에서 정지하지 않을 것이다..."(아이비드)

예: B11111_n 또는 B11111_n 또는 B11111_n

이 명세서는 불완전하다. 이 명세서는 지시사항의 위치 및 그 형식은 기계에서 필요로 한다.

(iv) 유한 상태 기계의 TABLE 또는 테이프에 있는 범용 튜링 기계의 경우,

(v) 지정된 형식의 지침 표

이 나중의 지점은 중요하다. Boolos-Burgess-Jeffrey는 표에 기재된 기재사항의 예측가능성이 순서대로 기재하고 입력 상태와 기호를 생략하여 표의 "축소"를 할 수 있다는 것을 실증(p. 36)한다. 실제로 튜링 머신 계산의 예는 아래 표와 같이 4개의 열만 필요했다(그러나 참고: 이것들은 기계에 행으로 표시됨).

주 qk	스캔 기호	액션	넥스트 스테이트 qk		주 qn	스캔 기호	액션	넥스트 스테이트 qk		주 qk	B-액션	B-다음 주 qkB	1액션	1: 다음 상태 qk1
1	B	R	H		1	1	R	2		1	R	H	R	2
2	B	P	3		2	1	R	2		2	P	3	R	2
3	B	L	4		3	1	R	3		3	L	4	R	3
4	B	L	5		4	1	E	4		4	L	5	E	4
5	B	R	H		5	1	L	5		5	R	H	L	5

2006년: Sipser의 주장과 그의 세 가지 수준의 설명

추가 알고리즘 "m+n"에 적용된 이 사양 방법의 예는 알고리즘 예제를 참조하십시오.

Sipser는 ''알고리즘''을 다음과 같이 정의하면서 시작한다.

"비공식적으로 말하면 알고리즘은 어떤 일을 수행하기 위한 간단한 지시의 집합체다. 일상 생활에서 흔히 볼 수 있는 알고리즘을 절차나 조리법(원래로는 이태리학, 페이지 154)이라고 부르기도 한다.

"...지금부터 우리의 진짜 초점은 알고리즘에 있다. 즉, 튜링 기계는 알고리즘 정의에 대한 정확한 모델 역할만 할 뿐.... 튜링 기계가 모든 알고리즘을 캡처한다고 믿을 수 있을 정도로만 있으면 된다."( 페이지 156)

Sipser는 "알고리즘"이 튜링 기계에 대한 "지침"에 불과하다는 뜻인가, 아니면 "지침 + (특정 다양한) 튜링 기계"의 조합인가? 예를 들어, 그는 자신의 특정 변종(튜링의 원본과 동일하지 않음)의 두 가지 표준 변종(다중 테이프와 비결정론적)을 정의하고 계속하여 그의 문제(160-161페이지)에서 네 가지 변종(쓰기-한 번, 두 배로 무한 확장 테이프(즉, 왼쪽과 오른쪽 무한 확장 테이프), 왼쪽 재설정, 그리고 "좌측 대신 put put put"을 설명한다. 게다가, 그는 약간의 제약을 가한다. 첫째, 입력은 문자열(p. 157)로 인코딩되어야 하며, 복잡성 이론의 맥락에서 숫자 인코딩을 언급해야 한다.

"그러나 (단일 번호 1111111111111111111111111111111111)로 인코딩되는 숫자 17에 대한 단일 표기법은 어떤 k ≥ 2에 대한 기본 k 표기법과 같이 정말로 합리적인 인코딩보다 기하급수적으로 크기 때문에 합리적이지 않다는 점에 유의한다."(259 페이지)

Van Emde Boas는 "알고리즘 분석"을 수행할 때 튜링 머신 대신 가끔 사용되는 계산의 RAM(Random-access Machine) 추상적 모델에 관해 유사한 문제에 대해 언급한다: "승법적이고 병렬적인 비트 조작의 부재 또는 존재는 일부 결과의 정확한 이해와 관련이 있다. 알고리즘 분석에 있어

". . . . . [T]여기에는 균일한 시간 측정에서 표준 RAM 모델의 "무결한" 확장 같은 것이 거의 존재하지 않는다. 하나는 적층 산술만을 가지고 있거나 아니면 다른 하나는 작은 피연산자에 대한 모든 합리적인 승법 및/또는 비트 비트의 부울 지침을 포함할 수 있다." (Van Emde Boas, 1990:26)

알고리즘에 대한 "설명 언어"와 관련하여 Sipser는 스톤과 볼로스-Burgess-Jeffrey가 시작한 작업을 마무리한다(볼드페이스가 추가됨). 그는 우리에게 튜링 머신 알고리즘에 대한 세 가지 수준의 설명을 제공한다 ( 페이지 157).

높은 수준의 설명: "어디서 우리가 알고리즘을 설명하기 위해... 산문을 사용하는가, 구현 세부사항을 무시한 채. 이 수준에서는 기계가 테이프나 헤드를 어떻게 관리하는지 언급할 필요가 없다."

구현 설명: "Turing 기계가 머리를 움직이는 방식과 테이프에 데이터를 저장하는 방식을 설명하기 위해 ...문을 사용하는 방법. 이 수준에서는 상태나 전환 기능에 대한 세부사항을 제공하지 않는다."

공식 설명: "... 가장 낮고, 가장 상세하고, 그것은 튜링 기계의 상태, 전환 기능 등을 완전히 말해준다."

메모들

참조

• 데이비드 베를린스키(2000년), 알고리즘의 등장: 아이디어에서 컴퓨터로 300년 여행, 샌디에이고 하코트, ISBN 0-15-601391-6 (pbk)
• 조지 볼로스, 존 P. 버지스, 리처드 제프리(2002년), 연산성과 논리: 영국 케임브리지의 케임브리지 대학 출판부 제4판. ISBN 0-521-00758-5(pbk).
• 안드레아스 블래스와 유리 구레비치(2003), 알고리즘: 절대 정의를 위한 탐구, 이론 컴퓨터 과학을 위한 유럽 연합의 회보 81, 2003. 56개의 참고 문헌이 수록되어 있다.
• 버긴, M. 슈퍼 리커버리 알고리즘, 컴퓨터 과학의 모노그래프, 스프링거, 2005. ISBN 0-387-95569-0
• Davis, Martin (1958). Computability & Unsolvability. New York: McGraw-Hill Book Company, Inc.. 중요한 정의의 출처 및 몇 가지 재귀 기능을 위한 튜링 머신 기반 알고리즘.
• Davis, Martin (1965). The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven Press. Davis는 각 기사에 앞서 논평을 한다. 괴델, 알론조 교회, 튜링, 로서, 클레네, 에밀 포스트의 서류가 포함되어 있다.
• Dennett, Daniel (1995). Darwin's Dangerous Idea. New York: Touchstone/Simon & Schuster.
• J. Barwise, H. J. Keisler, K.에 있는 교회의 논문과 메커니즘에 대한 원리. 쿠넨, 에드스 1980년 North-Holland 출판사 클레인 심포지엄 페이지 123–148. 간디의 유명한 "4가지 컴퓨터 메커니즘 원리"에는 "원칙 4 - 국부적 인과관계의 원리"가 포함되어 있다.
• Yuri Gurevich, 순차적 추상적 상태 기계 캡쳐 순차 알고리즘, 계산 로직에 대한 ACM 트랜잭션, Vol 1, no 1, 2000년 7월, 페이지 77–111. 33개 출처의 참고 문헌을 포함한다.
• Kleene C., Stephen (1943). "Recursive Predicates and Quantifiers". Transactions of the American Mathematical Society. 54 (1): 41–73. doi:10.2307/1990131. JSTOR 1990131. The Underdicable, 페이지 255f에 재인쇄되었다. 클렌은 "일반적인 재귀"에 대한 정의를 다듬고 그의 장 "12"에서 진행하였다. 알고리즘 이론"은 "합성 I" (p. 274)을 상정하기 위한 것으로, 그는 나중에 이 논문을 반복하고 (Kleene 1952:300에서) "교회의 논문"(Kleene 1952:317) (즉, 교회 논문)이라고 명명할 것이다.
• Kleene, Stephen C. (1991) [1952]. Introduction to Metamathematics (Tenth ed.). North-Holland Publishing Company. 탁월한 — 접근성, 읽기 쉬운 — 수학적인 "창안"에 대한 참조 출처.
• Knuth, Donald E.. (1973) [1968]. The Art of Computer Programming Second Edition, Volume 1/Fundamental Algorithms (2nd ed.). Addison-Wesley Publishing Company. 크누스의 유명한 세 권의 시리즈 중 첫 번째.
• Lewis, H.R.와 Papadimitriou, C.H.의 계산 이론 요소들, 프렌티스 홀, Uppre Saddle River, N.J., 1998.
• A. A. 마르코프(1954) 알고리즘 이론. [Jacques J. Schorr-Kon 및 PST 직원이 번역함] 1954년 USSR 과학 아카데미(Academy of Science, Academy of Sciences, Academy of Science) [i.e. 예루살렘, 이스라엘 과학번역을 위한 프로그램, 1961; 미국 워싱턴주 상무부 기술서비스국에서 이용할 수 있다] 설명 444 페이지 28cm. USSR의 과학 아카데미, 대 42의 러시아어 수학 연구소 작품 번역에 t.p.가 추가되었다. 원본 제목: 테오리야 알제리 영화. [QA248.M2943 다트머스 대학 도서관. 미국 상무부, 기술 서비스부, 번호 OTS 60-51085]
• Minsky, Marvin (1967). Computation: Finite and Infinite Machines (First ed.). Prentice-Hall, Englewood Cliffs, NJ. 민스키는 알고리즘에 대한 그의 "...아이디어"를 확장한다. 효과적인 절차.5.1 장 계산성, 유효 절차 및 알고리즘의 ". 무한대의 기계.
• Hartley Rogers, Jr. (1967), 재귀적 기능과 유효 연산 이론, MIT Press (1987), Cambridge MA, ISBN 0-262-68052-1 (pbk)
• Searle, John (2002). Consciousness and Language. Cambridge UK: Cambridge University Press. ISBN 0-521-59744-7.
• 로버트 소어(1995년 8월 19일-25일, 1995년 8월 25일, 플로렌스 이탈리아), 계산성과 재귀성의 제10차 국제논리, 방법론, 철학회의의 진행에 출연) 웹 사이트 ??
• Michael Sipser, (2006), 계산 이론 소개: Second Edition, Thompson Learning, Inc.의 Thompson Course Technology 지부. 보스턴, ISBN 978-0-534-95097-2
• 이안 스튜어트 알고리즘 브리태니커 백과사전 2006
• Stone, Harold S. Introduction to Computer Organization and Data Structures (1972 ed.). McGraw-Hill, New York. Cf 특히 첫 장 제목: 알고리즘, 튜링 머신 및 프로그램. 그의 간결한 비공식적 정의: "...로봇에 의해 복종할 수 있는 모든 명령의 순서를 알고리즘이라고 한다."(4 페이지)
• Peter van Emde Boas(1990), "Machine Models and Simulation" pp 3–66, Jan van Leeuwen(1990), 이론 컴퓨터 과학 핸드북에 출연. A: 알고리즘 & 복잡성, MIT 프레스/엘세비에르, 1990, ISBN 0-444-88071-2 (A)