Jagiellonian University Repository

The greatest fixed point in iterative programs.

pcg.skipToMenu

The greatest fixed point in iterative programs.

Show full item record

dc.contributor.advisor Zaionc, Marek [SAP11009271] pl
dc.contributor.author Tokarz, Mateusz pl
dc.date.accessioned 2020-10-20T20:12:53Z
dc.date.available 2020-10-20T20:12:53Z
dc.date.submitted 2020-09-10 pl
dc.identifier.uri https://ruj.uj.edu.pl/xmlui/handle/item/249650
dc.language eng pl
dc.title The greatest fixed point in iterative programs. pl
dc.title.alternative Największy punkt stały w programach iteracyjnych pl
dc.type master pl
dc.abstract.pl Celem tej pracy jest zbadanie ograniczenia górnego na procedurę iteracji w dół w programach w Prologu. W głównej części pracy pokazujemy schemat konstrukcji programów, które iterują się przez a kroków, dla każdej rekurencyjnej liczby porządkowej a. Następnie używamy notacji porządkowej Kleene'go, aby skonstruować program iterujący się przez dokładnie ωC−K kroków. Ostatnia część głównej sekcji pracy pokazuje ograniczenie górne na iterację w dół - ωC−K. Dowód opiera się na ograniczeniu na ekspresywność definicji induktywnych, które mogą być reprezentowane jako pewne formuły arytmetyczne. W ostatniej części pracy badamy liczby porządkowe iteracji w dół dla programów Prologa, których klauzule nie posiadają operatora koniunkcji - ograniczone programy. Pokazujemy ograniczenie górne na ograniczenie programy, w których występują jedynie unarne predykaty. Prezentujemy kilka narzędzi ,powstałych w procesie próby dowodu, że ograniczenie na liczby porządkowe iteracji w dół ograniczonych programów to ω^ω - hipoteza na końcu tej pracy. pl
dc.abstract.en The aim of this document is the examination of the upper bound on downwarditeration procedure in Prologue programs. In the main section of this documentwe provide a schema for the construction of programs that downward iterate forexactly α steps, where α is any recursive ordinal. Later, we use Kleene’s ordinalnotation to construct the program which iterates for exactly ωC−K steps. Thelast part of the main section provides an upper bound on any downward ordinal for Prologue program - ωC−K. It is based on the bound on the expression strength of inductive definitions that might be represented as some arithmetical formulas. In the last section of this document we are studying downward ordinals forPrologue programs such that their clauses do not contain conjunction operator- limited programs. We give an upper bound on limited programs with onlyunary predicates. We also present a couple of tools that were created while attempting to prove that the upper bound on the downward ordinalfor all limited programs is ω^ω - conjecture at the end of this paper. pl
dc.subject.pl Prolog, Liczby porządkowe, Liczba porządkowa Churcha-Kleene'go, Rekurencyjne liczby porządkowe, Logika pierwszego rzędu, Notacja porządkowa Kleene'go, Formuła arytmetyczna, Hierarchia arytmetyczna, Definicje induktywne, Twierdzenie Knastera-Tarskiego, Funkcje rekurencyjne, Relacja dobrze ufundowana, Unifikacja pl
dc.subject.en Prologue, Ordinal numbers, Church-Kleene ordinal, Recursive ordinals, First order logic, Kleene ordinal notation, Arithmetical formula, Arithmetical hierarchy, Inductive definitions, Knaster-Tarski theorem, Recursive functions, Well-founded order, Unification pl
dc.contributor.reviewer Zaionc, Marek [SAP11009271] pl
dc.contributor.reviewer Wrona, Michał pl
dc.affiliation Wydział Matematyki i Informatyki pl
dc.identifier.project APD / O pl
dc.identifier.apd diploma-144408-212926 pl
dc.contributor.departmentbycode UJK/WMI2 pl
dc.area obszar nauk ścisłych pl
dc.fieldofstudy informatyka analityczna pl


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)