Caralho de asa

1 – A tese de Church afirma que qualquer função computável pode ser processada por uma máquina de Turing, ou seja, existe um procedimento expresso na forma de uma máquina de Turing capaz de processar tal função. Ela não pode ser provada, pois como a noção intuitiva de procedimentos não é matematicamente precisa, é impossível demonstrar formalmente se a máquina de Turing é, de fato, o mais genérico dispositivo de computação. É considerada verdadeira, pois até hoje não se tem um formalismo com capacidade maior que a máquina de Turing, no máximo, com a mesma capacidade.

2 – Linguagens recursivamente enumeráveis ou linguagens do tipo 0, são aquelas que podem ser aceitas por uma máquina de Turing. Representa o conjunto de todas as linguagens que podem ser reconhecidas mecanicamente e em um tempo finito.

Linguagens recursivas são aquelas para as quais existe pelo menos uma máquina de Turing que para para qualquer entrada, aceitando ou rejeitando.

Linguagem sensível ao contexto é uma linguagem gerada por alguma gramática sensível ao contexto. O conjunto de todas as linguagens sensíveis ao contexto é idêntico ao conjunto de linguagens aceitas por um autômato linearmente limitado (máquina de Turing com fita limitada).

5 –

Possui quatro fitas de entrada independentes. A descrição da máquina a ser simulada e a sua entrada, são gravadas na primeira fita. A segunda fita é usada para representar a fita de entrada da máquina sendo simulada, a terceira fita representa o estado corrente da máquina sendo simulada e a quarta fita é usada como rascunho.

A Máquina Universal copia a cadeia de entrada da máquina sendo simulada para a segunda fita. Em seguida, são analisados os símbolos dessa fita e executados os movimentos conforme as especificações da máquina que está sendo simulada e que estão armazenadas na primeira fita.

A linguagem aceita pela MTU é a Linguagem Universal, formada por todas as cadeias que são obtidas pela justaposição de codificações de