EAD 2014

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 Turing [...], todas apresentam uma característica importante. O modelo de memória é sequencial, isto é, a fim de acessar uma informação armazenada em alguma localização, a máquina necessita primeiramente acessar, uma a uma, todas as células da memória localizadas entre a célula atual e aquela que se deseja acessar. Em contraste, os computadores reais apresentam uma memória de acesso aleatório, onde cada célula da memória pode ser acessada em uma única etapa, se for adequadamente endereçada.”