Máquina Turing Como calculado de funções



Baixar 75.16 Kb.
Encontro03.11.2017
Tamanho75.16 Kb.


Máquina Turing

Como calculado de funções

Raul de Assis Lima - T30261-7

Juliel Junio dos Anjos - C17HIB-9

Loyane Sousa Zacarias - C2389A-0

Jhonatta Costa da Silva Almeida - C25HJG-0

Iuri Carvalho Bezerra – C23154-1



INTRODUÇÃO

Uma Máquina de Turing pode ser vista como um modelo abstrato de um computador digital. Mostrado pelo matemático inglês Alan Turing. Quando ele uniu matemática e lógica na forma de uma máquina, Turing tornou possível sistemas processadores de símbolos. Turing também criou um famoso teste, usado para descobrir o nível de inteligência de um programa de inteligência artificial, identificando quão bem a máquina pode imitar o cérebro humano. Apesar de a máquina ser bem simples, elas podem simular cálculos de funções numéricas.

Máquina de Turing

Uma Máquina de Turing é um mecanismo constituído por uma fita dividida em quadrados, que pode ser infinitamente prolongada tanto à esquerda quanto à direita. Completamos o “hardware” da máquina com um cabeçote de leitura, que eu chamarei simplesmente de leitor.



A máquina observa apenas um quadrado por vez, que pode estar vazio ou conter algum símbolo proveniente de um conjunto finito de símbolos.



Σ={s1,s2,…,sk}.

Geralmente, o conjunto Σ é chamado de alfabeto. O leitor, por sua vez, além de realizar a leitura de um único símbolo de um quadrado da fita, pode:



  • apagar o símbolo do quadrado atual e escrever neste mesmo quadrado um símbolo qualquer do alfabeto ;

  • mover-se um quadrado para a esquerda;

  • mover-se um quadrado para a direita;

Vamos agora observar a computação de um ponto de vista completamente diferente que não seja baseado em qualquer formalismo computacional do explícito ou de manipulação de informação como ocorre com as máquinas de Turing ou com as gramáticas. Em lugar disso, focalizaremos o objetivo da Computação a realizar: as funções de números para números. Por exemplo é natural que o valor da função

F(m, n) = m . n² + 3 . m2.m+17

Possa ser computado para quaisquer valores dados de m e n porque se trata de uma composição de funções adição multiplicação e exponenciação, mais algumas poucas constantes que por sua vez podem ser computadas.

E como poderemos saber se uma operação de potenciação pode ser computada porque ela pode ser recursivamente definida em termos de uma função, mas simples no caso a multiplicação afinal de contas M elevado a n vale um de n = 0 E caso contrário valer a m valerá m.m a própria multiplicação pode ser definida recursivamente em termos da operação de adição e assim por diante.

No princípio devemos ser hábeis para iniciar o processo de funções de números naturais para números naturais que sejam tão simples que possam ser inequivocamente provados como o computados por exemplo a função Idêntica de uma função sucessor s u c c igual a n mais 1 E então combinadas vagarosa que pacientemente através de combinadores que sejam também por sua vez muito elementares e obviamente computáveis tais como os operadores de composição e de definição recursiva para Então porque obter uma classe de funções de números para números que sejam completamente Gerais e não triviais nessa sessão vamos nos entender de ser difícil significativamente a noção de computação assim definida para então provada como Idêntica as noções que nos chegam através das conclusões tiradas por outros caminhos neste capítulo máquina de turing suas variantes e gramáticas caminhos esses Que se mostram muito diferentes em espírito extensão e detalhes.

Iniciarmos definindo algumas funções extremamente simples de n para n para valores de k maior ou maior ou igual a zero a função 00 é naturalmente uma constante uma vez que não depende de nada as funções básicas são as seguintes



  1. Para qualquer função k ≥ 0, a função nula k-ária é definida como zerok (n1.... nk) = 0 para todo n1..... nk € N.

  2. Para qualquer k ≥ j > 0, a j-ésima função identidade k-ária é simplesmente a função idkij (n1..... nk) = nj para todo n1.... nk € N.

  3. A função sucessor é definida como succ(n) = n + 1 para todo n € N.

A seguir, apresentaremos duas maneiras simples de combinar funções para obter funções ligeiramente mais complexas.

Seja k € l ≥ 0, g: Nk  N uma função k-ária, e sejam h1 ..... hk g com h1.... hk como sendo a função l-ária seguinte, f(n1.... nk) = g(h1(n1....nk) ....hk (n1....nk)).

São funções recursivas primitivas todas as funções básicas e também todas as funções que podem ser obtidas a partir delas por qualquer numero de aplicações sucessivas das operações de composição e de definição recursiva.

A função plus2, definida como plus2(n) = n + 2 é recursiva primitiva, pois pode ser obtida a partir da função básica succ por uma composição com ela mesma. Em particular, seja k = l = 1 da definição 4.7.1 e g= h1 = succ.-

Analogamente, a função binária plus, definida como plus(m, n) = m + n, é recursiva primitiva, porque ela pode ser definida do mesmo modo a partir de combinações, das funções identidade, nula e sucessor. Em particular, na Parte 2 da definição 4.7.1, fazendo k = 1 e considerando g como a função id1+1 e h como a função h(m , n, p) = succ(id 3+3 (m, n, p)) – a composição de succ com id 3+3 A função assim obtida, definida recursivamente, é precisamente a função plis:

Plus(m, 0) = m


plus(m, n + 1) = succ(plus(m, n))

Continuando a função de multiplicação mult(m, n) = m . n pode ser definida recursiva como

Mult(m, 0 = zero(m)
mult(m, n + 1 ) = plus(m, mult(m, n )).
e a função exp(m, n = mn, como
exp(m, 0) = succ(m)),
exp(m, n + 1 ) = mult(m, exp(m, n)).

Portanto todas essas funções são recursivas primitivas.

Todas as funções constantes da fomra f(n1 .... nk) = 17 são recursivas primitivas, pois podem ser obtidas pela composição de uma função nula apropriada com a função succ, nesse exemplo 17 vezes. Além disso, a função sinal sgn(n), que vale zero se n = 0 e , um nos demais casos, também é recursiva primitiva: sgn(0) = 0 e sgn(n + 1) = 1.

Para melhor legibilidade escreveremos m+n em vez de plus(m, n) m.n em vez de mult(m, n), e m↑n, em lugar de exp(m, n) Todas as funções numéricas, tais como

M . (n + m²) + 179m

São portanto, recursivas primitivas, umas vez que elas podem ser obtidas a partir das funções anteriormente definidas, por meio de composições sucessivas.

Uma vez que estamos limitados aos números naturais não podemos ter as operações de subtração e divisão convencionais. Entretanto, podemos definis certas funções uteis, como m ~ n = max{m – n, 0) e as funções div(m, n) e rem(m, n) ( o quociente inteiro e o resto da divisão de m por n; convencionando com ambos são nulos quando n = 0, Primeiro, definimos a função predecessora:

Pred(0) = 0


pred(n + 1) = n,

Da qual obtemos nossa função de “subtração não-negativa”

M ~ n + 1 = pred(m ~ n).

As funções quociente e resto serão definidas posteriormente em um exemplo.

É relativamente claro que podemos calcular o valor de qualquer função recursiva primitiva dados os valores de seus argumentos. Também é igualmente evidente que podemos determinar a validade de asserções sobre números, como por exemplo:

m . n > m² + n + 7.

Para quaisquer valores fornecidos de m e n. É adequado para isso, definir um predicado recursivo primitivo como sendo uma função recursiva primitiva que somente assume os valores 0 e 1. Intuitivamente, um predicado recursivo primitivo, como greater-than (m, n). irá representar uma relação que pode ou não ser aplicável aos valores m e n. Se a relação se aplicar, então o predicado recursivo primitivo assumirá o valor 1, caso contrário, será nulo.

A função iszero, que vale 1 se n = 0 e zero se n > 0, é um predicado recursivo primitivo, definido recursivamente da seguinte maneira:

Iszero(0) = 1
iszero(m + 1) = 0

Analogamente podemos definir, isone(0) = 0 e isone(n + 1) = iszero(n). O predicado positive(n) é idêntico ao já definido sgn(n). além disso, greater-than-or-equal(m, n) denotado m ≥ n, pode ser definido como iszero(n – m), sua negociação less-than(m, n) é naturalmente 1 ~ greater-than-or-equal (m, n). Em geral, a negação de qualquer predicado recursivo primitivo também é um predicado recursivo primitivo, De fato, assim são a disjunção e a conjunção de dois predicados recursivos primitivos: p(m, n) and q(m, n) é 1 ~ iszero(p(m, n) +q(m, n)) e p(m, n).

Por exemplo, equals(m, n) pode ser definido como a conjunção de greater-than-or-equal (m, n) e greater-than-or-equal (n, m).

Além disso, se f e g são funções recursivas primitivas e o é um predicado recursivo primitivos todos os três com o mesmo número de argumentos k então a função definida por casos



Também é recursiva primitiva, uma vez que pode ser reescrita como:

F(n1 ... nk) = p(n1... nk) . g(n1... nk) + (1 ~ p(n1... nk)) . h(n1... nk)

Como se pode facilmente constatar, a definição por casos constitui uma abreviação de grande utilidade.

Podemos finalmente definir div e rem.

Rem(0,n) = 0.

O conjunto infinito de funções recursivas primitivas e enumerável. Essa é a razão por que cada função recursiva primitiva pode, a princípio, ser definida nos termos das funções básicas e, portanto, ser representada como uma cadeia sobre um alfabeto finito: o alfabeto deve conter símbolos para representar as funções de identidade, sucessor e nula, para as recursões e composições primitivas, além de parênteses e os símbolos 0 e 1 utilizados para indexar, em binário, funções básicas como id17,11(veja a Seção 5.2 para outro uso dessa indexação, desta vez para representar todas as possíveis máquinas de Turing). Poderemos então enumerar todas as cadeias sobre o alfabeto, e manter somente aquelas que sejam definições corretas de funções recursivas primitivas unárias, definidas com um argumento apenas.

Suponham, então, que listamos todas as funções recursivas primitivas unarias, como cadeias, em ordem lexicográfica.

F0.f1.f2.f3....

Nessas condições, dado qualquer número n ≥ podemos localizar fn n-ésima função recursiva primitiva nessa lista e então utilizar sua definição para computar o numero g(n) = fn(n) + 1. Claramente, g(n) é uma função computável – apenas delineamos uma forma de computa-la. Adicionalmente, g não é uma função recursiva primitiva. Porque, caso fosse, existiria algum m ≥ 0 tal que g = fm e em consequência, deveríamos ter fm (m) = fm(m) + 1, o que é absurdo.

Esse é um argumento de diagonalização. Ele depende da disponibilidade de uma lista sequencial contendo todas as funções recursivas primitivas nessa lista e então utilizar sua definição que difira de todas aquelas pertencentes a lista e que.

Se: suponha que uma maquina de turing Mm = (k, ∑, q, s (h) Computa uma função f: N  N – assumimos, para simplificar a apresentação, que f é unária: os demais casos podem ser obtidos mediante uma simples extensão (veja o problema 4.7.5). Devemos mostrar que f é u-recursiva. Devemos para isso aos poucos definis certas funções u-recursivas que representam o comportamento de M e sua operação, até termos acumulado material suficiente para definir a própria função f.

Sem perda de generalidade, vamos admitir que K e ∑ Disjuntos. Seja b= |∑ | + |K|, e vamos definir um mapeamento E e ∑UK PARA {0, 1, ...., B-1}, TAL QUE E(0) = 0 e E (1 = 1 – lembre-se de que, uma vez que M computa uma função numérica, seu alfabeto deve conter os símbolos 0 e 1. Utilizando esse mapeamento, poderemos representar as configurações de M como inteiros na base b. A configuração (q, a1 a2 ... na), onde os a’s são símbolos de ∑ , será representada como um inteiro, em base b, a1a2...akqak+1... nan isto é, como inteiro.

CONCLUSÃO

A  Máquina  de  Turing  era  a  resposta  de  Alan  Turing  à  questão   matemática  de  Hilbert. Em sua essência, toda máquina de Turing move-se ou move símbolos, de uma posição para outra em uma fita, faz cálculos de funções numéricas. Nos  dias  de  hoje  estes símbolos  podem  ser  impulsos  eletrônicos  em   um   microcircuito   e   a   fita   uma   série   de   endereços de memória em um chip, mas a ideia é a   mesma.   Turing   provou   que   sua   hipotética   máquina   é   uma   versão   automatizada   de   um   sistema formal especificado por uma combinação variada de símbolos e regras.

Questões

1. Máquinas de Turing são aceitadores de linguagem, ou seja, dada uma máquina de Turing sobre um alfabeto que inclui o símbolo 1, pode-se dizer como interpretar o comportamento de uma máquina de Turing tal que ela possa ser pensada como um dispositivo que computa uma função teorético-numérica. Com essas informações, julgue os itens a seguir como Certo ou Errado:


I.   (  C  ) É importante usar estas máquinas como dispositivos que computam funções numéricas, isto é, que mapeiam Nk → N?.

II.  (   C ) Pretende-se codificar o conjunto dos números naturais na notação unária.


III. (  C  ) O código para 0 é 1, o código para 1 é 11, 2 é 111, 3 é 1111, etc.
IV. (  C  ) Usando a notação unária, pode-se dar uma semântica teorético-numérica para as máquinas de Turing?

Estão corretas as alternativas:


A) I, II e IV.
B) II e IV.
C) I, III e IV.
D) Todas as alternativas estão corretas.
2. Sobre a máquina de turing, escolha a alternativa correta:


  1. Realiza a gravação dos dados em disco magnético.

  2. Consegue realizar a leitura de mais um espaço da fita por vez

  3. O leitor verifica apenas um espaço da fita por vez.

  4. A máquina de turing e composta por um leitor óptico, processador e disco rígido.

3. Sobre a Máquina de Turing em funções numéricas responda a questão abaixo:

Como podemos saber se uma operação de potenciação pode ser computada?


  1. Realizando as funções de números para números.

  2. Por que ela pode ser recursivamente definida em termos de uma função mais simples.

  3. Por que a função k ≥ 0, a função nula k-ária é definida como zerok (n1.... nk) = 0 para todo n1..... nk € N.

  4. Pois funções que podem ser obtidas a partir delas por qualquer numero de aplicações.

4. Por qual razão cada função recursiva primitiva pode, a principio, ser definida nos termos das funções básicas?

  1. Por que o conjunto infinito de funções recursivas primitivas e enumerável.

  2. Por que o conjunto infinito de funções recursivas e enumerável.

  3. Pela qual funções recursivas primitivas unárias, estão em ordem lexicográfica.

  4. Pois os números naturais não podem ter as operações de subtração e divisão convencionais.

5. Como podemos definir uma função recursiva primitica?



  1. Primitivas todas as funções básicas e também todas as funções que podem ser obtidas a partir delas.

  2. São funções  de números naturais para números naturais.

  3. A função binária plus.

  4. O processo de funções de números naturais


GABARITO

1

D

2

C

3

B

4

A

5

A


Baixar 75.16 Kb.

Compartilhe com seus amigos:




©bemvin.org 2020
enviar mensagem

    Página principal
Prefeitura municipal
santa catarina
Universidade federal
prefeitura municipal
pregão presencial
universidade federal
outras providências
processo seletivo
catarina prefeitura
minas gerais
secretaria municipal
CÂmara municipal
ensino fundamental
ensino médio
concurso público
catarina município
Dispõe sobre
reunião ordinária
Serviço público
câmara municipal
público federal
Processo seletivo
processo licitatório
educaçÃo universidade
seletivo simplificado
Secretaria municipal
sessão ordinária
ensino superior
Relatório técnico
Universidade estadual
Conselho municipal
técnico científico
direitos humanos
científico período
espírito santo
pregão eletrônico
Curriculum vitae
Sequência didática
Quarta feira
prefeito municipal
distrito federal
conselho municipal
língua portuguesa
nossa senhora
educaçÃo secretaria
segunda feira
Pregão presencial
recursos humanos
Terça feira
educaçÃO ciência
agricultura familiar