[feed] pefprints@pef.uni-lj.si | [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0 |
  Logo Login | Create Account

Undecidable problems in the theory of computation

Luka Viktor Rogač (2017) Undecidable problems in the theory of computation. MSc thesis.

[img] PDF
Download (1139Kb)


    In this master thesis the hierarchy of automata and related languages is presented. First, the concepts, associated with recognizable and unrecognizable languages are introduced, followed by further introduction of a subclass of recognized languages; these are decidable languages. By means of decidable and undecidable languages the concept of decidable and undecidable problems was translated and strictly defined. The following examples of undecidable problems are described in detail: the Turing's halting problem, the Post correspondence problem, the busy beaver problem and the Hilbert's tenth problem. In the frame of the master thesis, a web application which is searching for concrete solutions of the Post correspondence problem, was developed. The programming environment of the application and the interpretation of the source code with instructions for its using are described in detail. An example for the usage of the application at teaching, for example in a computer club, is presented.

    Item Type: Thesis (MSc thesis)
    Keywords: hierarchy of automata and related languages, recognizable languages, decidable languages, decidable problems, the Turing's halting problem, the Post correspondence problem, the Busy beaver problem, the Hilbert's 10th problem
    Number of Pages: 50
    Language of Content: Slovenian
    Mentor / Comentors:
    Mentor / ComentorsIDFunction
    prof. dr. Aleksander MalničMentor
    doc. dr. Rok PožarComentor
    Link to COBISS: http://www.cobiss.si/scripts/cobiss?command=search&base=50126&select=(ID=11768905)
    Institution: University of Ljubljana
    Department: Faculty of Education
    Item ID: 4835
    Date Deposited: 09 Oct 2017 17:14
    Last Modified: 09 Oct 2017 17:14
    URI: http://pefprints.pef.uni-lj.si/id/eprint/4835

    Actions (login required)

    View Item