Classificação dos grupos gerados por autômatos de dois estados

Abstract

O teorema principal do presente trabalho classifica os grupos gerados por autômatos de dois estados sobre o alfabeto de duas letras. Existem 64 autômatos invertíveis agindo sobre um alfabeto de duas letras, mas apenas seis grupos de autômatos: o grupo trivial, o grupo de ordem 2, o grupo não cíclico de ordem 4, o grupo cíclico-infinito, o grupo diedral-infinito e, por fim, o grupo Lamplighter. A exposição baseia-se numa palestra de A. Zuk (Astérisque, 2008, n. 317). Para além dessa classificação, foi proposta uma aplicação para o ensino de parte dos conceitos abordados. Optou-se pelo ensino de autômatos e máquinas de leitura para crianças cursando o Ensino Fundamental. O objetivo é fornecer a esses alunos um primeiro contato com a linguagem de máquina, uma linguagem essencial à computação moderna.