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
Fórum