Olá pessoal!
Então eu entendi como funciona a máquina de Turing seus componentes e tal.
Mas fui tentar fazer os exercícios da lista e fiquei com uma dúvida:
Como eu defino a computação de uma máquina de Turing?
Eu sou péssimo com formalismos então to meio perdido.
Eu sei como faz a parte da transição.
E pelo que eu entendi, a computação é como a máquina funciona, como ela anda, etc. Mas não sei definir isso de uma maneira formal...
Como faz?
Aproveitando, a maneira correta de mostrar que uma MT diferente reconhece a classe de linguagens reconhecíveis é montando uma MT "normal" que faz a mesma coisa que a MT diferente. É isso? Tem um jeito formal de mostrar essa parte?
Valeu!
Como definir a computação de uma máquina de Turing
por Bruno Vercelino da Hora -
Número de respostas: 1
Em resposta à Bruno Vercelino da Hora
Re: Como definir a computação de uma máquina de Turing
Oi Bruno,
> Como eu defino a computação de uma máquina de Turing?
Acho que o ponto na questão 3 é redefinir "configuração C leva à configuração C' ", que para máquinas de Turing normais está nos slides da aula 3.
> E pelo que eu entendi, a computação é como a máquina funciona
Pensando em linguagens, o que interessa é definir quando a máquina aceita uma cadeia.
> a maneira correta de mostrar que uma MT diferente reconhece a classe
> de linguagens reconhecíveis é montando uma MT "normal"
> que faz a mesma coisa que a MT diferente.
E montar uma MT diferente que faz a mesma coisa que a MT "normal"
> Tem um jeito formal de mostrar essa parte?
Deve ter vários jeitos. O mais comum pode ser mostrando que dá para substituir a transição de uma máquina por transições equivalentes da outra máquina.
Zé Augusto
> Como eu defino a computação de uma máquina de Turing?
Acho que o ponto na questão 3 é redefinir "configuração C leva à configuração C' ", que para máquinas de Turing normais está nos slides da aula 3.
> E pelo que eu entendi, a computação é como a máquina funciona
Pensando em linguagens, o que interessa é definir quando a máquina aceita uma cadeia.
> a maneira correta de mostrar que uma MT diferente reconhece a classe
> de linguagens reconhecíveis é montando uma MT "normal"
> que faz a mesma coisa que a MT diferente.
E montar uma MT diferente que faz a mesma coisa que a MT "normal"
> Tem um jeito formal de mostrar essa parte?
Deve ter vários jeitos. O mais comum pode ser mostrando que dá para substituir a transição de uma máquina por transições equivalentes da outra máquina.
Zé Augusto