Construção e Análise de uma Máquina de Turing para Ordenação de Vetores Binários: Uma Abordagem para Disciplinas de Teoria da Computação
Resumo
Este artigo apresenta uma Máquina de Turing para a ordenação de vetores binários via Selection Sort, validada no simulador JFLAP. Diferente de operações aritméticas, a manipulação de estruturas de dados revelou um custo computacional não linear severo: a ordenação de apenas 127 elementos exigiu mais de 32 milhões de transições. A implementação, composta por 133 estados e segmentação de fita, atua como recurso pedagógico para demonstrar visualmente a distinção entre computabilidade e eficiência, evidenciando as limitações práticas do acesso sequencial em contraste com modelos de memória de acesso aleatório.Referências
Bressoud, T. C. and Thomas, G. (2019). A novel course in data systems with minimal prerequisites. In Proceedings of the 50th ACM Technical Symposium on Computer Science Education, pages 15–21.
Campano Junior, M. M., Barbosa, C. R., Felinto, A., and Aylon, L. R. (2022). Multiplicando números binários com máquinas de turing: Interdisciplinaridade no ensino de computação. In Anais do XXXIII Simpósio Brasileiro de Informática na Educação, pages 1313–1323, Porto Alegre, RS, Brasil. SBC.
Campano Junior, M. M., Felinto, A. S., Sachs, C. R., and de Barbosa, C. (2019). Um merge entre máquina de turing e operações matemáticas em binário no ensino de linguagens formais e autômatos. In Anais do XXIV Congresso Internacional de Informática Educativa. Nuevas Ideas en Informática Educativa, Volumen 15, pages 78–83.
Cormen, T., Leiserson, C., Rivest, R., and Stein, C. (2012). Algoritmos-teoria e prática (3a. ediçao). Editora Campus.
Diverio, T. A. and Menezes, P. B. (2011). Teoria da Computação: Máquinas Universais e Computabilidade Volume 5 da Série Livros Didáticos Informática UFRGS, volume 5. Bookman Editora.
Ferreira, R., Canesche, M., and Penha, J. (2023). Google colab para ensino de computação. In Anais Estendidos do III Simpósio Brasileiro de Educação em Computação, pages 46–47. SBC.
Fukao, A. T., Colanzi, T. E., Martimiano, L. A., and Feltrim, V. D. (2023). Estudo sobre evasão nos cursos de computação da universidade estadual de maringá. In Anais do III Simpósio Brasileiro de Educação em Computação, pages 86–96. SBC.
Hopcroft, J. E., Motwani, R., and Ullman, J. D. (2001). Introduction to automata theory, languages, and computation. Acm Sigact News, 32(1):60–65.
JFLAP (2026). Jflap version 7.1. [link] Acessado em março 2026.
Junior, B. A., Cavalheiro, S. A., and Foss, L. (2021). Theoretical computer science in basic education: A systematic review. In Anais do VI Workshop-Escola de Informática Teórica, pages 133–140. SBC.
Mioni, J. and Barbosa, C. (2022). Ferramentas para o aprendizado de linguagens formais e autômatos. In Anais Estendidos do XXI Simpósio Brasileiro de Jogos e Entretenimento Digital, pages 969–978, Porto Alegre, RS, Brasil. SBC.
Mundim, P., Silva, T., e Silva, G. B., and Barbosa, D. (2025). Evasão em cursos superiores na área de computação: Um mapeamento sistemático da literatura. In Anais do XXXIII Workshop sobre Educação em Computação, pages 1055–1067, Porto Alegre, RS, Brasil. SBC.
Oda, M., Noborimoto, Y., and Horita, T. (2021). International trends in k-12 computer science curricula through comparative analysis: Implications for the primary curricula. International Journal of Computer Science Education in Schools, 4(4):n4.
Paiva, P., Souza, M., and Terra, R. (2023). Ferramentas de apoio para a disciplina de linguagens formais e autômatos: uma proposta de uso. In Anais do XXXIV Simpósio Brasileiro de Informática na Educação, pages 1698–1709, Porto Alegre, RS, Brasil. SBC.
Pardalos, P. M. and Rajasekaran, S. (1999). Data Structures and Algorithms. John Wiley Sons, Ltd.
Sano, J., Yamamoto, N., and Ueda, K. (2023). Type checking data structures more complex than trees. Journal of information processing, 31:112–130.
Silva, J., Cavalheiro, S., and Foss, L. (2024). Automata theory in computing education: A systematic review. In Anais do XXXV Simpósio Brasileiro de Informática na Educação, pages 301–313, Porto Alegre, RS, Brasil. SBC.
Souza, , Matos, E., Santos, D., and Sousa, R. (2016). Recursos computacionais para suporte ao ensino de teoria da computação, linguagens formais e autômatos. In Anais do XXIV Workshop sobre Educação em Computação, pages 2373–2382, Porto Alegre, RS, Brasil. SBC.
Vieira, N. J. (2006). Introdução aos fundamentos da computação: linguagens e máquinas. Pioneira Thomson Learning.
Walker, D. and Morrisett, G. (2000). Alias types for recursive data structures. In International Workshop on Types in Compilation, pages 177–206. Springer.
Zendler, A., Klaudt, D., and Seitz, C. (2014). Empirical determination of competence areas to computer science education. Journal of Educational Computing Research, 51(1):71–89.
Zendler, A., Klaudt, D., Spannagel, C., and Reuter, T. (2013). Semantic categorization of content and process concepts relevant to computer science education. International Journal of Research Studies in Computing, 2(1):3–10.
Zendler, A., Seitz, C., and Klaudt, D. (2016). Process-based development of competence models to computer science education. Journal of Educational Computing Research, 54(4):563–592.
Campano Junior, M. M., Barbosa, C. R., Felinto, A., and Aylon, L. R. (2022). Multiplicando números binários com máquinas de turing: Interdisciplinaridade no ensino de computação. In Anais do XXXIII Simpósio Brasileiro de Informática na Educação, pages 1313–1323, Porto Alegre, RS, Brasil. SBC.
Campano Junior, M. M., Felinto, A. S., Sachs, C. R., and de Barbosa, C. (2019). Um merge entre máquina de turing e operações matemáticas em binário no ensino de linguagens formais e autômatos. In Anais do XXIV Congresso Internacional de Informática Educativa. Nuevas Ideas en Informática Educativa, Volumen 15, pages 78–83.
Cormen, T., Leiserson, C., Rivest, R., and Stein, C. (2012). Algoritmos-teoria e prática (3a. ediçao). Editora Campus.
Diverio, T. A. and Menezes, P. B. (2011). Teoria da Computação: Máquinas Universais e Computabilidade Volume 5 da Série Livros Didáticos Informática UFRGS, volume 5. Bookman Editora.
Ferreira, R., Canesche, M., and Penha, J. (2023). Google colab para ensino de computação. In Anais Estendidos do III Simpósio Brasileiro de Educação em Computação, pages 46–47. SBC.
Fukao, A. T., Colanzi, T. E., Martimiano, L. A., and Feltrim, V. D. (2023). Estudo sobre evasão nos cursos de computação da universidade estadual de maringá. In Anais do III Simpósio Brasileiro de Educação em Computação, pages 86–96. SBC.
Hopcroft, J. E., Motwani, R., and Ullman, J. D. (2001). Introduction to automata theory, languages, and computation. Acm Sigact News, 32(1):60–65.
JFLAP (2026). Jflap version 7.1. [link] Acessado em março 2026.
Junior, B. A., Cavalheiro, S. A., and Foss, L. (2021). Theoretical computer science in basic education: A systematic review. In Anais do VI Workshop-Escola de Informática Teórica, pages 133–140. SBC.
Mioni, J. and Barbosa, C. (2022). Ferramentas para o aprendizado de linguagens formais e autômatos. In Anais Estendidos do XXI Simpósio Brasileiro de Jogos e Entretenimento Digital, pages 969–978, Porto Alegre, RS, Brasil. SBC.
Mundim, P., Silva, T., e Silva, G. B., and Barbosa, D. (2025). Evasão em cursos superiores na área de computação: Um mapeamento sistemático da literatura. In Anais do XXXIII Workshop sobre Educação em Computação, pages 1055–1067, Porto Alegre, RS, Brasil. SBC.
Oda, M., Noborimoto, Y., and Horita, T. (2021). International trends in k-12 computer science curricula through comparative analysis: Implications for the primary curricula. International Journal of Computer Science Education in Schools, 4(4):n4.
Paiva, P., Souza, M., and Terra, R. (2023). Ferramentas de apoio para a disciplina de linguagens formais e autômatos: uma proposta de uso. In Anais do XXXIV Simpósio Brasileiro de Informática na Educação, pages 1698–1709, Porto Alegre, RS, Brasil. SBC.
Pardalos, P. M. and Rajasekaran, S. (1999). Data Structures and Algorithms. John Wiley Sons, Ltd.
Sano, J., Yamamoto, N., and Ueda, K. (2023). Type checking data structures more complex than trees. Journal of information processing, 31:112–130.
Silva, J., Cavalheiro, S., and Foss, L. (2024). Automata theory in computing education: A systematic review. In Anais do XXXV Simpósio Brasileiro de Informática na Educação, pages 301–313, Porto Alegre, RS, Brasil. SBC.
Souza, , Matos, E., Santos, D., and Sousa, R. (2016). Recursos computacionais para suporte ao ensino de teoria da computação, linguagens formais e autômatos. In Anais do XXIV Workshop sobre Educação em Computação, pages 2373–2382, Porto Alegre, RS, Brasil. SBC.
Vieira, N. J. (2006). Introdução aos fundamentos da computação: linguagens e máquinas. Pioneira Thomson Learning.
Walker, D. and Morrisett, G. (2000). Alias types for recursive data structures. In International Workshop on Types in Compilation, pages 177–206. Springer.
Zendler, A., Klaudt, D., and Seitz, C. (2014). Empirical determination of competence areas to computer science education. Journal of Educational Computing Research, 51(1):71–89.
Zendler, A., Klaudt, D., Spannagel, C., and Reuter, T. (2013). Semantic categorization of content and process concepts relevant to computer science education. International Journal of Research Studies in Computing, 2(1):3–10.
Zendler, A., Seitz, C., and Klaudt, D. (2016). Process-based development of competence models to computer science education. Journal of Educational Computing Research, 54(4):563–592.
Publicado
19/07/2026
Como Citar
CAMPANO JUNIOR, Maurilio Martins; AYLON, Linnyer Beatrys Ruiz.
Construção e Análise de uma Máquina de Turing para Ordenação de Vetores Binários: Uma Abordagem para Disciplinas de Teoria da Computação. In: WORKSHOP SOBRE EDUCAÇÃO EM COMPUTAÇÃO (WEI), 34. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 163-174.
ISSN 2595-6175.
DOI: https://doi.org/10.5753/wei.2026.20514.
