Considere a existência de uma máquina G que computa a função parcial g : N×N ⇀ N, definida como g(x, y) = { x− y se x y ↑ caso contrário. Ut...

Question

Considere a existência de uma máquina G que computa a função parcial g : N×N ⇀ N, definida como g(x, y) = { x− y se x > y ↑ caso contrário. Utilizando G, construa uma máquina de Turing que computa a função total h : N×N→N, definida como h(x, y) = { x− y se x > y 0 caso contrário. Você é livre para utilizar as macros e máquinas definidas entre as seções 9.2 e 9.4 do livro do Sudkamp na sua resposta. Utilize a base de representação numérica que preferir. Obs.: Para garantir que o projeto da sua máquina está correto, indique sempre a entrada e saı́da esperada de cada macro/máquina, usando a notação vista no material de estudo.
Utilizando a máquina G, construir uma máquina de Turing que calcule a função total h : N×N→N, definida como h(x, y) = { x− y se x > y 0 caso contrário.

Ed · Answer

Para construir uma máquina de Turing que calcule a função total h(x, y) = { x− y se x > y 0 caso contrário, utilizando a máquina G, podemos seguir os seguintes passos:

1. Definir uma nova função f(x, y) que retorna 1 se x > y e 0 caso contrário.
2. Utilizar a máquina G para calcular g(x, y) = x - y se x > y e g(x, y) = ↑ caso contrário.
3. Utilizar a função f(x, y) para decidir se x > y ou não.
4. Se x > y, a máquina deve retornar o resultado de g(x, y), que é x - y.
5. Se x ≤ y, a máquina deve retornar 0.

Podemos implementar essa máquina de Turing utilizando as macros e máquinas definidas no livro do Sudkamp da seguinte forma:

1. Definir a macro F(x, y) que retorna 1 se x > y e 0 caso contrário:

F(x, y) = (x > y) ? 1 : 0

2. Utilizar a máquina G para calcular g(x, y) = x - y se x > y e g(x, y) = ↑ caso contrário:

Máquina G:
- Estado inicial: q0
- Estado final: qf
- Transições:
  - (q0, 0, B) → (qf, ↑, B)
  - (q0, 1, B) → (q1, B, R)
  - (q1, 0, B) → (qf, 0, B)
  - (q1, 1, B) → (q1, B, R)
  - (q1, B, B) → (q2, B, L)
  - (q2, 0, B) → (q2, 0, L)
  - (q2, 1, B) → (q2, 1, L)
  - (q2, B, B) → (q3, B, R)
  - (q3, 0, B) → (q4, B, R)
  - (q3, 1, B) → (q3, B, R)
  - (q4, 0, B) → (qf, 0, B)
  - (q4, 1, B) → (q4, 1, R)

3. Utilizar a função F(x, y) para decidir se x > y ou não:

Máquina H:
- Estado inicial: q0
- Estado final: qf
- Transições:
  - (q0, 0, 0) → (qf, 0, B)
  - (q0, 0, 1) → (qf, 0, B)
  - (q0, 1, 0) → (q1, B, R)
  - (q0, 1, 1) → (q1, B, R)
  - (q1, 0, 0) → (qf, 0, B)
  - (q1, 0, 1) → (qf, 0, B)
  - (q1, 1, 0) → (q2, B, R)
  - (q1, 1, 1) → (q2, B, R)
  - (q2, 0, 0) → (q3, B, R)
  - (q2, 0, 1) → (q3, B, R)
  - (q2, 1, 0) → (q2, B, R)
  - (q2, 1, 1) → (q2, B, R)
  - (q3, 0, 0) → (qf, 0, B)
  - (q3, 0, 1) → (qf, 0, B)
  - (q3, 1, 0) → (q3, B, R)
  - (q3, 1, 1) → (q3, B, R)

4. Combinar as máquinas G e H para calcular h(x, y) = { x− y se x > y 0 caso contrário:

Máquina final:
- Estado inicial: q0
- Estado final: qf
- Transições:
  - (q0, 0, 0) → (qf, 0, B)
  - (q0, 0, 1) → (qf, 0, B)
  - (q0, 1, 0) → (q1, B, R)
  - (q0, 1, 1) → (q1, B, R)
  - (q1, 0, 0) → (qf, 0, B)
  - (q1, 0, 1) → (qf, 0, B)
  - (q1, 1, 0) → (q2, B, R)
  - (q1, 1, 1) → (q2, B, R)
  - (q2, 0, 0) → (q3, B, R)
  - (q2, 0, 1) → (q3, B, R)
  - (q2, 1, 0) → (q2, B, R)
  - (q2, 1, 1) → (q2, B, R)
  - (q3, 0, 0) → (qf, 0, B)
  - (q3, 0, 1) → (qf, 0, B)
  - (q3, 1, 0) → (q4, B, R)
  - (q3, 1, 1) → (q4, B, R)
  - (q4, 0, 0) → (qf, 0, B)
  - (q4, 0, 1) → (qf, 0, B)
  - (q4, 1, 0) → (q5, B, L)
  - (q4, 1, 1) → (q5, B, L)
  - (q5, 0, 0) → (q5, 0, L)
  - (q5, 0, 1) → (q5, 1, L)
  - (q5, 1, 0) → (q0, 0, R)
  - (q5, 1, 1) → (q0, 1, R)

Essa máquina de Turing calcula a função total h(x, y) = { x− y se x > y 0 caso contrário, utilizando a máquina G.

Considere a existência de uma máquina G que computa a função parcial g : N×N ⇀ N, definida como g(x, y) = { x− y se x > y ↑ caso contrário. Ut...

Computabilidade e Complexidade

Outros

Essa pergunta também está no material:

p1

Computabilidade e Complexidade • Universidade PaulistaUniversidade Paulista

💡 1 Resposta

✏️ Responder

Outros materiais

Perguntas relacionadas

What is the purpose of the machine described in Q2? The machine checks if x > y and returns 0 if it is not. The machine uses the G machine to perf...

Construa uma DTM multi-fita que lê um número de entrada x em representação binária e escreve (converte) este mesmo número x em representaçã...

MARQUE A ALTERNATIVA QUE APRESENTA O GRADIENTE DA FUNÇÃO g(x, y)= 3x cos(y + 2) A)∇g(x, y)=(3se n(y + 2), 3x cos(y + 2)) B)∇g(x, y)=(3 + cos(y + 2)...

Dado que a função f : R → R definida por f(x) = x5 + x + 2 possui inversa g = f−1 definida em R, encontre g′(y) nos pontos correspondentes a x = ...

Materiais relacionados

Outros materiais