AndreCunha_MariaLuiza_P2_ComCom

Prévia do material em texto

1)
Fazendo uma análise inicial do tipo 3, sabe-se que a máquina desse tipo é um
Autômato Finito (sem memória) e portanto não é o tipo de L, já que para ter
um número arbitrario de "a" e "b" é necessário armazenar e contar esses valores,
o que não é possível aqui.
Para a análise do tipo 2, vimos que não seria possível ser também, pois vimos
que seria um Autômato a pilha não deterministicos.
No tipo 1, usando uma Máquina de Turing, percebemos que também não seria
possível, pois apesar de ser uma máquina poderosa ainda tem o problema da
memória limitada, equanto na nossa entrada podemos ter um valor infinito.
Logo o ideal seria uma Máquina de Turing do tipo 0. Uma vez que essa máquina
não tem o problema da mémoria limitada e possuí a construção da imagem abaixo.
Máquina de Turing do tipo 0
2)
Vamos construir uma máquina de Turing normal para exemplificar:
Fazendo outra máquina de Turing, mas agora com uma entrada vazia:
Criando uma máquina de Turing unindo as duas anteriores:
Vamos supor ainda que ela não entra em loop, 
portanto não é indecidível
Assumindo que podemos decidir o problema da parada com a fita vazia, 
isso nos permite decidir o problema da parada (que sabemos que é indecidível). 
Podemos levar a entrada para o problema de parada normal e criar uma 
nova máquina de Turing sempre que iniciar com uma fita vazia e depois 
gravar a entrada do problema de parada normal na fita como seu primeiro 
conjunto de etapas. Dessa forma, se essa máquina modificada parar quando
começar com uma fita vazia, a entrada do problema de parada normal vai 
parar com qualquer que seja sua entrada. Logo, é indecidível o problema 
de parada com fita vazia (Problema Lambda).
Legenda:
P -> Palavra
V -> Fita vázia
S -> Saida
MT -> Máquina de Turing
É indecidível o problema da parada, por causa do loop
Nessa máquina acima foi feita basicamente uma conversão. Perceba que foi 
fornecido de entrada para a máquina MT1 uma palavra (P), e sabemos que 
o problema da parada nessa máquina é indecidível. Estamos fornecendo essa
saída de MT1(indecidível), como entrada para a máquina MT2. Tinhamos 
suposto que a máquina MT2 não entrava em loop, portanto ela não seria 
indecidível, mas se isso fosse verdade essa conversão feita em MT3 seria 
suficiente para resolver o problema da parada, só que não é. Portanto a 
saída de MT2 também teria um loop e seria indecidível, chegando a conclusão
que uma entrada vazia, no Problema Lambda, é indecidível.
3)