Arcabouço didático da máquina de turing

Abstract

The Turing Machine (TM), developed in the first half of the last century, still maintains an important relevance for the courses of computer science, logic and mathematics, as a reference tool to establish the extent and limits of automatic resolution of problems. Its concept is attached to the renowned "Church-Turing Thesis", a collection of works on functions whose values are effectively calculable; that is, those functions that can be solved by (computable) algorithms. The MT remains the main model preferred by theorists who investigate issues concerning various problems in computer theory; in particular, the theories of decidability and computational complexity. In this context, a TM framework becomes a useful tool for learning such concepts, since it enables the learner, the construction of the most diverse TMs and the verification of the most varied programs built for them, completely independent of a supervisor.