Caralho de asa

Disponível somente no TrabalhosFeitos
  • Páginas : 4 (946 palavras )
  • Download(s) : 0
  • Publicado : 17 de abril de 2013
Ler documento completo
Amostra do texto
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 processartal 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 maisgené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 – Linguagensrecursivamente 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 umtempo 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 é umalinguagem 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áquinaUniversal 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...
tracking img