Aula 81 M2quina de Turing 3 Como Transdutor
Reconhecedores produzem apenas uma saída binária (aceitar/rejeitar). Transdutores podem produzir resultados mais ______.
Apuntes
Aula 8– Máquina de Turing – Como Transdutor “Pois é indigno destes doutos homens perder horas como escravos, em trabalhos de cálculos que poderiam, com segurança, ficar a encargo de qualquer pessoa, caso se utilizassem de máquinas” Gottfried Wilhelm Leibniz (1672) 1. Introdução Reconhecedores produzem apenas uma saída binária (aceitar/rejeitar). Transdutores podem produzir resultados mais complexos. Atualmente, considera-se mais conveniente pensar em Máquinas de Turing (Turing Machines - TM) como reconhecedores de linguagens ou, de modo equivalente, solucionadores de problemas. Contudo, a visão original de Turing sobre sua máquina era a de um computador de funções sobre inteiros. Seguindo este raciocínio, os inteiros eram representados em unário, como blocos de um único caractere e a máquina fazia os cálculos alterando os comprimentos dos blocos ou construindo novos blocos em outro lugar na fita. O unário, contudo, consome espaço, então geralmente é preferível a representação utilizando o binário. Quando não os recursos não precisam ser considerados, é mais conveniente usar unário (mais fácil de manipular com TMs). Um computador é sobretudo um transdutor: transforma uma entrada num...
Estudia con juegos interactivos
Sube tus apuntes y genera flashcards, examenes y mas con IA
Empezar gratis