Das Montanhas de Minas ao Oceano: Os Caminhos da Ciência para um Futuro Sustentável
20 a 25 de outubro de 2025
Trabalho 20385
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Dimensões Econômicas: ODS9 |
| Setor | Departamento de Matemática |
| Bolsa | CNPq |
| Conclusão de bolsa | Não |
| Apoio financeiro | CNPq |
| Primeiro autor | Phellype Xavier de Oliveira |
| Orientador | POUYA MEHDIPOUR |
| Título | Construção da Máquina de Turing Estendida |
| Resumo | O estudo das máquinas de Turing sob a perspectiva da dinâmica topológica e da dinâmica simbólica oferece uma ferramenta teórica útil para a compreensão da complexidade computacional e da dinâmica de sistemas discretos. A codificação das configurações de uma máquina de Turing em espaços simbólicos - tipicamente como pontos em um espaço métrico compacto - possibilita analisar o comportamento global da máquina como um sistema dinâmico. Em um primeiro momento, podemos visualizar uma Máquina de Turing como uma cabeça que possui uma quantidade finita de estados com uma fita divida em seções nas quais podem ter, no máximo, um símbolo. Em um determinado momento, a cabeça possui um estado e visualiza apenas um símbolo da fita (chamado de símbolo escaneado), formando uma configuração, com base nessa configuração ela decide a sua próxima ação. A cada passo, a máquina altera seu estado, a fita e a posição da cabeça. De modo matemático, a definição de uma Máquina de Turing como um sistema dinâmico é dada por uma função definida em um espaço de sequências bilaterais infinitas (que fazem o papel da fita, com os símbolos destas sequências pertencendo a um alfabeto finito) onde as configurações da máquina são dadas por uma função de transição. Em específico, neste trabalho estudamos o modelo no qual a cabeça permanece fixa, sobre a posição zero da cabeça, e a fita se move. O objetivo deste trabalho, além do estudo deste modelo clássico, é estender para um modelo no qual as sequências pertencem a um espaço zip, um espaço de sequências bilaterais infinitas onde os símbolos que compõem essas sequências pertencem a dois alfabetos distintos. Para a construção dessa Máquina de Turing Estendida, temos a adição de uma segunda cabeça (que possui um conjunto de estados diferentes dos estados da primeira cabeça) e a adição de uma nova função, chamada de função de tradução. Referências: P. Kůrka. “On topological dynamics of Turing machines”. Em: Theoretical Computer Science 174 (1997), pp. 203–216. doi: 10.1016/s0304-3975(96)00025-4. S. Lamei e P. Mehdipour. “Zip Shift Space”. Em: arXiv preprint arXiv:2502.11272 (2025). url: https://arxiv.org/abs/2502.11272. |
| Palavras-chave | Sistemas Dinâmicos, Máquina de Turing, Dinâmica Simbólica |
| Forma de apresentação..... | Painel |
| Link para apresentação | Painel |
|---|