Topic 6

Lesson 6. Abstract Post Machine. Turing Machine. Markov's Normal Algorithms.

Objective: involves a hierarchical acquisition of skills, ranging from understanding the basics of abstract computational models to being able to compare their equivalence and assess their limitations. At the lowest level, Knowing/Remembering, the student must define the concept of an abstract machine (such as a Post machine and a Turing machine), list the main components that make up a Turing machine (tape, head, control device), and state the essence of the Post Thesis and the Turing Thesis. The next level, Understanding, requires the student to explain the need to create abstract computing machines to formalize the concept of an algorithm, interpret the consequences of the fact that there are problems for which an algorithm cannot be constructed at all, and formulate the difference between a Turing machine and Normal Markov algorithms (simplification of action vs. simplification of control logic). Level Applying (3) requires the student to demonstrate practical application of knowledge, including applying a command from the E. Post machine to perform a simple operation for processing markers on a tape, and solving a problem to determine a class of algorithmically intractable problems using abstract machines. Level Four, Analyzing, requires the student to compare the architectural approaches of the Post machine, the Turing machine, and normal Markov algorithms, distinguish the essence of a universal Turing machine (which imitates the work of any other machine) from a regular one, and analyze why the Turing machine and normal Markov algorithms are considered equivalent in computational power. At the fifth level, Evaluating, the student must justify the importance of the Church-Turing conjecture as fundamental to modern computer science, criticize the limitations of the Post machine compared to the Turing machine in solving complex problems, and evaluate the importance of the universal Turing machine for the development of the concept of programmable computers. At the highest level, Creating, the student must design a set of instructions or commands for an abstract Post machine to implement a specific algorithm, and design a formal description of a Normal Markov algorithm for transforming certain sequences of characters.