Анотація: В лекції показана спільність традиційних комп'ютерних технологій, в основі яких лежить теорія алгоритмів і машини Тьюринга, з нейрокомп'ютерних технологіями.
3.1. Інтуїтивні передумови формалізації поняття "алгоритм"
Негативні наслідки значних успіхів мікроелектроніки та обчислювальної техніки виражаються в тому, що з середини 70-х років минулого століття вони стали розвиватися в помітному відриві від досягнень теорії обчислень. Добре апробований на практиці операційний базис ЕОМ класичної архітектури допускав такий розрив між теорією і практикою. Але ситуація кардинальним чином змінилася через відсутність видимого прогресу в промисловому освоєнні нанотехнологій, де так і не вдається вирішити проблему декоге-рентізаціі квантового "робочого тіла", викликаного розсіюванням теплової енергії, що призводить до неоднозначного реалізації необхідних функцій і, як наслідок, до втрати управління ходом обчислювального процесу. Проблему декогеренції можна вирішити двома шляхами:
- комплексом фізико-технічних заходів, що стабілізують на тривалих тимчасових інтервалах (близько 10 тис. годин і вище) відповідність між структурою і функцією квантового "робочого тіла", ніж, власне, і займаються фізико-технічні лабораторії в усьому світі;
- адаптацією методів організації обчислень під умови квазіустойчівие реалізації необхідних функцій квантовим "робочим тілом". Перший шлях повністю зберігає традиційні методи і засоби
організації обчислень, а з ним і напрацьоване програмне забезпечення, які повинні підтримуватися фізико-технічними і схемотехническими рішеннями, стійкими до зовнішніх чинників, що впливають на "нескінченних" інтервалах часу.
Другий шлях вимагає визнання квантових реалій і перегляду основоположних принципів організації обчислень, а значить, і більш поглибленого аналізу досягнень теорії обчислень.
Центральне місце в цій теорії займає поняття "алгоритм", без якого не може обійтися і обчислювальна техніка. Викликано це тим, що використання ЕОМ, починаючи з класичної фон-неймановской архітектури, стає можливим тільки в тому випадку, якщо можна вирішити завдання представлена у формалізованому вигляді, тобто частково впорядкованої послідовністю арифметико-логічних операцій, які
здатна виконати конкретна ЕОМ. Сам термін походить від імені арабського математика Мохаммеда ібн Мусса Альхварізмі (IX століття).
Під що дозволяє алгоритмом в математиці розуміють загальне правило вирішення завдань з деякого класу, яке можна знайти за кінцеве число кроків, без евристики і чисто механічно, якщо саме рішення існує [ 45 ].
Про дозвільному алгоритмі доводиться говорити не тільки при вирішенні класу задач, але і в разі виконання однієї арифметико-логічного операції (підсумовування, множення, порівняння і т. П.), Яка в кінцевому рахунку являє собою послідовність правил використання перетворень двійок або трійок символів, що входять в впорядковані послідовності, іменовані числами. Зокрема, складання двох цілих десяткових чисел 327 і 458 (327 + 458 = 785) можна виконати за наступним алгоритмом:
Крок 1. присвоїти індексу 
значення, що відповідає першому члену натурального ряду 
, І виділити в доданків перші справа символи 
і 
, Де нижній індекс 
відповідає положенню сумміруемих символів в впорядкованої послідовності (номер розряду). По таблиці підстановки, що відповідає правилу підсумовування ( табл. 3.1 ), Вибрати символи 5 і 1, де символ 5 відповідає значенню першого розряду "суми" ( 
), А символ 1 - значенням "одиниці переносу" ( 
) У другій розряд. якщо не останній член натурального ряду ( 
), То виконати крок 2. В іншому випадку (при 
) Перейти до кроку 3.
Крок 2. присвоїти індексу значення наступного члена натурального ряду 
(Тут 
не дія, а умовне позначення безпосередньо наступного члена натурального ряду, що стоїть за ). Виділити в доданків символи з ( ) -Го розряду (в даному випадку це 
і 
). З урахуванням значення символу "одиниця переносу" від попереднього розряду ( 
) По таблиці підстановки вибрати символи 8 і 0, де символ 8 відповідає значенню другого розряду "суми" ( 
), А символ 0 - значенням символу "одиниця переносу" ( 
) В ( 
) -Й розряд. якщо символ не останній член натурального ряду ( 
), То повторити крок 2. В іншому випадку (при 
) Виконати крок 3.
У нашому випадку повторюємо крок 2, тобто 
У виділеному розряді доданків розташовані символи 
і 
, Яким з урахуванням значення символу "одиниця переносу" від попереднього розряду 
в таблиці підстановки відповідають символи 
і 
При цьому виконується умова 
, Що призводить до кроку 3.
Крок 3. Підставити в наступний розряд суми значення символу "одиниця переносу". Кінець алгоритму: сума являє собою впорядковану послідовність символів 
Наведених даних досить для наступних узагальнень:
- Будь алгоритм передбачає перерахування деяких дій (у разі обчислень - арифметико-логічних операцій), кожне з яких також виконується за деяким заздалегідь заданим алгоритмом, тобто завдання алгоритму вже передбачає ставлення ієрархії, коли входять в нього дії також виконуються за певним алгоритмом над певною сукупністю "елементарних дій".
- Ставлення ієрархії в алгоритмах передбачає деякі вихідні, певні, але невизначені елементарні дії. У нашому випадку це:
- асоціативна вибірка по вмісту даних з таблиці підсумовування символів, які апріорі відомі, однозначно зрозумілі і реалізовані на практиці;
- підстановка символів в результуючу послідовність (операнд "сума").
- Незалежно від рівня ієрархії кожен алгоритм повинен виконуватися за кінцеве число кроків. У нашому випадку на рівні алгоритму складання кількість кроків визначається розрядної сіткою (n) сумміруемих змінних. На рівні "елементарних дій" кількість кроків визначається різноманіттям значень триплетних символів
, Індексуючих рядки таблиці перетворення за законом підсумовування триплетів вхідних символів в дуплети вихідних 
. Гідність асоціативної вибірки пари ( 
) Як раз і полягає в тому, що вона здійснюється за 1 крок [ 46 ]. - 4. Будь-який алгоритм можна зупинити тільки за умовою, але саме умова може бути визначено як властивість результату, який може бути отриманий або за допомогою даного алгоритму (наприклад, найбільший спільний дільник двох натуральних чисел в алгоритмі Евкліда), або за допомогою додаткової процедури, яка в нашому випадку має на увазі досягнення позиції, позначеної символом
Слідство 3.1. Вихідною "елементарної операцією", яка задає в традиційній обчислювальній техніці правила підсумовування, множення, ділення, порівняння і т. Д., Є асоціативна вибірка, яка характерна для нейроподібних обчислювальних технологій і яка в прихованому вигляді реалізується на схемотехническом рівні організації роботи класичних ЕОМ починаючи з фон-неймановской архітектури.
Слідство 3.2. Програмно-апаратні платформи класичних ЕОМ апріорі є ієрархічними і включають як мінімум два рівні: "елементарних дій" і заснованих на них арифметично-логічних операцій (в сучасній термінології відповідно мікрокомандном і асемблерний).
Слідство 3.3. Будь-яке завдання, яке вирішується класичної ЕОМ будь-якої архітектури, в кінцевому рахунку представлена в Нейроподібні операційному базисі асоціативної вибірки і підстановки символів з деякого кінцевого алфавіту. Іншими словами, якщо абстрагуватися від громіздкість опису, то нейроподібні операційного базису досить для формального опису алгоритму розв'язання будь-якої обчислювальної задачі, якщо таке рішення існує.
Прогрес у розвитку алгоритмічних методів вирішення завдань стався задовго до появи ЕОМ і привів до того, що такі математики, як Р. Декарт, Г. Лейбніц і Д. Гільберт, виходили з того, що рішенням будь-якого поставленого математичної задачі або проблеми повинно бути її алгоритмічне Рішення. Г. Лейбніц навіть придумав пристосовану для цих цілей автоматично працюючу машину, яку не вдалося реалізувати на практиці. Проте віра в універсальність алгоритмічних методів дожила до середини 30-х років минулого століття, коли К. Гедель [ 47 ] Довів алгоритмічну нерозв'язність деяких математичних проблем. Було показано, що відомі математичні проблеми неможливо вирішити за допомогою алгоритмів з деякого
точно певного класу. Алгоритмічна розв'язність по К. Геделя залежить від ступеня збігу цього точно певного класу алгоритмів і класу всіх інтуїтивно зрозумілих алгоритмів. В результаті поки математики, слідуючи Д. Гільберт, вірили, що всі поставлені математичні завдання алгоритмічно розв'язні, у них не було необхідності уточнювати саме поняття "алгоритм": раз за допомогою деякої сукупності правил вирішена деяка математична проблема, то цього вже було достатньо для того , щоб вважати сукупність використаних правил алгоритмом. Тільки твердження про алгоритмічної нерозв'язності, яке оперує з усіма мислимими алгоритмами, вимагає попереднього уточнення самого поняття "алгоритм".
Для подолання виниклої логічної колізії був запропонований цілий ряд уточнень цього поняття, що роблять його адекватним інтуїтивного розуміння терміна "алгоритм". При цьому вдалося довести еквівалентність всіх уточнень на основі общерекурсівних функцій (К. Гедель, С. Кліні, 1934-1936), 
-рекурсівних функцій (К. Гедель, С. Кліні, 1936), 
-определімих функцій (А. Черч, С. Кліні, 1933-1936), машин Тьюринга (А. Тьюринг, Е. Пост, 1936), марковских алгоритмів (А. Марков, 1950), графічних схем (Р. Петер, 1958) і т.п.
Більш того, виявилося, всі алгоритми в одному з точних смислів є алгоритмами в інтуїтивному сенсі, а всі відомі алгоритми можна "промоделювати" будь-яким з алгоритмів в одному з точних значень.
Це дозволило А. Черчу [ 48 ] Сформулювати тезу про тотожність інтуїтивного поняття "алгоритм" з одним з еквівалентних між собою точних визначень. Теза Черча грає в математиці ту ж роль, що і другий початок термодинаміки у фізиці, так як неможливо строго визначити поняття "алгоритм" в інтуїтивному сенсі.
В обчислювальній техніці найбільшого поширення набуло уточнення поняття "алгоритм" на основі машин Тьюринга, яке виходить з наступних вимог, що лежать в основі його інтуїтивного розуміння.
Вимога 1. Алгоритм оперує з конструктивними об'єктами, над якими можна виконати заздалегідь обумовлені операції.
Такі об'єкти, якщо вони не є словами над деякими алфавітом 
, Можна перенумерувати елементами натурального ряду 
і потім оперувати самими об'єктами, а їх номерами (геделезація). Тому в обчислювальній техніці в якості конструктивних об'єктів можна розглядати тільки слова, тобто кінцеві послідовності символів з деякого алфавіту . Дотримуючись [ 45 ], Позначимо безліч слів над через 
, Якому належить і "порожній" слово (#), тобто є полугруппой [ 49 ] З одиничним елементом # по відношенню до двомісної операції послідовного написання слів.
Вимога 2. Алгоритм 
задається кінцевим приписом 
, Вхідним алфавітом 
, Вихідним алфавітом 
, що містить і робочим алфавітом і розмірним числом 
, де 
- кількість слів у послідовності слів, кожне з яких містить 
символів з алфавіту 
Відповідно до такого описом алгоритм можна застосувати до -членів послідовності слів над 
Без порушення спільності обмежимо розгляд алгоритмів на "микропрограммном" рівні організації обчислень, тобто будемо вважати 
Кажуть що застосовується до , якщо є вихідним об'єктом при виконанні операцій, зазначених в приписі , З використанням робочого алфавіту . Можливо, що згідно операції повинні бути припинені, після чого має бути написано слово над . Якщо написане слово є елементів , То воно вважається результатом застосування алгоритму. В іншому випадку його застосування не призводить ні до якого результату. При цьому вважається, що саме припис звичайно, так як нескінченні приписи неможливо передати і зафіксувати.
Вимога 3. Припис має бути складено так, щоб визначаються ним операції виконувалися поетапно, тобто послідовно одна за одною. Згідно з цим вимогу припис 
має містити не тільки опис операцій, але і вказівки переходу від однієї позиції до "наступної за нею".
Вимога 4. Припис має бути складено так, щоб його виконання було однозначно і не допускало свободи прийняття рішень. Однозначність виконання приписи необхідна для створення технічних пристроїв. В математиці відмова від однозначності призводить до обчислення замість алгоритму.
Вимога 5. Припис має бути складено так, щоб його виконання було відтворено. Це передбачає наступне: застосування алгоритму до одного і того ж слова призводить або до жодного, або до одного і того ж результату. Дана вимога виключає приписи з використанням імовірнісного механізму вибору або реалізованої операції, або перетворюється слова або символу.
Вимога 6. Припис має бути складено так, щоб його виконання не вимагало ніякої іншої інформації, крім тієї, яка міститься у вихідному слові і в самому приписі.
Вимога 7. На довжину приписи , Довжину слів, з якими воно може оперувати, і число кроків, необхідних для його виконання, які не накладається ніяких інших обмежень, крім кінцівки, тобто міркування гіперкомбінаторних размерностей обчислень при теоретичних дослідженнях алгоритмів в розрахунок не приймаються.
Вимога 8. Припис має бути складено так, щоб виконуючому його обчислювачеві була потрібна як завгодно велика, але не нескінченна пам'ять.
