Grátis: Na máquina de Turing, a função de transição δ está na forma:(onde Q é o conjunto finito de estados, Σ é o conjunto finito de alfabetos de entrada, ... – Questões Respondidas

Teoria da Computação

Outros

Na máquina de Turing, a função de transição δ está na forma:(onde Q é o conjunto finito de estados, Σ é o conjunto finito de alfabetos de entrada, Γ é o símbolo de fita permitido, L significa esquerda, R significa direita e H significa parada).

Q × Γ → (Q × Σ)
Q × Γ → (Q × Γ × {L, R, H})
Q × Γ → (Q × Σ × {H})
Q × Σ → (Q × {L, R, H})
Q × Σ → (Q × Σ × {L, R, H})

Q × Γ → (Q × Σ)
Q × Γ → (Q × Γ × {L, R, H})
Q × Γ → (Q × Σ × {H})
Q × Σ → (Q × {L, R, H})
Q × Σ → (Q × Σ × {L, R, H})

Enviado por Testando o Conhecimento ano passado

Enviado por Testando o Conhecimento ano passado

EXERCICIO 8

ESTÁCIO

Respostas

Ed

há 6 meses

Na máquina de Turing, a função de transição \( \delta \) é definida como: \[ \delta: Q \times \Gamma \rightarrow (Q \times \Gamma \times \{L, R, H\}) \] Isso significa que, dado um estado atual \( q \in Q \) e um símbolo da fita \( \gamma \in \Gamma \), a função de transição retorna um novo estado \( q' \in Q \), um símbolo a ser escrito na fita \( \gamma' \in \Gamma \), e uma direção de movimento (esquerda \( L \), direita \( R \) ou parada \( H \)). Portanto, a forma correta é: \[ Q \times \Gamma \rightarrow (Q \times \Gamma \times \{L, R, H\}) \]

Essa resposta te ajudou?

0

0

left-side-bubbles-background

right-side-bubbles-background

Crie sua conta grátis para liberar essa resposta. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ed

ano passado

A alternativa correta é: Q × Γ → (Q × Γ × {L, R, H}). Essa é a forma da função de transição δ na máquina de Turing, onde Q é o conjunto finito de estados, Γ é o símbolo de fita permitido e L significa esquerda, R significa direita e H significa parada.

Essa resposta te ajudou?

0

0

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

EXERCICIO 8

ESTÁCIO

Mais perguntas desse material

Com base nas afirmativas abaixo sobre a descrição instantânea (DI) da máquina de Turing assinale a resposta correta:

I. Lembra o estado da máquina.
II. Lembra da célula que está sendo digitalizada pelo cabeçote de leitura e gravação.
III. O conteúdo de todas as células da fita.
IV. O conteúdo da célula seguinte a que está sendo lida.

a) I e IV, apenas.
b) I, II e IV, apenas
c) II e IV, apenas
d) I, II e III, apenas
e) II e III, apenas

I. Lembra o estado da máquina.
II. Lembra da célula que está sendo digitalizada pelo cabeçote de leitura e gravação.
III. O conteúdo de todas as células da fita.
IV. O conteúdo da célula seguinte a que está sendo lida.
a) I e IV, apenas.
b) I, II e IV, apenas
c) II e IV, apenas
d) I, II e III, apenas
e) II e III, apenas

Quais das seguintes sentenças matemáticas são verdadeiras?

I. para n > 0, f2 (n) < f3 (n)
II. para n > 2, f1 (n) < f2 (n)
III. para n = 0, f2 (n) < f3 (n)
IV. para n < 2, f1 (n) < f2 (n)
V. para n > 2, f3 (n) < f4 (n)

a) somente I, II e V.
b) somente I e II.
c) somente III, IV e V.
d) somente II, III e IV.
e) somente I, III e IV.

I. para n > 0, f2 (n) < f3 (n)
II. para n > 2, f1 (n) < f2 (n)
III. para n = 0, f2 (n) < f3 (n)
IV. para n < 2, f1 (n) < f2 (n)
V. para n > 2, f3 (n) < f4 (n)
a) somente I, II e V.
b) somente I e II.
c) somente III, IV e V.
d) somente II, III e IV.
e) somente I, III e IV.

Seja uma MT T dada pelas quíntuplas:

1. (0, 1, 1, 0, D)
2. (0, b, 1, 1, H)

Considere que 0 é um estado inicial e 1 é um estado final e a configuração inicial da fita igual a 111, com brancos antes e depois da cadeia 111 e n é o tamanho da cadeia, neste caso igual a 3. Qual a função que calcula essa MT?

2n
2n+1 - 1
2n+1
2n -1
2n +1

2n
2n+1 - 1
2n+1
2n -1
2n +1

O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para qualquer máquina de Turing M e palavra w, se M irá eventualmente parar com entrada w. Mais informalmente, o mesmo problema também pode ser assim descrito: dados um algoritmo e uma entrada finita, decidir se o algoritmo termina ou se executará indefinidamente. Para o problema da parada:

Existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial que o soluciona, fornecendo respostas aproximadas.
Existe algoritmo exato de tempo de execução polinomial para solucioná-lo.
Não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.
Não exist

Existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial que o soluciona, fornecendo respostas aproximadas.
Existe algoritmo exato de tempo de execução polinomial para solucioná-lo.
Não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.
Não exist

6. Uma redução é um processo de conversão de um problema em outro problema resolvido de tal forma que a solução do segundo problema possa ser usada para resolver o primeiro problema. Em particular, a redutibilidade pode ser usada para demonstrar que problemas são indecidíveis ou decidíveis. Nesse contexto, avalie as seguintes afirmativas:

I. A Redutibilidade não diz nada em resolver os problemas A ou B sozinhos, mas somente sobre a resolução de A na presença de um método para resolver B.
II. Reduções apresentam um importante papel em classificar os problemas em decidíveis ou indecidíveis.
III. Se A é redutível a B e B é um problema indecidível, então A é um problema decidível.

Quais as afirmativas verdadeiras?

I. A Redutibilidade não diz nada em resolver os problemas A ou B sozinhos, mas somente sobre a resolução de A na presença de um método para resolver B.
II. Reduções apresentam um importante papel em classificar os problemas em decidíveis ou indecidíveis.
III. Se A é redutível a B e B é um problema indecidível, então A é um problema decidível.
II e III.
I, II e III.
III.
I e II.
I e III.

7. Uma analogia matemática simples do conceito de redutibilidade ocorre quando desejamos medir a área de um retângulo. Nesse sentido, podemos reduzir o problema a medição da largura e comprimento. Acerca dos conceitos de redução, o que é verdadeiro para redutibilidade?

Converter um problema resolvido em outro problema não resolvido.
Se A se reduz a B, podemos usar uma solução de A para resolver B.
Se A é redutível a B e B é um problema indecidível, então A é um problema decidível.
Converter um problema não resolvido em outro problema não resolvido.
Se A se reduz a B, podemos usar uma solução de B para resolver A.

8. Na classificação da hierarquia de Chomsky a gramática tipo 0 é uma gramática de estrutura de frase sem qualquer restrição. Dentro dessa hierarquia estão classificadas a linguagem recursiva e a linguagem recursivamente enumerável. Acerca de suas características assinale a afirmação verdadeira.

Uma linguagem recursiva é um subconjunto de uma linguagem recursivamente enumerável.
Uma linguagem recursiva e uma recursivamente enumerável são equivalentes.
Uma linguagem recursiva e uma recursivamente enumerável podem fazer um loop para sempre na entrada de uma máquina de Turing.
Uma linguagem recursivamente enumerável é um subconjunto de uma linguagem recursiva.
Uma linguagem recursiva é uma linguagem que não é aceita por uma Máquina de Turing.

9. Existem dois tipos principais de complexidade computacional para um algoritmo: complexidade de tempo e complexidade do espaço. Nesse sentido, o que é falso para o problema da classe P?

Ele contém todos os conjuntos nos quais a pertinência pode ser decidida por um algoritmo cujo tempo de execução é limitado por um polinômio.
Em geral, a classe P contém todos os problemas que são resolvidos facilmente usando computadores.
P é definido como o conjunto de todos os problemas de decisão para os quais existe um algoritmo que pode ser realizado por uma máquina de Turing não-determinística em tempo polinomial.
Converter um problema não resolvido em outro problema não resolvido.
Se A se reduz a B, podemos usar uma solução de B para resolver A.

Em síntese, qualquer programa de computador pode ser traduzido em uma máquina de Turing, e qualquer máquina de Turing pode ser traduzida para uma linguagem de programação de propósito geral. Acerca de suas características principais, qual item não faz parte do diagrama mecânico da máquina de Turing?

Pilha.
Cabeça de leitura-escrita.
Controle finito.
Fita de entrada.
Direção de leitura.