Mostrando postagens com marcador Teoria da Computação. Mostrar todas as postagens
Mostrando postagens com marcador Teoria da Computação. Mostrar todas as postagens

sexta-feira, dezembro 28, 2007

e-Reality - Contexto

1) Introdução

O contexto da e-Reality pode ser estabelecido a partir do entendimento da figura abaixo, onde se destacam os seguintes elementos:

  1. Fenômeno da Realidade
  2. Fenômeno do Conhecimento
  3. Fenômeno Tecnológico
  4. Fenômeno Virtual ou Computacional
  5. Fenômeno Artificial
  6. Fenômeno Híbrido

A Realidade contém a totalidade desses fenômenos incluindo os fenômenos da e-Reality e como conseqüência ela própria.



A Realidade é um conjuntos de fenômenos relacionados e condicionados pela leis da natureza.


A e-Reality é um conjuntos de fenômenos virtuais ou computacionais relacionados e condicionados pela "leis da computação".

2) Realidade


Entende-se vulgarmente por Realidade tudo aquilo que existe, por conseguinte, existência é a "característica mais básica da Realidade". Existir é possuir um "estado físico" dentro da Realidade.

Para um entendimento mais profundo ver o segunte artigo sobre a Realidade

3) Fenômenos da Realidade

3.1) Fenômeno da Emergência

Emergência é o processo de formação de fenômenos complexos (fenômenos com estados complexos) a partir de fenômenos mais simples (estados mais simples).

Os fenômenos da Realidade e da e-Reality surgem por conta da emergência (que também é um fenômeno - meta-fenômeno).

Como exemplo podemos citar a evolução do cérebro humano, através de milhares de gerações sucessivas, a partir das interações entre neurônios. O cérebro humano é, então, um fenômeno emergente de um conjunto elevado de neurônios, sendo capaz de pensar e ter consciência. Pensamento e consciência são fenômenos (características) emergentes do cérebro humano. Um neurônio não é capaz de “pensar” ou de ter “consciência”, porém o cérebro humano possui essas características “emergentes”.

A "emergência" propicia a concepção de Níveis de Fenômenos, os quais visam, apenas, um melhor entendimento da Realidade. A Realidade não possui esses “Níveis”. Nós humanos “os criamos” apenas para melhor compreendermos e dominarmos os aspectos complexos dessa Realidade.

Não há consenso entre os cientistas sobre como a emergência deve ser utilizada como explicação. Não parece possível decidir completamente quando um fenômeno deve ser classificado como emergente, e mesmo nos casos onde esta classificação é aplicada ela raramente explica o fenômeno de modo profundo. De fato, nomear um fenômeno como emergente é muitas vezes usado pela falta de outra explicação melhor.

Para um entendimento mais profundo ver o segunte artigo sobre Emergência.

3.2) Fenômenos da Realidade

Os Fenômenos da Realidade podem ser explicados, com as limitações mencionadas anteriormente, a partir do conceito de emergência, conforme pode ser observado na figura abaixo, onde as setas em vermelho representam a idéia de emergência, numa abstração onde "fenômenos mais complexos" emergem de "fenômenos mais simples". (Aspas propositais)


  1. Fenômenos da Realidade são aqueles totalmente decorrente das Leis da Natureza. São os ..., quarks, elétrons, prótons, neutrons, átomos, moléculas, células, bactérias, órgãos, plantas, animais, homem, ...
  2. Fenômenos do Conhecimento são fenômenos emergentes da capacidade cognitiva humana. São as ..., linguagens, conceitos, regras, hHipóteses, teorias, paradigmas, ....
  3. Fenômenos Tecnológicos são fenômeno emergentes do conhecimento humano e da capacidade humana de mudar/criar Fenômenos da Realidade. Dentro do contexto da e-Reality destaca-se os Artefatos de Tecnologia da Informação, que são caracterizados como qualquer dispositivo mecânico/eletrônico/... capaz de capturar, armazenar, transmitir e manipular (processar) dados/informações.

3.3) Características Básicas dos Fenômenos da Realidade


Os Fenômenos da Realidade apresentam como sua característica mais básica ou fundamental a EXISTÊNCIA, onde EXISTÊNCIA significa o ESTADO FÍSICO DO FENÔMENO. Possivelmente essa é a única “característica real” dos Fenômenos da Realidade, todas as demais são meramente abstrações que construimos para um melhor entendimento da Realidade.


O ESTADO de um fenômeno pode ser quantificado ou qualificado a partier de INFORMAÇÕES.

Outras características básicas dos Fenômenos da Realidade são ESTRUTURA e COMPORTAMENTO. Ambas, porém, abstraídas da característica ESTADO.

ESTRUTURA é uma abstração estática de ESTADO (Abstração Espacial) independente do tempo.



COMPORTAMENTO é uma abstração dinâmica de ESTADO (Abstração Temporal). O Comportamento é uma abstração de mudanças de ESTADO.



A figura abaixo exibe as características mais fundamentais dos fenômenos da Realidade.



4) Fenômenos da e-Reality

Os Fenômenos da e-Reality são Fenômenos da Realidade com uma característica adicional - Computabilidade. Todos os fenômenos da e-Reality são fenômenos computáveis.

Para um entendimento mais profundo ver o segunte artigo sobre Computação, Computabilidade, Ciência da Computação e Teoria da Computação.


A figura a seguir mostra com mais clareza a idéia de que um Fenêmeno da e-Reality é um fenômeno da Realidade, ou seja herda todas as suas características.





4.1) Computação

Computação é uma Mudança de Estado (Comportamento) de um Fenômeno da Realidade capaz de ser descrita ou modelada através de um Algoritmo, ou seja Computação é um Processo da Realidade.

Em ourtras palavras computação, pode ser vista como o resultado da execução de um algoritmo.

Informação é representação simbólica de Estado (Estrutura) de um Fenômeno da Realidade.

Os Fenômenos/Artefatos Computacionais/Virtuais mais básicos são os Algoritmos e as Estruturas de Dados. Ambos são os objetos básicos da Ciência da Computação/Informação. Os demais são derivados (emergem) a partir deles.

  1. Um algoritmo é uma seqüência não ambígua de instruções que é executada até que determinada condição se verifique.
  2. Uma estrutura de dados é uma forma de organização de dados de modo que eles possam ser “computados” por algoritmos.



"Computação também pode ser definida como a busca de uma solução para um problema, a partir de entradas (inputs), com a geração de saídas (outputs), através de um algoritmo. É com isto que lida a Teoria da Computação, subcampo da Ciência da Computação e da matemática. Durante milhares de anos, a computação foi executada com caneta e papel, ou com giz e ardósia, ou mentalmente, por vezes com o auxílio de tabelas". [WIKIPEDIA]

Informação é o resultado do processamento, manipulação e organização de dados de tal forma que represente um acréscimo ao conhecimento da pessoa que a recebe. [WIKIPEDIA]

Computação e informação são fenômenos distintos da realidade, porém complementares.

4.2) Fenômrenos/Artefatos Computacionais/Virtuais

A e-Reality é uma parte da Realidade e é constituída pelos seguintes tipos de fenômenos:

  1. Fenômenos Virtuais/Computacionais são os fenômenos emergentes da Tecnologia da Computação/Informação e da característica de computabilidade de alguns Fenômenos da Realidade. Os Fenômrenos/Artefatos Computacionais/Virtuais, baseiam-se nos princípios da Ciência da Computação e são construídos com as Técnicas e Ferramentas das Engenharias da Computação e de Software. Exemplo: Algoritmos, Estruturas de Dados, Programas de Computador, Dados em Bancos de Dados, ...
  2. Fenômenos Artificiais. Todo e qualquer Fenômeno Tecnológico é um Fenômeno Artificial. Utilizaremos no contexto da e-Reality o termo com uma acepção mais restrita (na falta de outro mais significativo). Dentro da e-Reality um Fenômeno Artificial é um fenômeno criado pelo homem, que possui existência na Realidade e que simula a estrutura e o comportamento de outros Fenômenos Reais. Eles são emergentes da possibilidade de virtualização de Fenômenos Computáveis e de sua operação em Artefatos Tecnológicos. Exemplo: Computadores com Programas, Robôs, ...
  3. Fenômenos Híbridos são fenômenos emergentes dos Fenômenos Artificiais e dos Fenômenos Reais. Exemplo: Cyborg – Híbrido de Homem e Máquina.

Teoria da Computação

Teoria da computação - Wikipédia

Computação pode ser definida como a solução de um problema ou, formalmente, o cálculo de uma função, através de um algoritmo. A teoria da computação, um subcampo da ciência da computação e matemática, busca determinar quais problemas podem ser computados em um dado modelo de computação. Por milhares de anos,a computação foi feita com lápis e papel, ou giz e quadro, ou mentalmente, às vezes com a ajuda de tabelas.

A teoria da computação teve início nos primeiros anos do século XX, antes da invenção dos modernos computadores eletrônicos. Naquela época, os matemáticos estavam tentando descobrir quais problemas matemáticos poderiam ser resolvidos por um método simples, e quais não poderiam. O primeiro passo estava em definir o significado de um "método simples" para resolver o problema. Em outras palavras, eles precisavam de um modelo formal da computação.

Diversos modelos diferentes da computação foram propostos pelos primeiros pesquisadores. Um modelo, conhecido como Máquina de Turing, propunha a construção de uma máquina universal, capaz de operar com uma sequência de instruções e dados entremeados em uma fita de comprimento infinito; a máquina poderia operar em um ponto da fita de cada vez utilizando um cabeçote de leitura e escrita, executando assim a programação que lhe for passada. Outro modelo se baseia em funções recursivas compostas para operar diretamente sobre os números. Uma abordagem similar é o cálculo lambda. Outra classe de abordagens trabalha com regras gramaticais operando sobre cadeias de caracteres, como é o caso dos cadeias de Markov e dos sistemas de Post.

Todos os formalismos propostos acima são equivalentes em termos de poder computacional -- ou seja, qualquer computação que possa ser realizada com um modelo pode ser realizada com qualquer um dos outros modelos. Ainda em termos teóricos, os modelos propostos são equivalentes aos computadores eletrônicos, desde que não hajam restrições de memória envolvidas. Na verdade, acredita-se que todas as formalizações teoricamente possíveis para o conceito de algoritmo são equivalentes em poder a uma máquina de Turing; esta é a tese de Church-Turing. As questões relativas à possibilidade de realizar certos tipos de computação em determinados tipos de máquina (ou formalismo teórico) são investigadas pela teoria da computabilidade.

A teoria da computação estuda os modelos de computação genéricos, assim como os limites da computação:

  1. Quais problemas jamais poderão ser resolvidos por um computador, independente da sua velocidade ou memória? (Ver: Problema da parada, Problema da Correspondência de Post.)
  2. Quais problemas podem ser resolvidos por um computador, mas requerem um período tão extenso de tempo para completar a ponto de tornar a solucão impraticável? (Ver: Aritmética de Presburger.)

Em que situações pode ser mais difícil resolver um problema do que verificar cada uma das soluções manualmente? (Ver Classes P e NP).

Em geral, as questões relativas aos requerimentos de tempo ou espaço (memória, em particular) de problemas específicos são investigadas pela teoria da complexidade computacional.

Além dos modelos genéricos de computação, alguns modelos computacionais mais simples são úteis para aplicações mais restritas. Expressões regulares, são por exemplo utilizadas para especificar padrões de cadeias de caracteres, sendo populares em aplicações UNIX e em algumas linguages de programação, como Perl e Python. Outro formalismo matematicamente equivalente às expressões regulares são os autômatos finitos, que são utilizados em desenho de circuitos e e alguns sistemas de resolução de problemas. As gramáticas livres de contexto são utilizadas para especificar a sintaxe das linguagens de programação; um formalismo equivalente, são os autômatos com pilha, ou pushdown automata. As funções recursivas primitivas formam uma subclasse das funções recursivas.

Modelos de computação diferentes podem realizar tarefas distintas. Uma forma de estudar o poder de um modelo computacional é estudar a classe das linguagens formais que o modelo pode gerar; o resultado é a hierarquia de Chomsky das linguagens.

As tabelas abaixo mostram algumas das classes de problemas (ou linguagens, ou gramáticas) que são consideradas em teoria da computabilidade (azul) e em teoria da complexidade (verde).

Se a classe X é um subconjunto propriamente contido em Y, então X é mostrado abaixo de Y, conectados por um linha escura. Se X é um subconjunto, mas não é sabido se os conjuntos são iguais ou não, então a linha que os conecta será mais clara e pontilhada.