예를 들어, 아주 오래전... 하지만 사실 튜링 기계가 만들어지기 전에는 다양한 작업을 수행하는 기계가 만들어졌습니다. 예를 들어, 로그를 취해야 합니다. 숫자를 읽고 로그를 취하는 기계를 만들어 보겠습니다. 또는 예를 들어 두 개의 숫자를 추가해야 합니다. 여기에는 두 개의 숫자를 추가하는 기계가 있습니다. 그리고 지금도 계산기와 같은 기계가 있습니다. 그들은 무얼 할 수 있니? 더하기, 빼기, 곱하기 및 엔지니어링 - 코사인이나 사인도 사용할 수 있습니다. 이 어리석은 기계는 기록된 작업 외에는 어떤 것도 수행할 수 없고 수행할 수도 없다는 것이 밝혀졌습니다.

따라서 숫자나 기호가 아닌 알고리즘을 읽고 이를 실행하는 기계, 즉 프로그래밍 가능한 기계를 만드는 것은 매우 흥미로울 것입니다. 이것이 Turing이 한 일입니다(Turing 외에도 그러한 추상화가 많이 있다고 말씀드리겠습니다). 그리고 그는 그러한 기계의 모델을 생각해 냈습니다. 복잡한 알고리즘을 수행하기 위해 필요한 것은 캐리지, 끝없는 테이프, 테이프에 기록된 값을 변경하고 따라 이동할 수 있는 능력뿐이라는 것이 밝혀졌습니다. 이 추상화는 실제로 실제 기계로 바뀔 수 있다는 것이 밝혀졌습니다. 유일한 제한은 기계에 끝없는 테이프를 제공할 수는 없지만 매우 긴 테이프를 만들 수 있다는 것입니다.)

후퇴. 사실 이미 말했듯이 튜링 기계가 어떻게 작동하는지 말할 필요는 없습니다. 아주 쉽게 찾을 수 있습니다. 따라서 우리는 귀하가 그것이 어떻게 작동하는지 이미 알고 있다고 가정합니다.

음, Turing 기계는 몇 가지 간단한 알고리즘을 수행합니다. 이는 논쟁의 여지가 없습니다. 하지만 복잡한 것들은 어떻습니까? 그리고 예를 들어 MT를 사용하여 사이클을 어떻게 구성하시겠습니까? 아니면 분기를 알아내는 방법은 무엇입니까? MT가 루프와 분기를 수행할 수 있음을 증명하는 정리가 있다는 것이 밝혀졌습니다. 이는 매우 간단한 메커니즘을 사용하여 분기 및 루프와 같은 간단한 블록에서 프로그램을 구성하는 것이 가능하다는 것을 말해줍니다. 프로그래밍됩니다. 그리고 여기에는 이론적으로 계산할 수 없는 함수도 있으므로 해결할 수 없는 문제가 있으며 이러한 문제는 MT를 사용하여 해결할 수 없다는 설명이 있어야 합니다. 방법은 다음과 같습니다.

그러나 Turing 기계보다 더 멋진 것을 생각해낸 사람은 아무도 없으므로 현재 우리가 사용하는 모든 프로그래밍 언어는 Turing 기계 이상으로 프로그래밍할 수 없습니다. 이것이 튜링 완전성이라는 개념이 나온 곳입니다. 즉, 튜링 기계에서 실행되는 모든 알고리즘을 언어로 작성할 수 있다면 언어(또는 다른 모든 것)가 튜링 완전하다는 의미입니다. 그리고 Turing 기계 에뮬레이터를 작성하여 언어가 Turing 완전하다는 것을 증명할 수 있습니다. 이것들은 파이입니다.

수학적 관점에서 보면 그 게시물은 헛소리지만, 우리에게 Turing 기계가 필요한 이유는 분명합니다. 사실, 이 기계에 대한 알고리즘을 작성하는 것은 흥미로운 퍼즐입니다. 나는 Turing 기계에서 exp(x)를 프로그래밍한 후 알고리즘이 무엇인지 정말로 이해했다고 말하는 사람들을 믿습니다. 아직 해보지는 않았지만 흥미로운 문제네요.

튜링 기계는 다음 객체의 집합입니다.

• 1) 외부 알파벳 A=(a 0 , a 1 , …, an n );
• 2) 내부 알파벳 Q=(q 1, q 2,…, q m) - 상태 세트;
• 3) 제어 문자 세트(P, L, S)
• 4) 셀로 나누어진 양방향으로 무한한 테이프. 각 셀에는 알파벳 A에서 한 문자만 특정 순간에 쓸 수 있습니다.
• 5) 여러 상태 중 하나에 있을 수 있는 제어 장치

빈 셀의 기호는 외부 알파벳 a 0 입니다.

상태 중에는 기계가 작동하기 시작하는 초기 q1과 기계가 정지하는 최종(또는 정지 상태) q0이 있습니다.

제어 장치는 테이프를 따라 좌우로 이동할 수 있으며, 테이프의 셀에 알파벳 A를 읽고 쓸 수 있습니다. 제어 장치는 다음과 같은 형식의 명령에 따라 작동합니다.

q 나는 a j > a p X q k

기록이란 다음을 의미합니다. 제어 장치가 qi 상태에 있고 보고 있는 셀에 문자 aj가 기록되어 있으면 (1) 셀에 aj 대신 ap가 기록되고, (2) 기계가 다음 검토를 진행합니다. X = P인 경우 방금 본 것의 오른쪽 셀을 보거나 X = L인 경우 다음 왼쪽 셀을 보거나 X = C인 경우 동일한 테이프 셀을 계속 보려면 (3) 제어 장치는 상태 q로 전환됩니다. 케이.

관례적으로 기계의 작동은 주어진 순간의 상태 q와 그 순간에 표시되는 셀의 내용 a에 의해 완전히 결정되므로 가능한 각 구성 q i a j에 대해 정확히 하나의 규칙이 있습니다. 자동차가 정지한 최종 상태에만 적용되는 규칙은 없습니다. 따라서 외부 알파벳 A=(a0, a1, …, an) 및 내부 Q=(q1, q2,…, qm)을 사용하는 Turing 기계 프로그램에는 m(n+ 1)개 이하의 명령어가 포함됩니다.

알파벳 A, 알파벳 Q 또는 알파벳 A Q의 단어는 해당 알파벳의 문자 순서입니다. k 번째 구성이란 k 번째 단계 시작 시 정보가 축적된 머신 테이프의 이미지(또는 k 번째 단계 시작 시 테이프에 쓰여진 알파벳 A 단어)를 의미합니다. , 이 단계에서 어떤 셀을 보고 있는지, 자동차가 어떤 상태에 있는지를 나타냅니다. 유한한 구성만이 의미가 있습니다. 즉, 유한한 수를 제외하고는 테이프의 모든 셀이 비어 있는 경우입니다. 기계가 위치한 상태가 최종인 경우 구성을 최종이라고 합니다.

Turing 기계의 최종이 아닌 구성을 초기 구성으로 선택하면 기계의 작업은 최종 구성에 도달할 때까지 기계 프로그램에 따라 초기 구성을 순차적으로(단계적으로) 변환하는 것입니다. 이후 튜링 기계의 작업은 종료된 것으로 간주되며, 작업의 결과가 최종 구성이 달성된 것으로 간주된다.

알파벳 A (a 0) = (a 1, ..., an n)의 비어 있지 않은 단어 b가 테이프의 연속 셀에 기록되면 기계는 표준 위치에서 인식한다고 말할 수 있습니다. 다른 셀은 비어 있으며, 기계는 b라는 단어가 쓰여진 셀 중에서 가장 왼쪽에 있는 셀이나 가장 오른쪽에 있는 셀을 봅니다. 표준 위치의 단어를 인식하는 기계가 초기 상태 q 1(각각 중지 상태 q 0)에 있는 경우 표준 위치를 초기(최종)라고 합니다.

b라는 단어를 처리하면 튜링 기계가 최종 상태에 도달하면 b에 적용 가능하다고 하고, 그렇지 않으면 b에 적용할 수 없습니다(기계는 무한정 실행됩니다).

예를 살펴보겠습니다:

외부 알파벳 A = (0, 1)(여기서 0은 빈 셀의 기호)을 갖는 튜링 기계가 주어지면 내부 상태의 알파벳 Q = (q 0 , q 1 , q 2 )와 다음이 포함됩니다. 기능 다이어그램(프로그램):

q 1 0 > 1 L q 2 ;

q 1 1 > 0 С q 2 ;

q 2 0 > 0 П q 0 ;

q 2 1 > 1 С q 1 ;

이 프로그램은 테이블을 사용하여 작성할 수 있습니다.

첫 번째 단계에서는 명령이 유효합니다: q 1 0 > 1 L q 2 (제어 장치는 q1 상태에 있고 문자 0은 모니터링되는 셀에 기록되고 셀에는 0 대신 1이 기록됩니다. 헤드가 왼쪽으로 이동하면 제어 장치는 q2) 상태로 전환됩니다. 결과적으로 기계에 다음 구성이 생성됩니다.

마지막으로 q 2 0 > 0 П q 0 명령을 실행한 후 구성이 생성됩니다.

기계가 중지된 상태 q 0 에 있으므로 이 구성은 최종입니다.

따라서 원본 단어 110은 기계에 의해 단어 101로 처리됩니다.

결과적인 구성 순서는 더 짧은 방법으로 작성할 수 있습니다(모니터링 중인 셀의 내용은 시스템이 현재 있는 상태의 오른쪽에 기록됩니다).

11q 1 0 => 1q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

튜링 기계는 알파벳 AQ의 단어를 변환하는 특정 규칙(알고리즘)에 지나지 않습니다. 구성. 따라서 튜링 기계를 정의하려면 외부 및 내부 알파벳, 프로그램을 지정하고 빈 셀과 최종 상태를 나타내는 기호를 표시해야 합니다.

튜링 기계는 20세기 가장 흥미롭고 흥미로운 지적 발견 중 하나입니다. 이는 모든 컴퓨팅 작업을 구현하기에 충분히 일반적인 컴퓨팅(컴퓨터 및 디지털)의 간단하고 유용한 추상 모델입니다. 간단한 설명과 수학적 분석 덕분에 이론적인 컴퓨터 과학의 기초를 형성합니다. 이 연구는 메인프레임 컴퓨터에서 해결할 수 없는 일부 컴퓨팅 문제가 있다는 이해를 포함하여 디지털 컴퓨팅과 미적분학에 대한 더 큰 이해로 이어졌습니다.

앨런 튜링(Alan Turing)은 컴퓨터와 동일한 기본 기능을 갖춘 가장 원시적인 기계 장치 모델을 설명하려고 했습니다. 튜링은 1936년 런던 수학학회 회보(Proceedings of the London Mathematical Society)에 게재된 "해결 가능성 문제에 적용하여 계산 가능한 숫자에 관하여"라는 논문에서 기계에 대해 처음 설명했습니다.

튜링 머신은 읽기/쓰기 헤드(또는 "스캐너")와 이를 통과하는 종이 테이프로 구성된 컴퓨팅 장치입니다. 테이프는 사각형으로 나뉘며 각 사각형에는 "0" 또는 "1"이라는 단일 기호가 표시됩니다. 메커니즘의 목적은 입력과 출력을 위한 수단이자 중간 계산 단계의 결과를 저장하기 위한 작업 메모리 역할을 한다는 것입니다. 장치는 무엇으로 구성됩니까? 각 기계는 두 가지 구성 요소로 구성됩니다. 무제한 테이프. 양방향으로 무한하며 셀로 나누어져 있습니다. 자동 - 제어되는 프로그램, 데이터 읽기 및 쓰기용 스캐너 헤드. 특정 순간에 여러 상태 중 하나에 있을 수 있습니다.

각 기계는 두 개의 유한한 데이터 계열, 즉 수신 기호 A = (a0, a1, ..., am)의 알파벳과 상태 Q = (q0, q1, ..., qp)의 알파벳을 연결합니다. 상태 q0을 수동이라고 합니다. 장치에 부딪히면 작업이 종료되는 것으로 믿어집니다. 상태 q1을 초기라고 합니다. 기계는 시작하는 동안 계산을 시작합니다. 입력 단어는 테이프에 각 위치에 한 줄씩 문자가 있습니다. 양쪽에는 빈 셀만 있습니다.

메커니즘 작동 방식

튜링 기계는 컴퓨팅 장치와 근본적인 차이점이 있습니다. 저장 장치에는 끝이 없는 테이프가 있는 반면, 디지털 장치에서는 이러한 장치에 특정 길이의 스트립이 있습니다. 각 작업 클래스는 단 하나의 Turing 기계로 해결됩니다. 다른 유형의 문제에는 새로운 알고리즘을 작성해야 합니다. 한 상태에 있는 제어 장치는 벨트를 따라 어느 방향으로든 움직일 수 있습니다. 유한한 알파벳 문자를 셀에 쓰고 읽습니다. 이동하는 동안 빈 요소가 할당되어 입력 데이터가 없는 위치를 채웁니다. Turing 기계 알고리즘은 제어 장치의 전환 규칙을 결정합니다. 읽기-쓰기 헤드에 다음 매개변수를 설정합니다. 셀에 새 문자 쓰기, 새 상태로 전환, 테이프를 따라 왼쪽 또는 오른쪽으로 이동.

메커니즘 속성

다른 컴퓨팅 시스템과 마찬가지로 튜링 머신에는 고유한 기능이 있으며 이는 알고리즘의 속성인 이산성과 유사합니다. 디지털 머신은 이전 단계가 완료된 후에야 다음 단계 n+1로 이동합니다. 실행되는 각 단계는 n+1이 무엇인지 할당합니다. 명쾌함. 장치는 하나의 셀에 대해 하나의 작업만 수행합니다. 알파벳 문자를 입력하고 왼쪽 또는 오른쪽으로 한 번 움직입니다. 결정론. 메커니즘의 각 위치는 주어진 계획을 실행하기 위한 단일 옵션에 해당하며 각 단계에서 작업과 실행 순서는 명확합니다. 생산력. 각 단계의 정확한 결과는 Turing 기계에 의해 결정됩니다. 프로그램은 알고리즘을 실행하고 유한한 수의 단계를 거쳐 상태 q0으로 이동합니다. 대량 문자. 각 장치는 알파벳에 포함된 유효한 단어에 대해 정의됩니다. 튜링 기계 기능 알고리즘을 해결하려면 종종 기능 구현이 필요합니다. 계산을 위해 체인을 작성할 가능성에 따라 함수를 알고리즘적으로 해결 가능하거나 결정 불가능하다고 합니다. 자연수 또는 유리수 세트, 기계에 대한 유한 알파벳 N의 단어, 세트 B의 시퀀스가 ​​​​고려됩니다. 이진 코드 알파벳 B = (0.1) 내의 단어입니다. 또한 계산 결과는 알고리즘이 정지될 때 발생하는 "정의되지 않은" 값을 고려합니다. 기능을 구현하기 위해서는 최종 알파벳에 형식언어를 갖는 것이 중요하며, 정확한 설명을 인식하는 문제를 해결해야 한다.-

장치 프로그램

Turing 메커니즘의 프로그램은 첫 번째 행과 열에 외부 알파벳 기호와 자동 장치의 가능한 내부 상태 값(내부 알파벳)이 포함된 테이블 형식으로 구성됩니다. 표 형식 데이터는 Turing 기계가 허용하는 명령입니다. 문제 해결은 다음과 같은 방식으로 이루어집니다. 현재 위치한 셀의 헤드가 읽은 문자와 기계 헤드의 내부 상태에 따라 실행해야 할 명령이 결정됩니다. 이 특정 명령은 표에 있는 외부 및 내부 알파벳 기호의 교차점에 있습니다.

계산을 위한 구성 요소

하나의 특정 문제를 해결하기 위해 Turing 기계를 구축하려면 이에 대한 다음 매개변수를 정의해야 합니다. 외부 알파벳. 이것은 기호 A로 표시되는 특정 유한 기호 집합으로, 그 구성 요소를 문자라고 합니다. 그 중 하나(a0)는 비어 있어야 합니다. 예를 들어, 이진수로 작동하는 Turing 장치의 알파벳은 다음과 같습니다: A = (0, 1, a0). 테이프에 기록된 일련의 문자와 기호를 단어라고 합니다. 자동 장치는 사람의 개입 없이 작동하는 장치입니다. 튜링 기계에는 문제를 해결하기 위한 여러 가지 상태가 있으며, 특정 조건이 발생하면 한 위치에서 다른 위치로 이동합니다. 이러한 캐리지 상태의 집합은 내부 알파벳입니다. 그는 가지고있다 문자 지정 Q=(q1, q2...) 형식입니다. 이러한 위치 중 하나인 q1은 초기 위치, 즉 프로그램을 시작하는 위치여야 합니다. 하나 더 필요한 요소상태 q0은 최종 상태, 즉 프로그램을 종료하고 장치를 정지 위치로 이동시키는 상태입니다.

전환 테이블.

이 구성 요소는 기계의 현재 상태와 읽기 기호 값에 따라 장치 캐리지의 동작에 대한 알고리즘입니다.-

기계의 알고리즘

작동 중에 Turing 장치의 캐리지는 각 단계에서 다음 작업의 순서를 수행하는 프로그램에 의해 제어됩니다. 빈 위치를 포함하여 외부 알파벳 기호를 위치에 쓰고 원래 있던 요소를 대체합니다. 빈 것을 포함하여 그것. 한 셀 단계를 왼쪽이나 오른쪽으로 이동합니다. 내부 상태를 변경합니다. 따라서 각 문자 또는 위치 쌍에 대한 프로그램을 작성할 때 세 가지 매개변수를 정확하게 설명해야 합니다. ai - 선택한 알파벳 A의 요소, 캐리지 이동 방향(왼쪽으로 "←", 왼쪽으로 "→") 오른쪽, "점" - 이동 없음) 및 qk - 장치의 새 상태 예를 들어, 명령 1 "←" q2는 "문자를 1로 바꾸고, 캐리지 헤드를 왼쪽으로 한 셀 단계 이동한 다음"을 의미합니다. 상태 q2로의 전환”.

우리는 일상, 수학 등 다양한 복잡성의 문제를 해결하는 경우가 많습니다. 일부는 해결하기 쉽고, 일부는 많은 생각이 필요하며, 일부는 결코 해결책을 찾지 못합니다.

일반적으로 문제(문제가 있는 경우)를 해결하는 방법은 유한한 수의 기본 동작을 사용하여 설명할 수 있습니다.

예를 들어, 2차 방정식을 풀면 다음과 같습니다.

1. 방정식을 표준 형식 \(a x^2 + b x + c = 0\)으로 가져옵니다.
2. \(a=0\) 인 경우 다음은 일차 방정식\(x=\frac(-c)(b)\) 솔루션을 사용합니다. 문제가 해결되었습니다. 그렇지 않으면 3단계로 이동하세요.
3. 판별식 \(D=b^2-4 a c\) 계산
4. 방정식의 해 계산 \(x_(1,2) = \frac(-b\pm\sqrt(D))(2a)\). 문제가 해결되었습니다.

다음과 같은 직관적인 알고리즘 개념을 소개할 수 있습니다.

알고리즘은 초기 데이터 세트에 대해 유한한 수의 작업으로 문제 해결 결과를 얻기 위해 수행자의 작업 순서를 설명하는 지침 세트입니다.

물론 이것은 엄격한 정의는 아니지만 알고리즘 개념의 본질을 설명합니다.

알고리즘은 특정 기반으로 컴파일됩니다. 수행자, 따라서 연주자가 이해할 수 있는 언어로 편집되어야 합니다.

알고리즘의 실행자는 사람일 수도 있고, 컴퓨터일 수도 있고, 베틀과 같은 다른 기계일 수도 있습니다.

알고리즘의 다음 속성이 강조 표시됩니다.

알고리즘의 불연속성은 명확하게 정의된 별도의 특정 단계(작업) 순서여야 합니다. 이러한 각 작업은 시간적으로 유한해야 합니다. 알고리즘의 각 단계에서의 결정성은 시스템의 현재 상태에 따라 고유하게 결정됩니다. 결과적으로 동일한 초기 데이터에 대해 알고리즘은 실행 횟수에 관계없이 매번 동일한 결과를 반환합니다. 이해성 알고리즘은 수행자가 이해할 수 있는 언어로 공식화되어야 합니다. 만약에 우리 얘기 중이야컴퓨터에 대해 알고리즘은 컴퓨터에 알려져 있고 그 결과가 엄격하게 정의된 명령만 사용해야 합니다. 유한성 알고리즘은 유한한 수의 단계를 거쳐 완료되어야 합니다. 대규모 알고리즘은 다양한 입력 데이터 세트에 적용 가능해야 합니다. 즉, 알고리즘은 문제를 해결할 수 있어야 합니다. 수업작업. 2차 방정식 예로 돌아가서, 알고리즘은 다음을 푸는 데 적합합니다. 모든 사람단지 하나 또는 몇 개가 아닌 이차 방정식. 효율성 알고리즘은 특정 결과로 끝나야 합니다. 문제를 해결하거나 해결책이 부족한 것을 찾아낸다고 가정해 보겠습니다. 알고리즘이 결과로 이어지지 않는다면 그것이 왜 필요한지 전혀 불분명합니다.

문제를 해결하는 모든 방법이 알고리즘인 것은 아닙니다. 알고리즘이 선택의 여지가 없음을 의미한다고 가정 해 봅시다. 예를 들어, 대부분의 요리 조리법"맛에 소금을 추가하세요"와 같은 문구를 사용하기 때문에 알고리즘이 아닙니다. 결과적으로 결정론의 요구 사항이 위반됩니다.

솔루션이 있는 모든 문제에 솔루션 알고리즘도 있는 것은 아닙니다. 예를 들어, 이미지 인식 문제는 여전히 대부분 해결되지 않은 상태로 남아 있으며, 엄격한 알고리즘의 도움을 통해서도 확실히 해결되지 않습니다. 그러나 신경망을 사용하면 꽤 좋은 결과를 얻을 수 있습니다.

일반적으로 알고리즘에 대한 세트가 있습니다. 받아들일 수 있는입력 데이터. 저녁 식사 요리에 방정식 풀이 알고리즘을 적용하거나 그 반대로 적용하는 것은 이상할 것입니다.

또한, 수행자의 가능한 행동 범위도 제한됩니다. 왜냐하면 어떤 행동이 허용된다면 그 중에는 "허용할 수 없는" 행동도 있어야 하기 때문입니다.

알고리즘의 엄격한 정의

위에 주어진 알고리즘의 정의는 엄격하지 않습니다. 이로 인해 몇 가지 어려움이 발생합니다. 특히, 이러한 정의를 사용하면 특정 유형의 문제가 알고리즘을 사용하여 해결 가능한지 여부를 엄격하게 증명하는 것이 불가능합니다.

수업이 있는 것으로 밝혀졌습니다 알고리즘적으로 해결 불가능한 문제– 솔루션 알고리즘을 생성하는 것이 불가능한 문제. 그러나 알고리즘의 결정 불가능성을 엄격하게 증명하려면 먼저 알고리즘에 대한 엄격한 정의가 필요합니다.

20세기 20~30년대에는 다양한 수학자, 특히 Alan Turing, Emil Leon Post, Andrei Andreevich Markov, Andrei Nikolaevich Kolmogorov, Alonzo Church 등이 알고리즘의 엄격한 정의 문제를 연구했습니다. 그들의 작업은 궁극적으로 알고리즘 이론, 계산 가능성 이론, 미적분학에 대한 다양한 접근 방식, 그리고 일반적인 프로그래밍의 출현과 발전으로 이어졌습니다. 그들의 작업 결과 중 하나는 서로 다른 방식으로 도입되었지만 서로 동등한 알고리즘에 대한 몇 가지 엄격한 정의의 출현이었습니다.

Turing의 정의를 자세히 살펴보고 그에 상응하는 Post, Church 및 Markov 정의의 표면을 긁어보겠습니다.

튜링 머신

알고리즘의 공식적인 정의를 소개하기 위해 Turing은 Turing 기계 또는 간단히 Turing 기계라고 불리는 추상 컴퓨팅 기계를 발명하고 설명했습니다.

앨런 튜링(1912-1954)

영국의 수학자, 논리학자, 암호학자, 아마도 세계 최초의 "해커"는 컴퓨터 과학과 인공 지능 이론의 기원에 서 있었습니다. 그는 제2차 세계대전에서 연합군의 승리에 크게 기여했다.

튜링 기계의 입력 데이터는 다음과 같습니다. 단어, 특정을 사용하여 컴파일 알파벳, 즉 세트 문자.

튜링 기계의 출력도 단어입니다.

알고리즘이 적용된 단어를 이라고 합니다. 입력. 그 일의 결과로 나온 말은 쉬는 날에는.

알고리즘이 적용되는 단어 집합을 이라고 합니다. 알고리즘의 적용 범위.

엄밀히 말하면, 어떤 객체가 어떤 알파벳으로 구성된 단어의 형태로 표현될 수 있다는 것을 증명하는 것은 불가능합니다. 이를 위해서는 객체에 대한 엄격한 정의가 필요합니다. 그러나 객체에 작동하는 무작위로 선택된 알고리즘은 단어에 작동하도록 변환될 수 있지만 알고리즘의 본질은 변하지 않는다는 것을 확인할 수 있습니다.

튜링 기계에 대한 설명

튜링 기계는 양방향으로 무제한으로 셀로 나누어진 테이프와 제어 장치(또는 제어 장치라고도 함)로 구성됩니다. 읽기-쓰기 헤드또는 단순히 기계), 여러 상태 중 하나에 속할 수 있습니다. 제어 장치의 가능한 상태 수는 유한하며 정확하게 지정됩니다.

제어 장치는 테이프를 따라 왼쪽과 오른쪽으로 이동할 수 있으며 일부 유한 알파벳의 문자를 셀에 읽고 쓸 수 있습니다. \(a_0\) 또는 \(\Lambda\) 로 지정된 특수 빈 문자가 할당되어 입력 데이터가 기록되는 셀(마지막 번호)을 제외하고 테이프의 모든 셀을 채웁니다.

제어 장치는 주어진 Turing 기계에 의해 구현된 알고리즘을 나타내는 전환 규칙에 따라 작동합니다. 각 전이 규칙은 현재 상태와 현재 셀에서 관찰되는 기호에 따라 이 셀에 새 기호를 쓰고 새 상태로 이동하고 한 셀을 왼쪽이나 오른쪽으로 이동하도록 기계에 지시합니다. 튜링 기계의 일부 상태는 터미널로 표시될 수 있으며, 이러한 상태로의 전환은 작업이 종료되고 알고리즘이 중지됨을 의미합니다.

튜링 기계는 추상적인 개념이지만 (비록 유한한 테이프임에도 불구하고) 그러한 기계를 상상하는 것은 매우 쉽습니다. 심지어 이런 종류의 데모 기계도 있습니다.

튜링 기계의 알고리즘을 표 형식으로 표현하는 것이 편리합니다. 표의 열은 테이프의 현재(관찰된) 기호에 해당하고, 행은 기계의 현재 상태에 해당하며, 셀은 기록을 나타냅니다. 기계가 실행해야 하는 명령.

명령은 다음과 같은 구조를 가질 수 있습니다.

\[ a_k \left\lbrace \begin(행렬) L \\ N \\ P \end(행렬)\right\rbrace q_m \]

먼저 현재 셀 \(a_k\)에 기록되어야 하는 알파벳 기호가 오고, 그 다음 기계가 왼쪽(L), 오른쪽(R) 또는 아무데도(제자리에 머물지, N) 이동하는 것이 표시됩니다. 마지막에는 오토마톤 \(q_m\)이 가야 할 새로운 상태가 표시됩니다.

테이블 셀은 현재 기호 \(a_i\) 와 기계의 현재 상태 \(q_j\) 에 의해 명확하게 결정됩니다.

작업이 시작될 때 Turing 기계가 초기 상태, \(q_1\) 로 표시되며, 정지 상태\(q_0\) 알고리즘이 완료되고 기계가 중지됩니다.

예

입력 단어에 추가할 튜링 기계용 알고리즘을 만들어 보겠습니다. 십진수, 1.

그러면 알고리즘을 설명적으로 다음과 같이 공식화할 수 있습니다.

1. 오른쪽으로 이동하여 입력 단어의 시작 부분을 찾습니다.
2. 입력된 단어의 끝을 찾으려면 오른쪽으로 이동하세요.
3. 입력 단어의 현재 숫자에 1을 더합니다. 0~8 사이의 숫자가 있으면 종료합니다. 그렇지 않으면 0을 쓰고 왼쪽으로 이동한 후 3단계로 돌아갑니다.

이 알고리즘을 테이블 형식으로 작성해 보겠습니다. 알파벳은 0부터 9까지의 숫자와 "공백 문자" \(\Lambda\) 로 구성됩니다. 또한 알고리즘 설명 단계에 해당하는 정지 상태를 계산하는 기계의 4가지 상태가 필요합니다.

초기 상태 \(1\)은 입력 단어의 시작 부분에 대한 검색이고, \(2\)는 입력 단어의 끝 부분에 대한 검색이고, \(3\)은 1의 추가라는 점에 동의합시다.

\(_(q_j)\백슬래시^(a_i)\)	Λ	0	1	2	3	4	5	6	7	8	9
1	ΛП1	0H2	상반기	하반기	3H2	4H2	5N2	6N2	7N2	8N2	9N2
2	ΛЛ3	0P2	1P2	2P2	3P2	4P2	5P2	6P2	7P2	8P2	9P2
3	1Н0	1Н0	2Н0	3Н0	4Н0	5Н0	6Н0	7Н0	8Н0	9Н0	0L3

예제를 사용하여 이 알고리즘이 어떻게 작동하는지 살펴보겠습니다. 첫 번째 줄은 테이프에 해당하고 두 번째 줄은 기계의 위치와 현재 상태를 나타냅니다.

	1	9	9
1

상태 1에서는 머신이 빈 셀 위에 있습니다. 테이블 "ΛП1"의 해당 명령, 즉 셀을 비워두고 오른쪽으로 이동하여 상태 1을 유지합니다.

	1	9	9
	1

이제 기계는 값 "1"을 관찰합니다. 해당 명령은 "1H2"입니다. 즉, 셀 "1"에 그대로 두고 이동하지 않고 상태 "2"로 이동합니다.

	1	9	9
	2

상태 "2"에서 기계는 "1" 값을 관찰합니다. 해당 명령은 "1P2"입니다. 즉, "1"을 그대로 두고 오른쪽으로 이동하여 "2" 상태를 유지합니다.

상황은 반복됩니다.

이제 상태 3에서 기호 "9"를 관찰하면 기계는 "0L3" 명령을 실행합니다.

	1	9	0
		3

상황은 반복됩니다.

상태 "0" – 정지 상태. 알고리즘이 완성되었습니다.

공식적인 설명

수학적으로 튜링 기계는 다음과 같이 설명할 수 있습니다.

튜링 머신(MT)

이것은 다음과 같은 형태의 시스템이다. \(\(A, a_0, Q, q_1, q_0, T, \tau\)\), 어디

• \(A\) – MT 알파벳의 유한한 기호 집합
• \(a_0 \in A\) – 빈 알파벳 문자
• \(Q\) – MT 상태의 유한 집합
• \(q_1 \in Q\) – MT의 초기 상태
• \(q_0 \in Q\) – MT의 최종 상태(정지 상태)
• \(T = \(L, P, N\)\) – 교대 근무 세트 MT
• \(\tau\) – MT 프로그램, 즉 디스플레이를 지정하는 기능 \(\tau: A\times Q\backslash \(q_0\) \rightarrow A\times T \times Q\)

알고리즘 이론의 핵심은 튜링의 논문.

느슨하게 공식화하면 Turing의 논제는 다음과 같이 기술됩니다.

튜링의 논문: 알고리즘으로 해결할 수 있는 모든 문제에는 이 문제를 해결하는 튜링 기계가 있습니다. 그렇지 않으면 모든 알고리즘에 대해 동등한 Turing 기계가 있습니다.

Turing의 논문을 통해 우리는 매우 간단한 수학적 장치를 사용하여 알고리즘에 대해 이야기할 수 있습니다. 게다가 튜링 기계 자체는 범용 액추에이터, 그리고 그러한 상상의 기계를 만들 수 있다는 가능성 자체가 유니버설 컴퓨팅 기술의 창조를 이야기하는 이유가 되었습니다.

알고리즘의 대체 정의

튜링 기계 외에도 튜링의 정의와 동등한 몇 가지 독립적인 정의가 있습니다.

특히 Post Machine, Church의 람다 계산 및 일반 Markov 알고리즘을 통한 결정입니다.

이러한 방법을 고려해 봅시다.

포스트의 기계

튜링이 있은 지 1년 후, 미국 수학자 에밀 레온 포스트(Emil Leon Post)는 튜링 기계에 비해 다소 단순화된 또 다른 추상적 범용 컴퓨팅 기계를 독립적으로 제안했습니다.

포스트의 기계는 두 자리 알파벳으로 동작하며, 기계의 내부 상태는 다음과 같이 대체된다. 프로그램 라인.

다른 측면에서 포스트 머신은 튜링 머신과 유사합니다. 자동 장치가 있고 셀이 있는 무한한 테이프가 있습니다.

포스트 머신은 다음 명령을 실행할 수 있습니다.

1. 1을 쓰고 프로그램의 i번째 줄로 이동합니다.
2. 0을 쓰면 프로그램의 i번째 줄로 이동합니다.
3. 왼쪽으로 Shift, 프로그램의 i번째 줄로 이동
4. 오른쪽으로 Shift, 프로그램의 i번째 줄로 이동
5. 조건부 점프: 관찰된 셀에 0이 있으면 프로그램의 i번째 라인으로 이동하고, 그렇지 않으면 프로그램의 j번째 라인으로 이동합니다.
6. 멈추다.

또한 Post의 컴퓨터에는 몇 가지 금지된 명령이 있습니다.

1. 이미 1이 있으면 셀 1에 씁니다.
2. 이미 0이 있는 셀 0에 씁니다.

이러한 이벤트는 비정상적인 종료로 이어집니다.

포스트 머신용 프로그램을 작성하려면 다음 표기법을 사용할 수 있습니다.

1. ∨ i – 1을 쓰고, 프로그램의 i번째 줄로 이동
2. × i – 0을 쓰고, 프로그램의 i번째 줄로 이동
3. ← i – 왼쪽으로 이동, 프로그램의 i번째 줄로 이동
4. → i – 오른쪽으로 이동, 프로그램의 i번째 줄로 이동
5. ? 나; 제이 - 조건부 점프: 관찰된 셀에 0이 있으면 프로그램의 i번째 라인으로 이동하고, 그렇지 않으면 프로그램의 j번째 라인으로 이동합니다.
6. ! - 멈추다.

예제 프로그램:

1. → 2 2. ? 1; 3 3. × 4 4. ← 5 5. !

이 프로그램은 기계의 초기 위치 오른쪽에 있는 첫 번째 표시(1)를 지우고 왼쪽 셀에서 기계를 정지시킵니다.

대체로 포스트의 차가 전신이다. 피할 수 없는프로그래밍 언어(예: C, Fortran 등)

포스트 머신은 튜링 머신과 동일합니다. 즉, Turing 기계에 대한 모든 프로그램에 대해 Post 기계에 대한 동등한 프로그램을 작성할 수 있으며 그 반대의 경우도 마찬가지입니다.

이 동등성의 한 가지 중요한 결과는 다음과 같습니다. 모든 알파벳은 이진 코드로 축소될 수 있습니다..

Turing의 논문과 비슷한 Post의 논문도 있습니다.

Post의 논문에서는 모든 알고리즘을 Post 머신으로 상상해 보겠습니다.

일반 마르코프 알고리즘

Markov 정규 알고리즘은 다양한 알파벳의 단어에 적용되도록 설계되었습니다.

일반 알고리즘의 정의는 두 부분으로 구성됩니다.

1. 알파벳연산
2. 계획연산

알고리즘 자체가 적용됩니다. 단어, 즉 일련의 문자 알파벳.

정규 알고리즘의 체계는 소위 유한 순서 집합입니다. 대체 공식, 각각은 다음과 같을 수 있습니다. 단순한또는 결정적인. 단순 대체 공식은 \(L\to D\) 형식의 표현입니다. 여기서 \(L\) 및 \(D\)는 알고리즘의 알파벳으로 구성된 두 개의 임의 단어입니다(각각 왼쪽과 오른쪽이라고 함). 대체 공식의). 마찬가지로, 최종 대체 공식은 \(L\to\cdot D\) 형식의 표현식입니다. 여기서 \(L\) 및 \(D\)는 알고리즘의 알파벳으로 구성된 두 개의 임의 단어입니다.

보조 기호 \(\to\) 및 \(\to\cdot\)는 알고리즘 알파벳에 속하지 않는 것으로 가정됩니다.

임의의 단어 \(V\)에 일반 알고리즘을 적용하는 과정은 다음과 같은 일련의 동작을 따릅니다.

1. \(V"\)를 알고리즘의 이전 단계에서 얻은 단어(또는 현재 단계가 첫 번째 단계인 경우 원래 단어)로 둡니다.
2. 대체 공식 중에 왼쪽이 \(V"\) 에 포함될 사람이 없으면 알고리즘 작업이 완료된 것으로 간주되며 이 작업의 결과는 단어 \(V"\) 입니다.
3. 그렇지 않은 경우에는 \(V"\) 에 왼쪽이 포함된 치환식 중에서 가장 첫 번째 것을 선택한다.
4. \(RLS\)(여기서 \(R\)은 접두사이고 \(L\)은 접미사) 형식의 \(V"\) 단어의 가능한 모든 표현 중에서 \(R\ )는 가장 짧은 이며 그 후에 대체 \(V"=RDS\)가 수행됩니다.
5. 대체 공식이 유한한 경우 알고리즘은 결과 \(V"\)로 완료됩니다. 그렇지 않으면 1단계(다음 단계)로 이동합니다.

모든 일반 알고리즘은 일부 Turing 시스템과 동일하며 그 반대도 마찬가지입니다. 모든 Turing 시스템은 일부 일반 알고리즘과 동일합니다.

일반 알고리즘에 대한 Turing의 논문과 유사한 것은 일반적으로 다음과 같습니다. 정규화의 원리.

예

이 알고리즘은 이진수를 "단일" 숫자로 변환합니다(여기서 음수가 아닌 정수 N의 표현은 N개 막대의 문자열임). 예를 들어, 이진수 101은 5개의 막대기로 변환됩니다: |||||.

알파벳: ( 0, 1, | ) 규칙:

1. 1 → 0|
2. |0 → 0||
3. 0 → (빈 문자열)

소스 라인: 101 실행:

1. 0|00|
2. 00||0|
3. 00|0|||
4. 000|||||
5. 00|||||
6. 0|||||
7. |||||

재귀 함수

튜링 기계와 동등한 시스템은 수학적 함수를 기반으로 구성될 수 있습니다. 이를 위해서는 다음과 같은 함수 클래스를 도입해야 합니다:

• 원시 재귀 함수
• 일반 재귀 함수
• 부분 재귀 함수

후자 클래스는 튜링 계산 가능 함수(즉, 튜링 기계에 대한 알고리즘을 구성할 수 있는 계산을 위한 함수) 클래스와 일치합니다.

재귀 함수를 통해 알고리즘을 정의하는 것은 본질적으로 람다 계산의 기초이며 접근 방식은 이를 기반으로 합니다. 함수형 프로그래밍.

기본적으로 재귀적인 함수

원시 재귀 함수 클래스에는 다음이 포함됩니다. 기본 기능연산자를 사용하여 기본 함수에서 얻은 모든 함수 대체품그리고 원시 재귀.

기본 기능은 다음과 같습니다:

• null 함수 \(O()=0\) 은 항상 \(0\) 을 반환하는 인수가 없는 함수입니다.
• 함축 함수 \(S(x)=x+1\)는 임의의 자연수 \(x\)를 할당하는 함수입니다. 다음 번호\(x+1\)
• 기능 \(I_n^m(x_1,\ldots,x_n) = x_m\), 여기서 \(0

클래스의 나머지 함수를 구성하려면 다음 연산자가 사용됩니다.

• 대체. \(m\)개의 변수로 구성된 함수 \(f\)와 \(n\)개의 변수로 구성된 \(m\) 함수 \(g_1,\ldots,g_m\)에 대해 \(g_k\)를 대체한 결과 \(f\)에 대한 함수는 다음과 같습니다. \(h(x_1,\ldots,x_n) = f(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n))\)\(n\) 변수에 대해.
• 원시 재귀. \(f(x_1,\ldots,x_n)\)는 \(n\) 변수의 함수이고, \(g(x_1,\ldots,x_(n+2))\)는 \( n+ 2\) 변수. 그런 다음 기본 재귀 연산자를 \(f\) 및 \(g\) 함수에 적용한 결과는 다음 형식의 \(n+1\) 변수의 함수 \(h\)입니다. \[ h(x_1,\ldots,x_n,0) = f(x_1,\ldots,x_n) \] \[ h(x_1,\ldots,x_n,y+1) = g(x_1,\ldots,x_n, y, h(x_1,\ldots,x_n,y)) \]

부분 재귀 함수

부분 재귀 함수 클래스에는 기본 재귀 함수와 더불어 인수 최소화 연산자를 사용하여 기본 재귀 함수에서 얻은 모든 함수가 포함됩니다.

인수 최소화 연산자

\(f\)를 \(n\) 변수 \(x_i \in \mathbb(N)\)의 함수로 둡니다. 그런 다음 함수 \(f\)에 인수 최소화 연산자를 적용한 결과는 다음과 같이 정의된 \(n-1\) 인수의 함수 \(h\)입니다.

\[ h(x_1,\ldots,x_(n-1)) = \min y, \]어디 \ 즉, \(h\)는 \(f\)의 값이 0인 함수 \(f\)의 마지막 인수의 최소값을 반환합니다.

원시 재귀 함수는 항상 계산 가능하지만 부분 재귀 함수는 일부 인수 값에 대해 정의되지 않을 수 있습니다.

보다 엄밀히 말하면 부분 재귀 함수는 인수의 가능한 값 중 일부에만 정의되므로 "부분 정의 재귀 함수"라고 불러야 합니다.

일반 재귀 함수

일반적으로 재귀 함수는 모든 인수 값에 대해 정의된 모든 부분 재귀 함수의 하위 클래스입니다. 주어진 부분 재귀 함수가 일반적으로 재귀적인지 여부를 결정하는 작업은 다음과 같습니다. 알고리즘적으로 결정 불가능. 이는 계산 가능성 이론과 정지 문제라는 주제로 이어집니다.

계산 가능성 이론과 정지 문제

우리의 상상력은 일반적으로 해결 불가능한 문제, 즉 알고리즘을 만드는 것이 불가능한 문제의 존재를 허용합니다.

계산 가능성 이론은 그러한 문제를 연구합니다.

알고리즘적으로 해결 불가능한 문제의 예는 다음과 같습니다. 종료 문제그리고 부화 가능성 인식 문제. 좀 더 자세히 살펴보겠습니다.

문제 중지 알고리즘 A와 입력 데이터 \(x\)에 대한 설명이 주어지면 알고리즘 \(A\)가 입력 데이터 \(x\)에서 중지되는지 여부를 알아내는 것이 필요합니다.

중지 문제는 알고리즘적으로 해결할 수 없습니다. 그것을 증명해 봅시다.

\(\델타\)

정지 문제를 해결하는 보편적인 알고리즘이 있다고 가정해 보겠습니다. 그러면 알고리즘 설명 텍스트를 처리하는 알고리즘 클래스를 고려해 보겠습니다.

중지 문제를 해결하기 위한 보편적인 알고리즘이 존재하기 때문에 언급된 클래스의 알고리즘이 자체 텍스트에서 중지할지 여부를 결정하는 알고리즘이 있습니다. 이러한 알고리즘 \(B\) 을 표시해 보겠습니다.

자체 텍스트를 처리하는 알고리즘 \(A\)의 텍스트를 입력 데이터로 사용하는 알고리즘 \(C\)를 구축해 보겠습니다.

1. \(A\) 에 대해 알고리즘 \(B\) 를 실행합니다.
2. \(B\) 알고리즘이 \(A\)가 해당 텍스트에서 중지한다고 결정한 경우 1단계로 이동합니다. 그렇지 않으면 3단계로 이동합니다.
3. 알고리즘 \(C\) 의 끝입니다.

\(C\) 알고리즘을 \(C\) 알고리즘에 적용하려고 하면 명백한 모순에 직면하게 됩니다. 즉, \(C\)가 자체 텍스트에서 멈추면 멈출 수 없으며 그 반대의 경우도 마찬가지입니다. 따라서 \(B\) 알고리즘은 없습니다. \(\아님 \델타\)

중지 문제의 보다 일반적인 공식화는 연역성을 결정하는 문제입니다.

부화 가능성 인식 문제

특정 알파벳, 이 알파벳의 단어(공식) 및 이 알파벳의 단어에 대한 형식 변환 시스템을 정의합니다(즉, 논리 계산이 구성되었습니다).

임의의 두 단어 \(R\)과 \(S\)에 대해 주어진 논리 계산 내에서 \(R\)에서 \(S\)로 이어지는 연역 체인이 있습니까?

1936년에 Alonzo Church는 Church의 정리를 증명했습니다.

Church's Theorem 파생 가능성 인식 문제는 알고리즘적으로 결정 불가능합니다.

Church는 그것을 증명하기 위해 람다 미적분 형식을 사용했습니다. 1937년에 튜링은 튜링 기계 형식론을 사용하여 동일한 정리를 독립적으로 증명했습니다.

알고리즘의 모든 정의는 서로 동일하므로 특정 알고리즘 정의와 연관되지 않고 다음 개념으로 작동하는 개념 체계가 있습니다. 계산 가능한 함수.

계산 가능한 함수는 알고리즘을 작성할 수 있는 함수입니다.

입력 데이터와 출력 데이터 간의 관계를 알고리즘을 사용하여 설명할 수 없는 문제가 있습니다. 그러한 기능은 계산할 수 없는.

계산할 수 없는 함수의 예

다음과 같이 \(\forall n \in \mathbb(N)\)에 대해 정의된 함수 \(h(n)\)를 사용합니다.

\[ h(n) = \begin(cases) 1, & \text(if in )\pi\text( 정확히 )n\text( 9-k) \\ 0, & \text(그렇지 않은 경우 ) \end(건수) \]

이 함수에 대해 \(1\) 값을 얻을 수 있지만, \(0\) 값을 얻으려면 유한 시간에서는 분명히 불가능한 숫자 \(\pi\)의 무한 소수점 확장을 확인해야 합니다. . 따라서 이 함수는 계산할 수 없습니다.

1920년대 이후의 표현 계산기작업을 수행하는 모든 기계를 말합니다. 인간-컴퓨터특히 교회-튜링 이론의 효율적인 방법에 따라 개발된 것입니다. 이 논문은 다음과 같이 공식화됩니다. “모든 알고리즘은 해당 튜링 기계 또는 부분 재귀 정의의 형태로 지정될 수 있으며, 계산 가능한 함수 클래스는 부분 재귀 함수 클래스 및 튜링 기계에서 계산 가능한 함수 클래스와 일치합니다. .” 또 다른 방식으로 Church-Turing 논문은 전자 컴퓨터와 같은 기계적 컴퓨팅 장치의 본질에 대한 가설로 정의됩니다. 시간과 저장 공간이 충분하다면 컴퓨터에서 가능한 모든 계산을 수행할 수 있습니다.

무한대 계산을 수행하는 메커니즘은 아날로그 유형으로 알려졌습니다. 이러한 메커니즘의 값은 샤프트의 회전 각도 또는 전위차와 같은 연속적인 수치로 표시됩니다.

아날로그 기계와 달리 디지털 기계는 숫자 값의 상태를 표현하고 각 숫자를 별도로 저장할 수 있는 능력을 갖고 있었습니다. 랜덤 액세스 메모리 장치가 발명되기 전에는 디지털 기계에서 다양한 프로세서나 릴레이를 사용했습니다.

이름 계산기 1940년대부터 그것은 개념으로 대체되기 시작했다. 컴퓨터. 이러한 컴퓨터는 이전에 사무원이 수행했던 계산을 수행할 수 있었습니다. 값은 더 이상 물리적 특성(아날로그 기계처럼)에 의존하지 않기 때문에 디지털 하드웨어를 기반으로 하는 논리적 컴퓨터는 설명할 수 있는 모든 작업을 수행할 수 있게 되었습니다. 순수 기계 시스템 .

튜링 기계는 계산 능력의 제한에 따라 계산할 수 있는 것을 공식적으로 수학적으로 정의하도록 설계되었습니다. Turing 기계가 작업을 완료할 수 있으면 해당 작업은 Turing 계산 가능한 것으로 간주됩니다. Turing은 주로 무엇을 계산할 수 있는지 결정할 수 있는 기계를 설계하는 데 중점을 두었습니다. Turing은 숫자의 근사치를 계산할 수 있는 Turing 기계가 있는 한 그 값은 셀 수 있다고 결론지었습니다. 또한 Turing 기계는 AND, OR, XOR, NOT 및 If-Then-Else와 같은 논리 연산자를 해석하여 다음을 결정할 수 있습니다.