Формалізація поняття алгоритму

Поштовхом до виникнення теорії алгоритмів як окремого розділу математики стала невдача в знаходженні алгоритмів розв’язування деяких масових проблем. Найвідомішими з них були проблема істинності для арифметичних формул, проблема істинності для формул числення предикатів 1-го порядку та 10-а проблема Гільберта про розв'язність діофантових рівнянь.

Виникла гіпотеза про те, що для деяких масових проблем алгоритми їх розв'язування взагалі не існують. Але для доведення неіснування алгоритму треба мати його точне математичне визначення. Тому після сформування поняття алгоритму як нової та окремої сутності першочерговою стала проблема знаходження адекватних формальних моделей алгоритму.

Зауважимо, що відкриття поняття алгоритму як самостійного, окремого поняття не можна змішувати з відкриттям конкретних формальних моделей алгоритму чи алгоритмічно обчислюваної функції. Такі моделі запропоновані якраз для адекватного формального уточнення інтуїтивного поняття алгоритму, яке є для них первісним.

Пошук формальних уточнень поняття алгоритму проводився в таких напрямах:

1) Опис точного математичного поняття алгоритмічної машини та обчислюваності на ній. Першою формальною моделлю алгоритмічної машини була машина Тьюрінга, яка моделює елементарні дії при реалізації алгоритму людиною (А. Тьюрінг, Е. Пост, 1936). Зараз відомо багато різновидів машин Тьюрінга. Із пізніших формальних моделей алгоритмів відзначимо також нормальні алгоритми (А. Марков, І952) та регістрові машини (Д. Шепердсон, Г. Стерджіс, 1963). Модифікація регістрових машин - машини із натуральнозначними регістрами.

2) Опис певних класів функцій, для яких існує алгоритм знаходження функції за значеннями її аргументів, тобто уточнюється не первісне поняття алгоритму, а похідне поняття алгоритмічно обчислюваної функції. Спочатку такі описи були запропоновані для функцій, заданих на множині натуральних чисел, пізніше - для функцій, заданих на множинах інших об’єктів.

Першими формальними моделями алгоритмічно обчислюваних функцій були l- означувані функції (А. Чорч, 1932) та загальнорекурсивні функції (К. Гедель, 1934). Вказані класи визначались як функції, графіки яких породжуються відповідно численням l-конверсій і численням Ербрана-Геделя. В 1936 році С. Кліні поширив поняття загальнорекурсивної функції на випадок часткових функцій, увівши поняття частково рекурсивної функції, та описав клас частково рекурсивних функцій у чисто функціональних термінах. У 1943 році Е. Пост запропонував модель обчислюваних функцій на основі введеного ним числення спеціального вигляду (канонічних систем).

Ураховуючи розглянутий вище зв’язок алгоритмів і числень, формальні моделі алгоритмів та алгоритмічно обчислюваних функцій можуть бути задані у вигляді формальних систем.

У 1936 р. А. Чорч і С. Кліні довели, що класи загальнорекурсивних та l-означуваних функцій збігаються. На основі цього факту й аналізу ідей, які привели до вказаних понять, А. Чорч висунув знамениту тезу про збіг класу АОФ із класом загальнорекурсивних функцій. С. Кліні узагальнив цю тезу для випадку часткових функцій. Доведений А. Тьюрінгом у 1937 р. збіг класів частково рекурсивних функцій та функцій, обчислюваних на машинах Тьюрінга, став ще одним підтвердженням тези Чорча. Пізніше такі збіги були встановлені для всіх відомих формальних моделей АОФ. Тому є всі підстави вважати, що кожна із названих вище формальних моделей адекватно уточнює інтуїтивне поняття АОФ.

3. Машини з натуральнозначними регістрами (МНР).

МНР- обчислюваність

Машина з натуральнозначними регiстрами (МНР) є iдеалiзованою моделлю комп’ютера. МНР мiстить, узагалі кажучи, нескiнченну кiлькiсть регiстрiв, умiстом яких є натуральнi числа. Регiстри нумеруємо (йменуємо) натуральними числами, починаючи з 0, i позначаємо їх R ₀ , R ₁ ,..., R_n ,.... Вмiст регiстру R_n позначаємо ’R_n.

Послiдовнiсть (’R ₀, ’R ₁ ,..., ’R_n ,...) умiстiв регiстрiв МНР назвемо конфiгурацiєю МНР.

МНР може змiнити вмiст регiстрiв згiдно з виконуваною нею командою. Скiнченний список команд утворює програму МНР. Команди програми послiдовно нумеруємо натуральними числами, починаючи з 1. Номер команди в програмі називатимемо також адресою команди. МНР-програму з командами I ₁, I ₂ ,..., I_k будемо позначати I ₁ I ₂ ...I_k . Довжину (кiлькiсть команд) МНР-програми P позначатимемо | P |.

Команди МНР бувають 4-ох типiв.

Тип 1. Обнулення n -го регiстру Z(n): ’R_n:=0.

Тип 2. Збiльшення вмiсту n- го регiстру на 1 S(n): ’R_n:= ’R_n+ 1.

Тип 3. Копіювання вмісту регістру T(m,n): ’R_n:= ’R_m (при цьому ’R_m не змiнюється).

Команди типiв 1-3 називають арифметичними. Пiсля виконання арифметичної команди МНР повинна виконувати наступну за списком команду програми.

Тип 4. Умовний перехiд J(m,n,q): якщо ’R_n =’R_m, то перейти до виконання q-ї команди, iнакше – виконувати наступну за списком команду програми.

Число q у команді J(m,n,q) назвемо адресою переходу.

Виконання однiєї команди МНР назвемо кроком МНР.

Зрозуміло, що саме МНР-програми є формальними моделями алгоритмів, а поняття МНР використовується для опису функціонування МНР-програм.

Виконання програми МНР починає, перебуваючи в деякiй початковiй конфiгурацiї, з виконання 1-ї за списком команди. Наступна для виконання команда програми визначається так, як описано вище. Виконання програми завершується (програма спиняється), якщо наступна для виконання команда вiдсутня (тобто номер наступної команди перевищує номер останньої команди програми). Конфiгурацiя МНР у момент завершення виконання програми називається фiнальною, вона визначає результат роботи МНР-програми над даною початковою конфiгурацiєю.

Якщо МНР-програма P при роботi над початковою конфiгурацiєю (a ₀, a ₁ ,...) нiколи не спиняється, цей факт позначатимемо P (a ₀, a ₁ ,...)­, якщо ж коли-небудь спиниться, цей факт будемо позначати P (a ₀, a ₁ ,...)¯.

Якщо МНР-програма P при роботi над початковою конфiгурацiєю (a ₀, a ₁ ,...)спиняється iз фiнальною конфiгурацiєю (b ₀, b ₁ ,...), цей факт позначатимемо так: P (a ₀, a ₁ ,...)¯(b ₀, b ₁ ,...).

Таким чином, кожна МНР-програма визначає певне відображення вигляду N^N → N^N, де N^N - множина всіх нескінченних послідовностей натуральних чисел. Зрозуміло, що таке відображення однозначне. В той же час МНР-програми як моделі алгоритмів є фінітними об’єктами, звідки природно обмежитися розглядом тільки скінченних послідовностей. Тому надалі будемо розглядати тільки скінченні конфігурації.

Конфiгурацiю виду (a ₀, a ₁ ,..., a_п, 0, 0 ,...), в якiй ’R_m= 0 для всiх m>n, будемо називати скiнченною. Таку конфігурацію будемо позначати у вигляді (a ₀, a ₁ ,..., a_n). Якщо МНР-програма P починає роботу над скiнченною початковою конфiгурацiєю, то в процесi виконання P МНР перебуватиме тiльки в скiнченних конфiгурацiях.

МНР-програми P та Q назвемо еквiвалентними, якщо вони визначають однакові відображення послідовностей натуральних чисел. Це означає, що при роботi над однаковими початковими конфiгурацiями вони або обидві спиняються з однаковими фiнальними конфiгурацiями, або обидвi не спиняються.

МНР-програма P обчислює часткову n -арну функцiю f:N^п → N, якщо:

- за умови (a ₁, a ₂ ,..., a_п)Î D_f та f (a ₁, a ₂ ,..., a_п) =b маємо P (a ₁, a ₂ ,..., a_п)¯(b,...);

- за умови (a ₁, a ₂ ,..., a_п)Ï D_f маємо P (a ₁, a ₂ ,..., a_п)­.

Це означає, що значення аргументiв функцiї послiдовно розмiщуються в початкових регiстрах, починаючи з R ₀, значення функцiї знiмається з регiстру R ₀.

Замiсть P (a ₁ , a ₂ ,...)¯(b,...) надалі будемо писати P (a ₁ , a ₂ ,...)¯ b.

Неважко переконатись, що наведене визначення МНР-обчислюваності еквівалентне наступному:

МНР-програма P обчислює часткову n -арну функцiю f:N^п → N, якщо

f (a ₁, a ₂ ,..., a_п) =b Û P (a ₁, a ₂ ,..., a_п)¯ b.

Функцiю називають МНР-обчислюваною, якщо iснує МНР-програма, яка обчислює цю функцiю.

Розглянемо приклади МНР-програм для функцій та предикатів.

Приклад 1. МНР-програма для всюди невизначеної функції:

1) J(0,0,1)

Приклад 2. МНР-програма для предиката " x = y ":

1) J(0,1,3)

2) J(0,0,4)

3) S(2)

4) T(2,0)

Приклад 3. МНР-програма для функцiї f (x, y)= x+y:

1) J(1,2,5)

2) S(0)

3) S(2)

4) J(0,0,1)

Приклад 4. МНР-програма для функцiї f (x)=2 x:

1) T(0,1)

2) J(1,2,6)

3) S(0)

4) S(2)

5) J(0,0,2)

Зауважимо, що кожна МНР-програма обчислює безліч функцій натуральних аргументів та значень, але, зафіксовуючи наперед арність функцій (тобто кількість компонент початкових конфігурацій), дістаємо, що кожна МНР-програма обчислює єдину функцію заданої арності.

МНР-програму P назвемо стандартною, якщо в P для кожної команди виду J(m,n,q) виконується умова q£|P|+ 1.

Конкатенацiєю стандартних МНР-програм P=I ₁ I ₂ ...I_k та Q=I ₁ I ₂ ...I_m будемо називати стандартну МНР-програму I ₁ ...I_kI_k+1...I_k+m, де I_{k+ 1},..., I_k+m - це по суті команди програми Q, але кожна команда вигляду J(m,n,q) замiнюється командою J(m,n,q+k).

Нехай P - стандартна МНР-програма для n -арної функцiї f. Найбiльший номер регiстру, задiяного при обчисленнi f, позначатимемо r(P) (для n -арної функцiї завжди вважаємо r(P) ³ n -1).

Через P [ k ₁ ,k ₂ ,...,k_n → r ] позначимо МНР-програму, яка обчислює ту ж функцiю f, якщо початковi значення аргументiв занести в регiстри k ₁ ,..., k_n, a значення функцiї знiмати з регiстру r. При цьому для обчислення f задiянi щонайбiльше r(P) + 1 регiстрiв - із 0-го по r(P) - й включно.

МНР-програма P [ k ₁ ,k ₂ ,...,k_n → r ] для випадку k ₁< k ₂< ... < k_n має такий вигляд:

T(k_i, i- 1 ), 1 <i£n

Z(k), n£k£ r(P)

P’

T(0,r)

Тут МНР-програма P’ відрізняється від P тільки зміщенням адрес команд та адрес переходу на r(P).

ЛЕКЦІЯ З

ПЛАН

1. Машини Тьюрінга. Обчислюваність за Тьюрінгом.

2. Нормальні алгоритми Маркова. Обчислюваність за Марковим.

3. Система Поста. Обчислюваність за Постом.

Поиск по сайту: