Evolutionary Synthesis of the Turing Machine's Rules

Abstract

Tato dizertační práce se věnuje možnostem využití umělé inteligence pro programování Turingova stroje. Nosným tématem je využití Diferenciální evoluce a Samo-organizujícího se migrujícího algoritmu jako vybraných metod umělé inteligence pro syntézu pravidel přechodové funkce Turingova stroje. Pravidla Turingova stroje představují program, na jehož základě Turingův stroj pracuje. Jejich návrh lze tedy považovat za formu programování tohoto stroje.Dizertační práce sestáva ze čtyř částí, které lze charakterizovat následovně. První část představuje úvod do konečných automatů, mezi které patří i Turingův stroj. Tato část je nezbytná pro pochopení mechanismů, na jejichž základě tento typ strojů pracuje. Velmi důležitá je charakterizace stroje na základě jeho formálního popisu, který je v dalších částech dizertační práce využit jako základ pro formulaci problému syntézy pravidel. Tato první část rovněž seznamuje s vybranými algoritmy umělé inteligence, tedy s Diferenciální evolucí a Samo-organizujícím se migrujícím algoritmem. Toto seznámení hraje důležitou roli pro vhodné nastavení parametrů těchto algoritmů při syntéze pravidel.Druhá část dizertační práce představuje dva navržené přístupy k syntéze (nebo také optimalizaci) pravidel Turingova stroje. Těmito přístupy jsou "klasická optimalizace" a "optimalizace po částech". Oba tyto přístupy se zásadně liší jeden od druhého. Zároveň každý z těchto přístupů má své výhody i zápory, které zároveň určují i jejich využití. V této druhé části jsou oba tyto přístupy podrobně popsány.Ve třetí části dizertační práci jsou uvedeny tři vybrané elementární problémy. Jde o unární součet, problém dělitelnosti bez zbytku celým číslem a problematika detekce prvočísla. Tyto problémy jsou využity jako vzorové úlohy pro Turingův stroj, jehož pravidla chceme zjistit pomocí navržených přistupů. Toho je následně využito pro analýzu závislosti procesu optimalizace pravidel na různém nastavení Diferenciální evoluce a Samo-organizujícího se migrujícího algoritmu. Tato analýza je zcela zásadní nejen pro tuto část dizertační práce, ale především pro následující.Poslední, čtvrtá, část dizertační práce představuje praktické využití navržených přístupů k programování Turingova stroje pomocí umělé inteligence. Za reálnou problematiku bylo zvoleno zpracování proteinů pomocí Turingova stroje. Proteiny jsou v tomto případě míněny primární proteinové struktury. Evoluční syntéza pravidel Turingova stroje je demonstrována na celkem dvanácti vybraných primárních proteinových strukturách, lišících se svou délkou. Tato problematika, jak je popsáno dále v textu, je natolik komplexní, že ji lze považovat jako dostatečný způsob ověření správné činnost přístupů k evoluční syntéze pravidel Turingova stroje, jimiž se tato dizertační práce zabývá.