Teoria da computação: máquinas universais e computabilidade (3a. ed.)

Visualizações: 570
Classificação: (0)

Aborda os principais aspectos relativos à teoria da computação de forma sistematizada e acessível.

FORMATOS DISPONíVEIS

Impresso
eBook

10 capítulos

Formato Comprar item avulso Adicionar à Pasta

1. introdução

PDF Criptografado

22

Teoria da Computação: Máquinas Universais e Computabilidade

“Há um teorema conhecido que diz que qualquer computador

é capaz de emular qualquer outro computador”

Astronauta Frank Poole ao explicar o princípio usado por Halman (computador HAL/astronauta Bowman) para impedir o Monólito de executar qualquer ordem que ameaçasse a humanidade

Do livro 3001: a odisséia final - Arthur C. Clarke (1997), da série iniciada pelo livro 2001 - uma odisséia no espaço

Este capítulo inicia com uma breve história do surgimento e do desenvolvimento dos conceitos, formalismos e resultados nos quais a teoria da computação é baseada. A seguir, é apresentada a abordagem geral adotada nesta publicação. Por fim, são introduzidos alguns conceitos básicos que são usados ao longo de todo o texto.

1.1

notas históricas

A ciência da computação é o conhecimento sistematizado da computação. Sua origem é milenar, tendo se desenvolvido em diversas regiões e momentos ao longo da história da humanidade, com destaque para culturas como Mesopotâmia, Egito, Grécia, Babilônia, Índia,

 

2. programas, máquinas e computações

PDF Criptografado

34

Teoria da Computação: Máquinas Universais e Computabilidade

Neste capítulo, é introduzida a formalização das noções de programa, de máquina, de computação e do que é computável em uma máquina e de relações entre formalismos, como equivalência e simulação.

Considerando que diferentes computadores podem ter diferentes arquiteturas e que os diversos tipos de linguagens de programação aparecem em abundância, a formalização dos conceitos de programa e de máquina não é baseada em qualquer linguagem ou computador real. Assim, suas características essenciais são descritas em modelos matemáticos simples, permitindo um rápido entendimento de suas semânticas e facilitando a demonstração de resultados.

Inicialmente, é introduzido o conceito de programa, o qual pode ser visto como um conjunto de operações e testes compostos de acordo com uma estrutura de controle. O tipo de estrutura de controle associada determina uma classificação de programas como segue:

monolítico: baseada em desvios condicionais e incondicionais; iterativo: possui estruturas de iteração de trechos de programas; recursivo: baseado em sub-rotinas recursivas.

 

3. verificação da equivalência forte de programas

PDF Criptografado

80

Teoria da Computação: Máquinas Universais e Computabilidade

Neste capítulo, são estudadas formas de se determinar se dois programas, sob determinadas condições, são ou não fortemente equivalentes. Uma vez que programas iterativos e monolíticos podem ser transformados em programas recursivos fortemente equivalentes, uma resposta satisfatória a essa questão poderia ser a obtenção de um método geral, aplicável a qualquer par de programas recursivos P e Q, o qual decidiria, em um número finito de passos, se P ≡ Q. Porém, como afirmado anteriormente, até o momento, não se sabe se o problema da equivalência forte de programas recursivos é solucionável.

Na falta de um algoritmo genérico para programas recursivos, procuram-se métodos para verificar a equivalência forte de classes mais simples de programas. De fato, mostra-se que existe um algoritmo para decidir a equivalência forte entre programas monolíticos. E, como todo o programa iterativo possui um programa monolítico fortemente equivalente, o mesmo pode ser afirmado para programas iterativos.

 

4. máquinas de registradores – Norma

PDF Criptografado

104

Teoria da Computação: Máquinas Universais e Computabilidade

Até o momento, o termo algoritmo foi intuitivamente usado como solução de um problema, ou seja, como uma forma de descrever se determinada propriedade é verificada ou não para uma dada classe de entrada. Portanto, o estudo da solucionabilidade de um problema é a investigação da existência de um algoritmo capaz de resolvê-lo. Entretanto, se a noção de algoritmo é intuitiva (não formal), qualquer afirmação sobre a não solucionabilidade de determinado problema é questionável.

Em relação à noção intuitiva de algoritmo, o seguinte pode ser afirmado:

sua descrição deve ser finita e não ambígua; deve consistir de passos discretos, executáveis mecanicamente em um tempo finito.

Limitações de tempo ou de espaço podem, eventualmente, determinar se um algoritmo pode ou não ser utilizado na prática. Entretanto, estas não são restrições teóricas, pois a inexistência de limitações não implica recursos ou descrições infinitas. Assim, recursos de tempo e de espaço são “tanto quanto necessários”. O correto entendimento dessa observação é de fundamental importância para todo o estudo que segue.

 

5. máquina de Turing

PDF Criptografado

132

Teoria da Computação: Máquinas Universais e Computabilidade

Provavelmente, o modelo mais utilizado como formalização de algoritmo é a máquina de Turing, proposta em 1936, por Alan Turing. O trabalho de Turing é particularmente significativo por ter sido o primeiro a identificar programas escritos para uma “máquina computacional”, como noções intuitivas do efetivamente computável.

Basicamente, uma máquina de Turing é um mecanismo simples, que formaliza a ideia de uma pessoa que realiza cálculos, usando um instrumento de escrita e um apagador. O modelo formal é baseado em uma fita infinita (usada para entrada, saída e rascunho), uma unidade de controle e um programa, de forma muito similar aos atuais computadores, embora tenha sido proposto aproximadamente 20 anos antes do primeiro computador digital.

No que se refere aos recursos “tanto quanto necessários”, entende-se que a máquina de Turing possui “tantas células de armazenamento de dados quanto necessário”.

Existem três maneiras de abordar o estudo das máquinas de Turing e de seus modelos equivalentes, como segue: a Processamento de funções. Funções computáveis e suas propriedades; b Reconhecimento de linguagens. Linguagens que podem ser reconhecidas e suas propriedades; c Solucionabilidade de problemas. Problemas solucionáveis e não solucionáveis, problemas parcialmente solucionáveis (computáveis) e completamente insolúveis (não computáveis), bem como suas propriedades.

 

6. máquinas universais e hipótese de Church

PDF Criptografado

158

Teoria da Computação: Máquinas Universais e Computabilidade

Máquinas universais podem ser entendidas de duas formas:

se é capaz de simular todas as outras máquinas; se toda função computável pode ser expressa como um programa nesta máquina.

Ambos os entendimentos não podem ser provados, pois:

não há como definir o conjunto de todas as máquinas possíveis e, portanto, uma prova exaustiva de simulação não seria possível; o conceito de função computável não é matematicamente preciso.

Como é impossível formalizar a demonstração de que uma máquina é universal, buscam-se evidências para tal comprovação analogamente ao desenvolvido nos capítulos referentes às máquinas Norma e Turing. Nesse caso, foram buscadas evidências internas, pois, nos referidos capítulos, foram exploradas variações nas definições das máquinas que não aumentaram o poder computacional das mesmas, ou seja, o conjunto das funções computadas por estas máquinas permaneceu o mesmo.

Neste capítulo, é mostrado que o conjunto das funções computadas por Norma e Turing é o mesmo, por meio da demonstração de equivalência entre essas máquinas, o que constitui uma evidência externa.

 

7. outros modelos de máquinas universais

PDF Criptografado

182

Teoria da Computação: Máquinas Universais e Computabilidade

Neste capítulo, é verificado que os seguintes formalismos são equivalentes à máquina de

Turing (note o tipo de estrutura de dados de cada modelo): a Máquina de Post. Baseada na estrutura de dados do tipo fila (o primeiro dado armazenado é o primeiro a ser recuperado); b Máquinas com pilhas. Baseada na estrutura de dados do tipo pilha (o último dado armazenado é o primeiro a ser recuperado), onde são necessárias pelo menos duas pilhas para simular o mesmo poder computacional de uma fita ou fila. Trata-se de uma família de máquinas com poder computacional variado. Para alguns casos da família, o não determinismo aumenta o poder computacional; c Autômatos com duas pilhas. Analogamente, é baseada na estrutura de dados do tipo pilha, com exatamente duas pilhas, com programas expressos na forma de grafos, podendo ser determinístico ou não determinístico.

Um resultado importante que pode ser estabelecido a partir das equivalências destas máquinas universais, bem como da máquina Norma é que, referente às estruturas de dados:

 

8. funções recursivas

PDF Criptografado

Capítulo 8

Funções Recursivas

215

de poder computacional, a gramática é equivalente às máquinas universais. Dependendo de restrições feitas na definição das gramáticas, é possível estabelecer uma hierarquia conhecida como hierarquia de Chomsky, na qual as seguintes equivalências podem ser estabelecidas:

Autômatos finitos ⇔ gramáticas regulares;

Autômatos com uma pilha não determinísticos ⇔ gramáticas livres do contexto;

Máquinas universais ⇔ gramáticas irrestritas.

Neste capítulo, são estudados dois formalismos denotacionais (funcionais) do tipo recursivo

(permite a definição de uma função em termos de si mesma) denominados:

Funções recursivas parciais, ou funções recursivas de Kleene, introduzidas por S. C. Kleene

(1936), as quais, como o próprio nome indica, são funções parciais definidas recursivamente;

Cálculo Lambda (λ-Cálculo), introduzido por A. Church (1936), formalismo para definição de função, aplicação de função e recursão.

Assim como Turing, Kleene e Church tinham como objetivo formalizar a noção intuitiva de função computável. Nos dias atuais, isto significaria dizer que eles formalizaram o que é possível computar em um computador. Quando foi provado que as classes das funções Turing-computáveis, das funções recursivas parciais e das funções Lambda-computáveis são iguais, a tese de Church cresceu significativamente em termos de credibilidade, fortalecendo-a como hipótese para toda a teoria da computação clássica.

 

9. computabilidade

PDF Criptografado

246

Teoria da Computação: Máquinas Universais e Computabilidade

O objetivo do estudo da computabilidade é determinar a solucionabilidade de problemas, ou seja, investigar a existência ou não de algoritmos que solucionem determinada classe de problemas. Mais ainda, investigar os limites da computabilidade e, consequentemente, os limites do que pode efetivamente ser implementado em um computador. Por consequência, o estudo da solucionabilidade objetiva evitar a pesquisa de soluções inexistentes de problemas.

Um exemplo de problema que não tinha solução, mas que foi estudado por muitos anos

(cerca de 70 anos) foi um dos 23 problemas propostos por David Hilbert, em Paris, no ano de 1900, durante o II Congresso Internacional de Matemática. Ele apresentou uma lista de

23 problemas ainda não solucionados, que seriam o desafio para o novo século. Entre eles, consta como o décimo problema o seguinte enunciado:

Dada uma equação diofantina P(a0,…,an) = 0, onde P é um polinômio com coeficientes inteiros, quer-se saber se existe um procedimento efetivo que seja capaz de determinar, em um tempo finito, se suas raízes são inteiras.

 

10. conclusões

PDF Criptografado

Capítulo 10

Conclusões

277

formalismo equivalente às máquinas universais. Por fim, o livro trata da computabilidade e do estudo da solucionabilidade de problemas. Os problemas podem ser divididos em problemas solucionáveis (existe um algoritmo que resolva o problema, para qualquer entrada) e os não solucionáveis (não existe um algoritmo que sempre resolva o problema). Ou, alternativamente, podem ser divididos em problemas parcialmente solucionáveis (computáveis) e problemas completamente insolúveis (não computáveis).

10.1

resumo dos principais conceitos

O principal conceito estudado é o de computabilidade, o qual é construído usando noções de programas, máquinas e computações. São três conceitos distintos, mas diretamente relacionados, pois um programa para uma máquina pode induzir uma computação. Se ela for finita, então se define ainda a função computada por esse programa nessa máquina: ela descreve o que o programa faz.

A distinção entre programa e máquina é importante na ciência da computação, uma vez que o programa (ou algoritmo) independe da máquina e possui uma complexidade estrutural e computacional (quantidade de trabalho necessário para resolver o problema).

 

Detalhes do Produto

Livro Impresso
Book
Capítulos

Formato
PDF
Criptografado
Sim
SKU
B000000042517
ISBN
9788577808311
Tamanho do arquivo
2,9 MB
Impressão
Desabilitada
Cópia
Desabilitada
Vocalização de texto
Não
Formato
PDF
Criptografado
Sim
Impressão
Desabilitada
Cópia
Desabilitada
Vocalização de texto
Não
SKU
Em metadados
ISBN
Em metadados
Tamanho do arquivo
Em metadados