REPOSTAS EAD -ATC ASPECTOS TEORICOS DA COMPUTAC ----UINDADE I
Pergunta 1

e. A fita de trabalho de uma MT é passível de ser lida e escrita

Pergunta 2
A hipótese de Turing-Church sugere:

e. Qualquer outra forma de expressar algoritmos terá no máximo a mesma capacidade computacional da máquina de Turing

Pergunta 3 A máquina de Turing permite a computação de números naturais. Seja I um símbolo fixo não branco. Um número natural n pode ser representado em notação unária, pela cadeia de símbolos I, de comprimento n+1.
Considerando essa definição, selecione a representação unária para os números 0, 1 e 2, respectivamente, com I =1|.

c. 1, 11, 111
d)

Pergunta 4 Não se trata de uma máquina equivalente à máquina de Turing:

b. Autômato com uma pilha.
c)

Pergunta 5
Considere as seguintes afirmações:
I - Uma linguagem L é aceita por uma máquina de Turing com k fitas, m dimensões, n cabeçotes de leitura e gravação por fita se, e somente se, ela é aceita por uma máquina de Turing determinística com uma fita infinita em apenas um sentido e um cabeçote de leitura e gravação.
II - O conjunto de todos os programas que param para uma dada entrada é um conjunto recursivamente enumerável.
III – A tese de Church Turing iguala uma função computável por algoritmo com uma função computável por Turing. Está correta a alternativa:

a. I, II e III

Pergunta 6
Apesar do aparente poder e versatilidade das variantes da Máquina de