CCCC

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|.

a) 1 - 1, 1, 1+1

b) i, ii, iii

c) 1, 11, 111

d) 0, 1, 2

e) 00, 01, 10

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

a) Autômato com duas pilhas.

b) Autômato com uma pilha.

c) Autômato com múltiplas fitas.

d) Máquina de Turing multidimensional.

e) Máquina de Turing com múltiplos cabeçotes.

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

b) Apenas I

c) Apenas II

d) Apenas III

e) Apenas I e III

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.” (LEWIS, Papadimitrious). Considere as afirmações I e II:

I - As máquinas de Turing de acesso aleatório são mais poderosas que as máquinas de Turing padrão.

PORQUE

II - Prova-se que a hipótese de Turing Church é verdadeira.

Assinale a alternativa correta:

a) Ambas afirmações, I e II, são verdadeiras e a afirmação I é justificada pela afirmação II.

b) Ambas afirmações são falsas.

c) Ambas afirmações são verdadeiras, mas a afirmação I não pode ser justificada pela afirmação II.

d) Apenas a afirmação I é verdadeira.

e) Ambas afirmações são verdadeiras, mas a afirmação II é justificada pela afirmação I.

7) Considere a seguinte definição: “Dada uma máquina universal M qualquer