К понятию функции как вычислительной процедуре
Работа посвящена формальному уточнению общего понятия функции как вычислительной процедуры. При этом выбирается предельно возможный уровень абстракции, который условно можно было бы назвать пропозициональным: все объекты трактуются исключительно как теоретико-множественные «черные ящики». Понятие фу...
Saved in:
| Published in: | Штучний інтелект |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/58341 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | К понятию функции как вычислительной процедуре / В.В. Зубенко // Штучний інтелект. — 2010. — № 4. — С. 20-29. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859948427886985216 |
|---|---|
| author | Зубенко, В.В. |
| author_facet | Зубенко, В.В. |
| citation_txt | К понятию функции как вычислительной процедуре / В.В. Зубенко // Штучний інтелект. — 2010. — № 4. — С. 20-29. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | Работа посвящена формальному уточнению общего понятия функции как вычислительной процедуры. При этом выбирается предельно возможный уровень абстракции, который условно можно было бы назвать пропозициональным: все объекты трактуются исключительно как теоретико-множественные «черные ящики». Понятие функции-процедуры позволяет уточнить и общее понятие абстрактного алгоритма – оно становится его производным. Рассматриваются общие свойства таких алгоритмов. Показано, что функции-процедуры и абстрактные алгоритмы замкнуты относительно регулярных композиций. Для табличных алгоритмов дано общее решение проблемы анализа.
Робота присвячена формальному уточненню загального поняття функції як обчислювальної процедури. При цьому вибирається гранично можливий рівень абстракції, який умовно можна було б назвати пропозиційним: усі об’єкти трактуються виключно як теоретико-множинні «чорні скриньки». Поняття функції-процедури дозволяє уточнити і загальне поняття абстрактного алгоритму – воно стає його похідним. Розглядаються загальні властивості таких алгоритмів. Показано, що функції-процедури і абстрактні алгоритми замкнені відносно регулярних композицій. Для табличних алгоритмів подано загальний розв’язок проблеми аналізу.
The research is dedicated to the formal refinements of general notion of function as a computational
procedure. The strongest level of abstraction is adopted: all objects are treated as “black box”. The notion of
function as a procedure makes it possible to revise generic notion of abstract algorithm, as it becomes it’s
derivative. The general properties of such algorithms are considered. It is proven that classes of functionprocedures
and abstract algorithms are closed under regular compositions. A generic solution for the tabulated algorithms analysis problem is proposed
|
| first_indexed | 2025-12-07T16:15:37Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 4’2010 20
1-З
УДК 004.8:519.254
В.В. Зубенко
Киевский национальный университет им. Тараса Шевченко, г. Киев, Украина
К понятию функции
как вычислительной процедуре
Работа посвящена формальному уточнению общего понятия функции как вычислительной процедуры.
При этом выбирается предельно возможный уровень абстракции, который условно можно было бы
назвать пропозициональным: все объекты трактуются исключительно как теоретико-множественные
«черные ящики». Понятие функции-процедуры позволяет уточнить и общее понятие абстрактного
алгоритма – оно становится его производным. Рассматриваются общие свойства таких алгоритмов.
Показано, что функции-процедуры и абстрактные алгоритмы замкнуты относительно регулярных
композиций. Для табличных алгоритмов дано общее решение проблемы анализа.
Понятие функции – одно из самых важных понятий информатики. Известно два
различных его толкования: процедурное (интенсиональное) и теоретико-множественное
(экстенсиональное). В первом случае функция (от лат. functio – исполнение, соверше-
ние) рассматривается как способ для получения определенного результата на аргумен-
тах, во втором – как синоним теоретико-множественного отображения. Эти два подхода
вошли в математическую практику не случайно. Они имеют принципиально разный
смысловой оттенок. Если первый апеллирует к сути, содержанию конкретной функции,
то второй – к тому, чем она отличается от других. Когда говорят о некотором отобра-
жении :f A B→ , то интересуются только тем, принадлежит ли пара ( ),a b подмно-
жеству f A B⊂ × , есть ли связь между элементами a и b или нет. При этом вопрос о
природе этой связи, каким способом она осуществляется, считается несущественным.
Фактически при экстенсиональном подходе осуществляется переход на более высокий
уровень абстракции, при котором нивелируются индивидуальные черты конкретных
объектов. В случае же функции-процедуры f на неё тоже смотрят как на возможность
поставить в соответствие элементам множества A элементы множества B , но сам
способ, реализация такого сопоставления выходит на передний план при определении f .
Исторически процедурный подход сформировался первым (сам термин пред-
ложил Г. Лейбниц (1646 – 1716)). Но он был почти вытесненный вторым в начале
ХХ ст. в связи с тотальным переходом математики на теоретико-множественную
основу. Достаточно сослаться на названия таких фундаментальных математических
дисциплин, как функциональный анализ, теория функций комплексных переменных
и т.д. Сегодня процедурный подход постепенно возвращает свои позиции благодаря бур-
ному развитию конструктивной математики и информатики. Понятие функции как
действия является центральным в теории алгоритмов, теории программирования,
программологии и языках программирования.
Далее в тексте термин «функция» будет употребляться в обоих смыслах – и в
традиционном теоретико-множественном, и как вычислительная процедура. Какой
из них имеется ввиду – будет видно из контекста.
К понятию функции как вычислительной процедуре
«Штучний інтелект» 4’2010 21
1-З
1 Функции как вычислительные процедуры
Пусть U – произвольное множество. Интуитивно функция f определяется как
процедура, которая может быть применена к одному или нескольким элементам
(аргументам) множества U с целью нахождения других элементов (результатов) с U.
Применение функции состоит в проведении вычисления – последовательности опре-
деленных действий, которая завершается построением результата. О том, как про-
исходит выбор этой последовательности, чем он определяется, речь пойдет ниже.
А пока заметим, что функция не всегда гарантирует однозначность, и даже сущес-
твование результата. Это означает, что процесс вычисления может не привести к
результату, а применение функции повторно к тем же аргументам может приводить к
другому результату. В этом смысле все функции разделяются на детерминированные
и недетерминированные. Первые гарантируют однозначность своих результатов, все
остальные принадлежат ко вторым. Как видим, 1) вычислительное пространство, в
котором развертываются вычисления, является как минимум двумерным – с
временной и информационной координатами и 2) существует механизм для опреде-
ления результатов вычислений.
Термы ( )f x , fx и xf используются для записи результата применения функции
f к аргументу x . Учитывая, что результата такого применения по определению может и
не быть, будем добавлять к указанным термам справа символ ↓ в случае, если дан-
ный результат гарантированно существует. С каждой функцией f связаны две области –
определения { : ( ) }fD x U f x= ∈ ↓ и значений { : ( )& }f fE y U y f x x D= ∈ = ∈ . Чтобы
показать эту связь, функцию f подают в виде : f ff D E→ и называют всюду опреде-
ленной на fD . На практике бывает проще описать не сами области определения и зна-
чений данной функции, а определенные их надмножества, например, T и R . Чтобы
подчеркнуть, что функция рассматривается над этими более общими областями, ее
записывают как f : Т→R и называют частичной, а пару ( ),T R – типом функции.
Будем считать выражение ( )f x бессодержательным (т.е. равным # ) для всех аргу-
ментов вне области определенности функции. Функции :f A B→ и :g C D→ назы-
ваются эквивалентными ( )f g≅ , если x A C∀ ∈ ∪ fx gx= (*). Например, функции
0 :f N N→ и :f N N→ , определяемые термами 0 /
def
f x x x= и fx
def
= 1 , не экви-
валентны. Их разделяет точка 0x = . Эквивалентные функции называются равными,
если их типы совпадают.
Вернемся к интуитивному определению функции и попытаемся его детализи-
ровать. Как следует из этого определения, для уточнения функции необходимо (и до-
статочно!) уточнить понятия процедуры и вычисления.
Если взять одно отдельное вычисление, то оно не является одноразовым актом, а наоборот,
начавшись в определенный фиксированный момент времени с определенной
начальной информацией на входе, развертывается во временном пространстве и
сопровождается выполнением определенных элементарных действий и определением
результата. Пусть <Γ <, > – произвольная линейно упорядоченная совокупность,
которую будем трактовать как временное пространство1. Обозначим
+τ и
−τ –
непосредственно следующий и предыдущий моменты времени относительно момен-
1 В некоторых случаях часовое пространство может иметь более сложную структуру [1].
Зубенко В.В.
«Искусственный интеллект» 4’2010 22
1-З
та τ . Считается, что во временном пространстве нет наименьшего и наибольшего
элементов. Информационную составляющую процессов вычислений представляют так
называемые состояния. На данном уровне абстракций нас не интересует их струк-
тура. Пусть S – произвольное множество состояний.
Двойка =Π ,SΓ называется вычислительным пространством, а пара ( , )τ ∈ Γ ×s S –
конфигурациями пространства. Пусть 1 2, ,τ τ τ ∈Γ . Положим { | }τ ′ ′Γ = τ ∈Γ τ ≤ τ ,
\ { }+
τ τΓ = Γ τ , ττ ΓΓ=Γ− \ , 1 2 1 2[ , ] { : }τ τ = τ τ ≤ τ ≤ τ . Абстрактным процессом в вычис-
лительном пространстве с началом в момент времени τ называется произвольное
отображение вида :p S
τ
Γ → , а абстрактным процессом на интервале 1 2[ , ]τ τ – произ-
вольное отображение вида 1 2: [ , ]τ τ →p S . Состояния τp , ςp ( 1 2τ < ς < τ ) и 2τp
называются начальным, промежуточными и заключительным состояниями процесса p .
Возьмем произвольную функцию : f A B→ и ее аргумент a . Если процесс p на
интервале 1 2[ , ]τ τ начинается в состоянии a , а заканчивается в заключительном
состоянии b fa= , говорится, что он представляет функцию f на аргументе a . Говорят,
что совокупность процессов на интервалах представляет функцию f , если для каждого
ее аргумента из области определения эта совокупность содержит процесс, который
ее представляет на данном аргументе.
Теперь среди всех абстрактных процессов в вычислительном пространстве Π
попробуем выделить процессы-вычисления и их совокупности. Индексом многозначной
функции назовем максимальную мощность множеств значений функции на отдельно
взятых аргументах. Зафиксируем некую совокупность }0|:{ ≥→=∆ iSSfi элемен-
тарных операций на состояниях и определим функцию управления процессами.
Последняя с каждым моментом времени процесса связывает одно или несколько
возможных элементарных преобразований его состояния. Положим ее как имеющую
вид : 2δ Γ × → ∆S и конечный индекс1.
Вычислительной процедурой над пространством Π с совокупностью элементарных
преобразований ∆ и функцией управления δ называется тройка , ,д= Π ∆P .
Каждая вычислительная процедура порождает определенную совокупность про-
цессов вычисления в пространстве Π . Пусть τ ∈ Γ и Ss∈ – произвольные
моменты времени и состояние. Вычисления : τΓ →p S в процедуре P с началом в
момент времени τ и начальным состоянием 0s определяются рекуррентно: τ =p 0s
и для всех ς > τ ( )−ςς = ςp f p , где ( , )−ς ∈ δ ς ςf p . Функция управления по текущему мо-
менту времени ς и состоянию −ςp в предыдущий момент времени определяет сово-
купность элементарных операций, которые могут быть применены для получения
текущего состояния процесса. Будем говорить, что вычисление p в момент времени
ς переходит от предыдущего состояния −ςp к следующему состоянию ςp , и обоз-
начать этот факт −ς → ςPp p . Вариантов таких переходов может быть несколько,
поскольку функция перехода неоднозначна. В действительности их может быть: а)
два и более (в случае недетерминированных процедур); б) ровно один (в случае
детерминированных процедур); в) ни одного (вычисления останавливаются).
1 В общем случае функция управления может задавать преобразование и часового компонента
(при этом возможны «прыжки» процесса во времени как вперед, так и назад [1]).
К понятию функции как вычислительной процедуре
«Штучний інтелект» 4’2010 23
1-З
Вычисления p по процедуре P на интервале 1 2[ , ]τ τ определяются как
ограничение соответствующего вычисления p по процедуре P с началом в момент
1τ на временной интервал. 1 2[ , ]τ τ Будем говорить, что вычисление p в этом случае
начинается состоянием 1τp и заканчивается состоянием 2τp ,и обозначать этот факт
1 2τ ⇒ τPp p .
Обычно интерес представляют не все возможные вычисления в процедуре, а
прежде всего те, что начинаются в определенный фиксированный момент времени с
определенных выделенных входных состояний и заканчиваются определенными
выделенными заключительными состояниями. Поэтому введем понятие инициальной
процедуры 0 0( , , )τfinP S S над пространством Π как четверки 0 0, , ,τfinP S S , где
−P определенная процедура над пространством Π , 0 ⊆S S и SS fin ⊆ –
выделенные подмножества соответственно входных и заключительных состояний,
0τ ∈Γ – начальный момент времени. Результативными назовем вычисления в про-
цедуре P , которое начинается в момент времени 0τ с определенного начального
состояния 0pτ = 0 0s S∈ , заканчивается в определенный момент τ заключительным
состоянием pτ finS∈ , и все промежуточные состояния которого незаключительные.
Состояние pτ называется результатом данного вычисления на 0s , обозначается
( )*
0P s и есть единственным, если функция управления – однозначная. Если в
результативном вычислении 0τ ⇒ τPp p снять условие, чтобы все промежуточные
состояния были незаключительными, то о таком вычислении будем говорить как о
гиперрезультативном. Его исходные состояния могут встречаться и среди про-
межуточных, а заключительный обозначается ( )**
0P s . В некоторых случаях как
результат вычисления берется не само заключительное состояние, а значение на нём
некоторой результирующей операции : finVal S B→ , а также считают заклю-
чительными и те конечные вычисления, на последних состояниях которых не
определена функция управления. Если значение результирующей операции Val на
заключительном состоянии не определено, то оно считается безрезультатным.
Таковыми являются, як правило, и бесконечные вычисления, а также те конечные,
которые не имеют результативных продолжений.
Мы уточнили понятие процедуры и вычисления в ней. Это позволяет уточнить
и понятие функции как процедуры.
Функциями-процедурами называются инициальные вычислительные процедуры.
С каждой функцией-процедурой ( )0 0, ,τfinP S S связаны два ее графика – соответст-
вия на входных состояниях *
0: finP S S→ и **
0: finP S S→ , а именно те, значения
которых на начальном состоянии 0 0∈s S составляют заключительные состояния
соответственно всех результативных и гиперрезультативных вычислений с началом
в момент 0τ . О графиках *P и **P будем говорить как о таких, которые представляет
или вычисляет функция P .
Много примеров функций-процедур можно найти в математике, в частности, в
алгебре и геометрии. Например, задачи по планиметрии на построение с помощью
циркуля и линейки являются фактически задачами на построение определенных (не
обязательно детерминированных) функций. Состояниями здесь есть совокупности
Зубенко В.В.
«Искусственный интеллект» 4’2010 24
1-З
фигур на плоскости, которые могут быть построены с помощью циркуля и линейки и
операций выделения произвольной точки плоскости, точек пересечения фигур,
операций именования точек и фигур, а также условных вариантов подобных опе-
раций. Временное пространство дискретное и совпадает с натуральными числами.
Интересная ситуация возникает в случае существования нескольких решений задачи.
Тогда общее решение может обеспечить недетерминированная функция. Но ее можно и
детерминизировать. Если, например, для решения задачи используется школьная
доска и необходимо построить два разных решения, то после завершения построения
первого из них доска вытирается (полностью или частично) и функция возвращается
в одно из предыдущих состояний доски, но, что важно, не в предыдущую конфи-
гурацию – момент времени другой! Благодаря этому процесс вычисления может
быть продолжен детерминированно, как того требует построение второго решения.
Функции-процедуры, управление действиями в которых реально зависит от
временной компоненты, будем называть темпоральными в отличие от автоматных,
когда это не так.
Классическими примерами автоматных процедур являются конечные и мага-
зинные автоматы, машины Тьюринга, игровые исчисления и т.д. Если взять последние,
то иногда в их правилах и стратегиях временные факторы могут играть важную роль
и они приобретают признаки темпоральных процедур. Во многих играх (шахматы,
шашки, карты), например, важным фактором есть очередность хода. В шахматах
(шашках) во все нечетные моменты времени ходят белые, а в четные – черные.
Имеются и другие обстоятельства, связанные со временем. Например, рокировка ко-
роля в шахматах зависит от того, двигался ли он до этого момента игры. В некото-
рых моделях (игра с часами), на стратегию выбора очередного хода влияет ограни-
ченность времени на часах (игра в цейтноте). В последнем случае на временном
пространстве игровой функции определяют некоторую топологию.
Обратимся к натуральной арифметике и рассмотрим функцию (алгоритм Евклида)
GCD для нахождения наибольшего общего делителя ( )НСД ,a b двух натуральных чисел.
Пусть =Π ,SΓ – вычислительное пространство с натуральным временем N=Γ ,
множеством состояний S N N+ += × , \ {0}.N N
+
= Набор операций { },∆ = α β и фун-
кцию управления δ определим так. Для произвольных ,a b N +∈ , 0τ ≥ положим:
( , ) ( , )α = −a b a b b , ( , ) ( , )a b a b aβ = − , ( , ) ( , )a b a bθ = , ( )( ) ( )( ), , | |a b a b a bδ τ = ≠ → > →α β θ ,
где ( | )p a b→ равно a , если 0p ≠ и b для 0p = .
Определим функцию , ,GCD = Π ∆ δ и ее инициализированный вариант
GCD 0( , ,0)finS S с результирующей операцией проектирования по первой компоненте
1pr , где 0S N N+ += × , fin NS i= . Несложно проверить, что полное вычисление функции
GCD на каждом входном состоянии ( )0 ,s a b= будет результативным. Действи-
тельно, непосредственно из определения GCD и соотношений:
1) ( )gcd ,d d d= ,
2) ( ) ( )( )gcd , gcd ,b a a b a b a> ⇒ = − , 3) ( ) ( )( )gcd , gcd ,b a a b b a b< ⇒ = −
следует, что последнее состояние в вычислении функции GCD на входном состо-
янии 0 ( , )=s a b будет иметь вид ( , )d d для некоторого числа ( )gcd ,d a b= , потому
что рано или поздно компоненты состояния процесса станут равными, а операции α
и β не изменяют наибольший общий делитель компонентов состояния. Конечный
К понятию функции как вычислительной процедуре
«Штучний інтелект» 4’2010 25
1-З
результат вычисления формирует операция проектирования 1pr ( ),d d d= . Таким об-
разом, *( , ) gcd( , )GCD a b a b= .
Отдельного рассмотрения заслуживают инициальные процедуры, которые за-
канчивают вычисления исключительно по временным критериям. В этом случае
могут даже не фиксироваться заключительные состояния процедуры, а вместо них
на состояниях, например, вводится определенный частичный порядок и как резуль-
тат вычисления (в том числе и бесконечного) рассматривается наименьшая верхняя
грань его состояний. Другой вариант составляют процедуры, которые заканчивают
работу в определенный момент времени τ или после некоторого момента времени
τ и т.д. Функции P и Q называются эквивалентными (P Q≡ ), если их графики *P
и *Q эквивалентные. Состояние функции ( )0 0, ,τfinP S S назовем допустимым, если
оно встречается среди состояний некоторого результативного ее вычисления. Поло-
жим accS S⊆ – подмножество всех допустимых состояний функции ( )0 0, ,τfinP S S .
Для соответствий, вычисляемых функцией, состояния за пределами подмножества
accS несущественны. Пусть ( )0 0, ,′ ′ ′ τfinP S S – функция над пространством Π′ с мно-
жеством состояний accS и ограниченными на Π′ элементарными операциями, функ-
цией перехода, входными и заключительными состояниями функции P . Очевидно,
что процедуры P и P ′ эквивалентные. Функция, все состояния которой допустимы,
называется приведенной. Например, ранее определенная функция GCD является
приведенной.
При конструировании функций важно иметь специальные операции, которые
из одних функций строят другие, более сложные. Такие операции называются ком-
позициями. Наиболее известны три из них – последовательное выполнение, развет-
вление и итерация. Они называются регулярными и входят в состав композиций сис-
тем алгоритмических алгебр. Имеет место
Теорема 1 (замкнутости). Класс функций замкнут относительно регулярных
композиций.
Доказательство теоремы приведено [1]
2 Абстрактные алгоритмы
При определении понятия алгоритма мы хотим отойти от принятой в теории
алгоритмов практики определять какой-то конкретный класс алгоритмов (например,
машины Тьюринга или алгоритмы Маркова) и, ссылаясь на его универсальность,
связывать с ним общее понятие алгоритма. Такой подход, имея определенный смысл
в мировоззренческом отношении, к сожалению, почти ничего не дает непосред-
ственно программированию. Поэтому мы предлагаем другой подход, опирающийся
на понятие функции и её реализацию.
Когда говорят о реализации класса функций или отдельной функции, то имеют
в виду, что существует исполнитель (реальный или гипотетический), который спо-
собен воспринимать функции и производить в них конкретные вычисления: фикси-
ровать отдельные состояния, находить значения функции управления на каждом
шаге вычисления и выполнять соответствующие элементарные преобразования. Для
представления процедур и их компонентов исполнитель имеет специальный внут-
ренний язык программирования (далее – просто внутренний язык). Он не обязательно
вербальный, но обязательно финитный – считается, что исполнитель способен вос-
принимать и оперировать только конечными с точки зрения описания объектами.
Зубенко В.В.
«Искусственный интеллект» 4’2010 26
1-З
Объекты внутренних языков исполнителей, которые реализуют функции, будем
называть конструктивными, представленные в них функции – абстрактными алго-
ритмами (А-алгоритмами), а сами внутренние языки – алгоритмическими язы-
ками1.
Таким образом, конструктивность объекта имеет смысл только в контексте неко-
торого исполнителя и его алгоритмического языка, а функция-процедура становится
А-алгоритмом только при условии, что для неё существует конкретный исполнитель.
На выбранном нами пропозициональном уровне абстракции не рассматривается вну-
тренняя структура самих исполнителей. Мы только знаем, что исполнитель или вос-
принимает конструктивный объект как входящий, или строит его с помощью конеч-
ного числа элементарных преобразований в процессе вычислений.
Как пример класса А-алгоритмов можно привести обычные арифметические
выражения и общие интерпретированные Ω -термы. Каждый из них определяет неко-
торую функцию-процедуру для вычисления значений. Исполнителем таких А-алго-
ритмов может быть, например, лицо, умеющее анализировать структуру термов и
выражений и выполнять соответствующие операции и предикаты. Можно пойти еще
дальше и рассмотреть все интерпретированные регулярные выражения над сигнатурой Ω .
Соответствия *A и **A , вычисляемые А-алгоритмом (его графики), называются
алгоритмически вычисляемыми. Как и процедуры, А-алгоритмы могут быть детер-
минированными и недетерминированными. Приведем основные свойства А-алгоритмов,
которые непосредственно вытекают из их определения.
Массовость. А-алгоритм может быть применен к любому входному состоянию.
Темпоральность. Вычисления А-алгоритма происходят во временном простран-
стве, элементы которого могут влиять на выбор преобразований текущего состояния.
Элементарность. В каждый момент времени в вычислении выполняется одна
элементарная операция из фиксированной совокупности таких операций.
Определенность. Порядок применения элементарных операций в вычислении
не является произвольным, а определяется функцией управления.
Результативность. Есть механизм завершения вычислений.
Финитность. Конечность представления А-алгоритма.
Релятивность. Относительность понятия А-алгоритма. Конструктивность А-алго-
ритма как объекта алгоритмического языка напрямую зависит от конкретного испол-
нителя. А-алгоритм для данного исполнителя не обязательно будет А-алгоритмом для
другого. Другим аспектом релятивности А-алгоритмов являются взаимоотношения
элементарных операций и исполнителя. В некоторых случаях элементарные операции
(все или их часть) могут считаться абстрактными и не подлежать исполнению. Такие
операции называются оракулами, а сами А-алгоритмы – алгоритмами с оракулами.
Как видим, А-алгоритмам присущи основные свойства классических числовых
и словарных алгоритмов [2]. Однако появились и новые специфические черты – тем-
поральность и релятивность.
В связи с релятивностью возникает задача сравнения различных классов алго-
ритмов по мощности. Будем говорить, что алгоритм 1A с множеством состояний 1S
является моделью алгоритма 2A с множеством состояний 2S относительно функции
кодирования 2 1:S Sϕ → , если для каждого из входных состояний s алгоритма 2A
выполняется: * 1 *
2 1( ) ( ( ))A s A s−= ϕ ϕ . Пусть 1K и 2K – произвольные классы алгоритмов
1 Не случайно первые языки программирования тоже назывались алгоритмическими. Например,
Алгол-60 (англ. – ALGOrithmic Language ALGOL-60).
К понятию функции как вычислительной процедуре
«Штучний інтелект» 4’2010 27
1-З
над вычислительными пространствами 1Π = 1 1,SΓ и 2Π = 2 2,SΓ соответственно.
Зафиксируем определенную функцию кодирования 2 1:S Sϕ → . Говорят, что класс
алгоритмов 1K моделирует класс алгоритмов 2K , если для каждого алгоритма с 2K
в классе 1K есть его модель. Если классы алгоритмов моделируют друг друга отно-
сительно определенных фиксированных функций кодирования, то они называются
эквивалентными относительно этих функций.
Фиксируя конкретные вычислительные пространства Π и соответствующих
исполнителей, можно получить весь спектр классических алгоритмических систем
(машины Тьюринга, алгоритмы Маркова и Колмогорова – Успенского, дискретные
преобразователи, различные классы автоматов и схем программ, формальные грам-
матики и исчисления и т.п.) [2]. Все перечисленные классы классических алго-
ритмических систем являются, как известно, эквивалентными и получили название
универсальных.
Посмотрим, например, на машины Тьюринга как на А-алгоритмы. Исполнитель
А-алгоритма A , реализующего машину Тьюринга, оперирует состояниями, изобра-
жающими машинные конфигурации. Такие состояния имеют две компоненты: пер-
вый компонент – внутреннее состояние машины, второй – подает состояние памяти
машины и имеет вид последовательности ячеек, в которой хранится слово в
алфавите X с указанной позицией рабочей ячейки. Временное пространство Γ –
натуральное. Значение функции перехода на конфигурации определяется внутрен-
ним состоянием и состоянием рабочей ячейки (рабочим состоянием). Оно никоим
образом не зависит от номера шага (временной компоненты) вычисления. Само дей-
ствие состоит в изменении исполнителем внутреннего и рабочего состояний и пози-
ции рабочей ячейки. Новой позицией может стать позиция одной из двух непосред-
ственно соседних ячеек в последовательности. Учитывая, что совокупности внутренних
состояний Q и состояний рабочей ячейки X машин Тьюринга конечны, то функцию
перехода нашей процедуры можно описать тоже конечно, например, таблично как
соответствие δ × → × × −: { 1,0,1}Q X Q X , которое по текущим внутренним и рабо-
чим состояниями определяет новые их значения и новую позицию рабочей ячейки.
Ноль означает, что она не меняется, –1 означает сдвиг влево, а 1 – сдвиг вправо.
Выделяется начальный ∈0q Q и совокупность заключительных ⊆F Q внутренних
состояний. Совокупности 0S начальных и finS заключительных состояний А-алго-
ритма составляют множества × *
0{ }q X и × *F X соответственно. Результатом вычи-
сления процедуры P на начальном состоянии есть состояние ее рабочей ленты в
заключительном состоянии вычисления. Учитывая, что начальное внутреннее со-
стояние А-алгоритма фиксировано, то можно полагать, что он вычисляет словарную
функцию *A на множестве рабочих состояний *X .
Пусть { ,#}X a= и *{ }F q= . Табл. 1 задает А-алгоритм для машины Тьюринга,
которая вычисляет функцию ( # )n m n mf a a a += , где ,n m – произвольные натураль-
ные числа:
Q X { 1,0,1}Q X× × −
0q a 1( , ,1)q ε
0q # *( , ,0)q ε
1q a 1( , ,1)q a
1q # *( , ,0)q a
Зубенко В.В.
«Искусственный интеллект» 4’2010 28
1-З
Стоит отметить, что машины Тьюринга, как и другие классические алгоритмы,
являются сугубо автоматными – выбор следующего действия в них не зависит от
текущего момента времени.
Для А-алгоритмов тоже имеет место
Теорема 2 (замкнутости). Класс А-алгоритмов замкнут относительно регуляр-
ных композиций.
Доказательство. Следует из доказательства Теоремы 1.
Как и классические алгоритмы, А-алгоритмы могут использоваться для опи-
сания множеств. Подмножество состояний R S⊆ называется разрешимым (частично
разрешимым), если существует А-алгоритм A , график которого совпадает с харак-
теристической функцией Rχ (частичной характеристической функцией Rχ ) подмно-
жества R .
А-алгоритмы вычисляют и временные операторы, которые отображают их вход-
ные конфигурации в заключительные, поэтому они могут служить основой для уточ-
нения и общего понятия вычислимого временного оператора в произвольной области.
Этот путь прямой и не опирается на те или иные универсальные числовые или сло-
варные модели алгоритмов.
3 Табличные алгоритмы
Важный класс А-алгоритмов составляют табличные А-алгоритмы. Пусть времен-
ное пространство Γ изоморфно аддитивной группе Z целых чисел и пусть A –
произвольная процедура над пространством =Π ,Z S . Факторизуем функцию управ-
ления по обоим аргументам. Зафиксируем некоторую часовую константу 0k ≥ и
некоторое отношение эквивалентности π на состояниях с S . Будем говорить, что
функция управления δ периодичная по модулю отношения π с периодом k (или
просто k -периодичная по модулю π), если для всех эквивалентных состояний p и
s и произвольного момента времени t Z∈ : ( , ) ( , )t p t k s+δ = δ . Функция управления
δ – просто периодичная по модулю π, если она k -периодичная по модулю π для
некоторого k . Функция-процедура с периодичной функцией управления, а эквива-
лентность π – конечный индекс | |π (конечное число классов эквивалентности) и
разрешимые классы, называется табличным алгоритмом. Табличные алгоритмы
(T − алгоритмы) можно задавать двумерными таблицами размером | |k× π : первое
измерение отвечает числам от 0 до 1k − , второе – классам эквивалентности π , а в клет-
ках таблицы размещены значения функции управления. Традиционные алгорит-
мические системы, как правило, являются табличными как А-алгоритмы. А поскольку
они являются автоматными, то и – 1 – периодичными по модулю равенства. Это вид-
но на примере конечных и МП-автоматов. Машина Тьюринга – табличный алгоритм:
два её состояния эквивалентны, если их внутренние состояния и состояния рабочих
ячеек на лентах совпадают.
Для табличных алгоритмов тоже имеет место
Теорема 3 (замкнутости). Класс табличных алгоритмов замкнут относительно
всех регулярных композиций.
Доказательство приведено в [2].
Проблема анализа А-алгоритмов, которые принадлежат некоторому классу K ,
состоит в поиске тех или иных общих алгебраических форм представления для их
графиков. Следующая теорема решает эту проблему для табличных алгоритмов. Кон-
К понятию функции как вычислительной процедуре
«Штучний інтелект» 4’2010 29
1-З
фигурации называются соседними, если они принадлежат одному временному периоду
(их временные компоненты 1t та 2t удовлетворяют условию: ktkt ÷=÷ 21 , где ÷ –
операция целочисленного деления).
Теорема 4 (о регуляризации графиков табличных алгоритмов). Пусть A –
табличный алгоритм над некоторым вычислительным пространством =Π ,Z S .
Тогда его график регулярен относительно базиса, который состоит из элементарных
операций ∆ , характеристических предикатов классов разбиения отношения π , мно-
жеств входных и заключительных состояний, а также предиката временного со-
седства конфигураций.
Доказательство приведено в [3].
Заключение
В работе предложено формальное уточнение общего понятия функции как вычис-
лительной процедуры. Это позволяет уточнить и общее понятие абстрактного алго-
ритма – оно становится его производным (сужением). Рассмотрен важный класс
А-алгоритмов – табличные алгоритмы. Все основные классические алгоритмические
и автоматные системы являются табличными алгоритмами. Показано, что функции и
абстрактные алгоритмы замкнуты относительно регулярных композиций. Для таб-
личных алгоритмов дано общее решение проблемы анализа – показано, что их графики
есть регулярными функциями относительно одного довольно естественного базиса.
Литература
1 Зубенко В.В. Про темпоральні процедури та алгоритми / В.В. Зубенко // Вісн. КНУ ім. Тараса Шевченка.
Серія: Кібернетика. – 2005. – № 6. – С. 20-26.
2 Успенский В.А. Теория алгоритмов: основные открытия и приложения / В.А. Успенский, А.Л. Семенов. –
М. : Наука. Гл. ред. физ.-мат. лит., 1987. – 288 с.
3 Зубенко В.В. Періодичні темпоральні алгоритми / В.В. Зубенко // Вісн. Київ. ун-ту. Серія: Кібернетика. –
2006. – № 7. – С. 19-23.
4 Зубенко В.В. Про регуляризацію монотонних табличних алгоритмів / В.В. Зубенко // Штучний інтелект. –
2006. – № 3.
В.В. Зубенко
До поняття функції як обчислювальної процедури
Робота присвячена формальному уточненню загального поняття функції як обчислювальної процедури.
При цьому вибирається гранично можливий рівень абстракції, який умовно можна було б назвати
пропозиційним: усі об’єкти трактуються виключно як теоретико-множинні «чорні скриньки». Поняття
функції-процедури дозволяє уточнити і загальне поняття абстрактного алгоритму – воно стає його
похідним. Розглядаються загальні властивості таких алгоритмів. Показано, що функції-процедури і
абстрактні алгоритми замкнені відносно регулярних композицій. Для табличних алгоритмів подано
загальний розв’язок проблеми аналізу.
V.V. Zubenko
To the Concept of Function as a Computational Procedure
The research is dedicated to the formal refinements of general notion of function as a computational
procedure. The strongest level of abstraction is adopted: all objects are treated as “black box”. The notion of
function as a procedure makes it possible to revise generic notion of abstract algorithm, as it becomes it’s
derivative. The general properties of such algorithms are considered. It is proven that classes of function-
procedures and abstract algorithms are closed under regular compositions. A generic solution for the tabulated
algorithms analysis problem is proposed.
Статья поступила в редакцию 19.07.2010.
|
| id | nasplib_isofts_kiev_ua-123456789-58341 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T16:15:37Z |
| publishDate | 2010 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Зубенко, В.В. 2014-03-22T15:47:42Z 2014-03-22T15:47:42Z 2010 К понятию функции как вычислительной процедуре / В.В. Зубенко // Штучний інтелект. — 2010. — № 4. — С. 20-29. — Бібліогр.: 4 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/58341 004.8:519.254 Работа посвящена формальному уточнению общего понятия функции как вычислительной процедуры. При этом выбирается предельно возможный уровень абстракции, который условно можно было бы назвать пропозициональным: все объекты трактуются исключительно как теоретико-множественные «черные ящики». Понятие функции-процедуры позволяет уточнить и общее понятие абстрактного алгоритма – оно становится его производным. Рассматриваются общие свойства таких алгоритмов. Показано, что функции-процедуры и абстрактные алгоритмы замкнуты относительно регулярных композиций. Для табличных алгоритмов дано общее решение проблемы анализа. Робота присвячена формальному уточненню загального поняття функції як обчислювальної процедури. При цьому вибирається гранично можливий рівень абстракції, який умовно можна було б назвати пропозиційним: усі об’єкти трактуються виключно як теоретико-множинні «чорні скриньки». Поняття функції-процедури дозволяє уточнити і загальне поняття абстрактного алгоритму – воно стає його похідним. Розглядаються загальні властивості таких алгоритмів. Показано, що функції-процедури і абстрактні алгоритми замкнені відносно регулярних композицій. Для табличних алгоритмів подано загальний розв’язок проблеми аналізу. The research is dedicated to the formal refinements of general notion of function as a computational procedure. The strongest level of abstraction is adopted: all objects are treated as “black box”. The notion of function as a procedure makes it possible to revise generic notion of abstract algorithm, as it becomes it’s derivative. The general properties of such algorithms are considered. It is proven that classes of functionprocedures and abstract algorithms are closed under regular compositions. A generic solution for the tabulated algorithms analysis problem is proposed ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Концептуальные проблемы создания систем искусственного интеллекта К понятию функции как вычислительной процедуре До поняття функції як обчислювальної процедури To the Concept of Function as a Computational Procedure Article published earlier |
| spellingShingle | К понятию функции как вычислительной процедуре Зубенко, В.В. Концептуальные проблемы создания систем искусственного интеллекта |
| title | К понятию функции как вычислительной процедуре |
| title_alt | До поняття функції як обчислювальної процедури To the Concept of Function as a Computational Procedure |
| title_full | К понятию функции как вычислительной процедуре |
| title_fullStr | К понятию функции как вычислительной процедуре |
| title_full_unstemmed | К понятию функции как вычислительной процедуре |
| title_short | К понятию функции как вычислительной процедуре |
| title_sort | к понятию функции как вычислительной процедуре |
| topic | Концептуальные проблемы создания систем искусственного интеллекта |
| topic_facet | Концептуальные проблемы создания систем искусственного интеллекта |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/58341 |
| work_keys_str_mv | AT zubenkovv kponâtiûfunkciikakvyčislitelʹnoiprocedure AT zubenkovv doponâttâfunkcííâkobčislûvalʹnoíproceduri AT zubenkovv totheconceptoffunctionasacomputationalprocedure |