Academic seminar looks at applications of the Turing Machine
João Colombo, a master’s student at IMPA, presented his thesis on Turing’s model
20/6/2025
The legacy of British mathematician Alan Turing (1912-1954) was the subject of an academic seminar held on Wednesday (18). Invited to the meeting, IMPA master’s student in Pure Mathematics João Colombo presented his thesis for his undergraduate degree in Computer Science at UFSC (Federal University of Santa Catarina) to IMPA Tech undergraduates. The work proposes a variant of the non-deterministic Turing Machine for computing mathematical functions.
The Turing Machine is a theoretical model created by the mathematician to represent the basic functioning of a computer. It consists of an infinite tape, like a memory, and a “reader” that reads and writes symbols, following specific rules. Despite being an abstract model, it is fundamental for showing the limits of computing and what can and cannot be solved by an algorithm.
Colombo’s work proposes an adaptation of the non-deterministic model, capable of exploring different paths simultaneously, but in a controlled way, guaranteeing a single correct output for each input. “It can be used to model algorithms, it’s a new way of thinking and classifying them. By analyzing the complexity of a problem, we can study it and optimize resources,” explained the master’s student.
In addition to his degree in Computer Science, Colombo has a degree in Mathematics, also from UFSC, and is currently a course assistant for Programming I at IMPA Tech. “It’s nice to be in this other place, to see the students’ difficulties and explain concepts. I really enjoy helping them understand and we learn a lot together,” he said.
The seminar was organized by IMPA Tech professor Uéverton Souza. The topic was chosen to coincide with the celebration of the birth of Alan Turing, who would have turned 113 next Monday (23). To this day, the mathematician’s legacy is fundamental to modern computing. “When Turing formulated the theory of the machine, there were no computers. The model he proposed, at first theoretical, brought to light how a machine could work so that computing could exist. The Turing Machine is the soul of modern computers,” said the professor.
Student Vinicius Prestes likes Computing and enjoyed the topic presented. “The Turing Machine is like one of the great foundations of the area, it shows how algorithms can act on values they receive to return other results. It’s a primitive example, but very complete. Colombo proposed a new model of the Machine, which can’t solve more problems, but which solves problems more efficiently, more quickly.”
Wednesday’s lecture was the last seminar of this semester, bringing the cycle of complementary activities to a close for Professor Uéverton, who highlighted the interdisciplinary nature of the meetings. “The students have been able to see all the emphases mixed together and applied in a practical way. In addition, we exchanged experiences with other institutions, such as UFF, UERJ, FGV and CBPF. We were able to mix a lot of institutions and show the students what they can do after graduation, either post-graduation or in the job market. I certainly intend to do it again next semester, broadening the range of topics.”
Read more: ‘I’ve never been in such a good environment’, says IMPA Tech graduate
See also: Common Root: project brings students together in conversation circles
