АВТОМАТИ ЗРОСТАННЯ
інші, змінюються стану елементів, змінюються і зв'язки між ними (в результаті можуть з'являтися непов'язані з початковим об'єктом частини, які потім функціонують самостійно). Т. о., до класу А. н. відносяться всі біол. організми чи колективи таких організмів, які ростуть самі та створюють собі нащадків. Формалізацією та вивченням таких А. р. займаються відповідні природничі науки. У певному сенсі до класу А. н. можна віднести і будь-який обчислювач (людини, машину), який у процесі обчислення пише цифри чи ін. ці знаки можна як елементи, що він породжує у процесі обчислення.
Розглянемо математично точні концепції А.Р. (Див. Автоматова теорія). Ці концепції є окремим випадком загального поняття керуючих систем. Вони можуть бути розглянуті також як конструктивне уточнення нескінченного автомата. За своїм призначенням математично точні концепції A. н. можна розділити на дві групи: 1) концепції, що є мовою для опису реально існуючих (технічно реалізованих) автоматів, зокрема, для опису алгоритм, процесів, які у таких автоматах; 2) концепції, що є мовою для уточнення інтуїтивного поняття алгоритм. процесу. До 1-ї групи А. н. можна віднести ітеративні автомати, «розміщені» в евклідовому просторі (такі автомати, зокрема, розглядав Дж. фон Нейман при вивченні проблеми автоматів самовідтворюваних). Ще до цієї групи можна віднести автомати, описані А. Беркс і Дж. Холланд. До 2-ї групи можна віднести Тьюринга машини, поняття алгоритму, описаного А. Н. Колмогоровим та B. А. Успенським, А. р., описаного Я. М. Барздінем, та інші абстрактні машини, що використовуються для уточнення інтуїтивного поняття алгоритму.
Під час розгляду 2-ї групи А.нар. виникає проблема створення якомога більш загальної концепції А. р., яка не суперечить вимогі, що кожен елемент у кожен дискретний момент часу виконує лише «дія обмеженої складності». Розглянемо, наприклад, машини Тьюринга. Вони характеризуються граничною простотою допустимих засобів під час запису та переробки інформації. Зокрема, інформація в них записується на одновимірній стрічці та зростання стрічки можливе лише по краях. Але інформація, по суті, може бути записана і у вигляді матриці, графа та ін., І для того, щоб обробляти її на машині Тьюринга, її треба перекодувати. Сам процес перекодування може бути досить складним, іноді навіть складнішим, ніж саме обчислення. Звідси виходить ідея А. Н. Колмогорова про алгоритм, що переробляє довільну інформацію. Цей алгоритм, на відміну машини Тьюринга, може переробляти довільні комплекси (напр., графи з фіксованим розгалуженням). Однак самі перетворення, як і у випадку машини Тьюринга, локальні: кожен такт може бути перетворена лише околиця обмеженого радіуса одного фіксованого елемента, званого початковим.
Більше загальну концепцію А. р. (Називається надалі узагальненим А. р.) описав Я. М. Барздінь. Вона з наступних інтуїтивних міркувань. Кожен автомат складається з елементів обмеженого числа типів (можна навіть рахувати, з елементів одного типу). Елементи можуть бути пов'язані між собою зв'язками обмеженої складності, що належать також до обмеженої кількості типів. Робота автомата загалом складається з його елементів. Кожен елемент у кожен дискретний момент може лише дію обмеженої складності. Формалізуючи описане інтуїтивне поняття А. р., приходимо до поняття узагальненого А. р. Воно характеризується тим, щоінформація, як і у разі алгоритму Колмогорова — Успенського, задається у вигляді довільного графа з фіксованим розгалуженням, але на відміну від попередніх випадків перетворення інформації протікає паралельно: кожна вершина графа є елементом, який у кожний дискретний момент часу «переглядає» свою околицю обмеженого радіуса і залежно від цієї околиці (що розглядається з точністю до ізоморфізму) змінює свої зв'язки з елементами цієї околиці та породжує нові елементи; при цьому правило функціонування у всіх елементів даного автомата те саме. Виникає питання існування універсального правила функціонування елементів, т. е. існування такого правила функціонування А, що будь-який узагальнений А. р. можна моделювати на деякому узагальненому А. р., елементи якого функціонують відповідно Ло. При цьому під моделюванням мається на увазі блочне моделювання, коли окремі блоки моделюючого автомата точно відтворюють функціонування складових елементів моделюється автомата і кожному такту моделюється автомата відповідає один макротакт фіксованої довжини моделюючого автомата. Показано, що таке універсальне правило функціонування існує й до того ж воно відносно нескладніше.
Великий інтерес представляє моделювання А. н. на автоматах, що мають досить просту тех. реалізацію. Отримані результати показують, що існує мережа логічна з числом елементів порядку, яка моделює з розтягуванням порядку будь-який узагальнений А. р., поки він складається не більше ніж з елементів (при довільно фіксованому правилі функціонування елементів). Інтерес становлять також питання, пов'язані з побудовою надійних А. р. з ненадійних елементів, проте ці питання ще малодосліджено.
Літ.: Колмогоров А. Н., Успенський В. А. До визначення алгоритму. "Успіхи математичних наук", 1958, т. 13, ст. 4; Барздин Я. М. Проблеми універсальності в теорії зростаючих автоматів. "Доповіді АН СРСР", 1964, т. 157, N "3; Офман Ю. П. Моделювання системи, що самоконструюється, на універсальному автоматі. «Проблеми передачі», 1966, т. 2, в. 1; Holland J. Н. Iterative circuit computers. У кн.; Процедури western joint computer conference. New York, 1960; Беркс А. У. Обчислення, поведінка та структура постійних і зростаючих автоматів. У кн.: Самоорганізовані системи. Пров. з англ. М., 1964; Нейман Дж. тло. Теорія самовідтворюваних автоматів. Пров. з англ. М., 1971 [бібліогр. С. 322-326]. Я. М. Барздінь.