Conceitos Fundamentais de Teoria da Computação
História da Computação
A História da Computação para uma Máquina de Turing (MT) sobre uma entrada é, simplesmente, a sequência de configurações pelas quais a máquina passa à medida que processa a entrada. É um registro completo da computação dessa máquina.
Autômato Linearmente Limitado (ALL)
É um tipo restrito de MT no qual a cabeça de leitura-escrita não tem permissão para mover-se para fora da parte da fita contendo a entrada. Se a máquina tentar mover sua cabeça para além de qualquer uma das extremidades da entrada, a cabeça permanecerá onde está, da mesma maneira que a cabeça não se moveria para além da extremidade esquerda da fita de uma MT.
Decidibilidade e Computabilidade
- Decidibilidade: É o problema de determinar