Узагальнена схема обчислення індуктивної функції.

Будується індуктивне розширення F вихідної функції, яке дозволяє ціною збільшення запам'ятовуваної інформації про ланцюг ω (в F(ω) інформації більше ніж в f (ω)) застосуємо схему обчислення індуктивної функції до F(ω), а потім просто знайти .

Нехай і - два індуктивних розширення функції . Будемо говорити, що , якщо таке, що .

Означення 10 .3 Мінімальним індуктивним розширенням функції f: , називається індуктивне розширення таке, що 1) ( - сюр’єктивне); 2) для будь-якого індуктивного розширення F функції f виконано .

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

Для будь-якої функції на просторі послідовностей існує і єдине (у певному сенсі), її мінімальне індуктивне розширення. Доведення цього факту проведемо в два етапи, спочатку переконавшись у єдиності розширення.

Теорема 10.2 Мінмальне індуктивне розширення будь-якої функції f: , єдине з точністю до ізоморфізму.

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

Візьмемо довільний елемент . Із сюр’єктивності випливає, що знайдеться ланцюг , такий, що і тому . Отримана рівність показує, що \ - тотожне відображення. Розглядаючи довільні елементи , аналогічно отримуємо, що , що і закінчує доведення теореми.

Критерій мінімальності

Перед тим, як сформулювати критерій мінімальності, доведемо існування мінімального індуктивного розширення.

Теорема 10.3 Мінімальне індуктивне розширення для будь-якої функції f: існує.

Доведення. Для доведення теореми побудуємо в три етапи канонічне мінімальне індуктивне розширення заданої функції f.

Перший етап. Розглянемо на множині ланцюгів бінарне відношення , задане формулою , і покажемо, що

1) - відношення еквівалентності на ;

2) ;

3) .

Рефлексивність, симетричність і транзитивність відношення випливають відповідно з рефлексивності, симетричності і транзитивності відношень рівності.

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

Властивість 3) негайно випливає із визначення відношення , якщо в якості взяти пустий ланцюг .

Другий етап. Побудуємо простір та відображення В якості візьмемо фактор множину (множина класів еквівалентності) , що можна зробити в силу властивості 1). Домовимося позначати клас еквівалентності, який містить ланцюг через і визначимо відображення формулою .

Переписавши властивість 2) в еквівалентному вигляді

, з критерію індуктивності робимл висновок, що відображення - індуктивне.

Покажемо, що є індуктивним розширенням вихідної функції .

Визначимо проекцію формулою . Коректність цього визначення випливає із властивості 3) - якщо два ланцюжки належать одному класу єквівавлентності, то значення функції на них співпадає.

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

Третий етап. Нам залишилося показати, що побудоване канонічне індуктивне розширення є мінімальним.

Сюр'єктивність випливає безпосередньо із його побудови, тому що кожен клас еквівалентності не порожній.

Припустимо наступне, що існує – інше індуктивне розширення вихідної функції , тоді для завершення доведення теореми нам необхідно показати, що

Визначимо проекцію формулою , де – один із праобразів елемента при відображенні . Перевіримо коректність даного визначення.

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

Рівність для довільного ланцюга показує, що . Теорема повністю доведена.

Побудоване в процесі доведення цієї теореми канонічне індуктивне розширення дозволяє переконатися в істинності наступного критерію мінімальності.

Теорема 10.4 Критерій мінімальності. Індуктивне розширення функції – мінімальне

()

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

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

Критерій буде доведений, якщо ми покажемо, що відображення – біекція.

Сюр'єктивність витікає із сюр'єктивності та , а ін'єктивність доводиться наступними судженнями. Розглянемо різні та, скориставшись сюр'єктивністю , знайдемо ланцюги із такі, що

. Так як , то в силу даної нам умови , що еквівалентно нерівності .

Отже, відображення різні перетворює в різні ж

, що і вимагалося довести.

Доведемо, що функція , визначена за формулою

де , є мінімальним індуктивним розширенням для середнє арифметичне елементів послідовності. Для доведення сюр'єктивності функції F предявимо прообраз довільного елемента . Ним буде ланцюг з n елементів, перший з яких дорівнює s, а решта – нулеві. Для того щоб перевірити другу умову критерію мінімальності, необхідно переконатися в тому, що

та або або . Якщо для порожнього ланцюга виконується , то все доведено. Інакше маємо . Візьмемо тепер в якості одноелементний ланцюг 0. Припустивши що для нього із системи

отримаємо , що суперечить припущенню. Це завершує доведення мінімальності F.

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

Теорема 10.5 Для довільної функції на просторі послідовностей існує єдиний з точністю до ізоморфізму однопрохідний алгоритм з мінімальною ємнісною складністю.