Apresentação sobre Metabiologia, Subcomputação e Hipercomputação

UFRJ

Metabiologia, Subcomputação e Hipercomputação: em direção a uma teoria geral de evolução de sistemas

Felipe Sobreira Abrahão Tese de doutorado

Orientadores:

2015

Francisco Antônio Dória Gregory Chaitin

Rio de Janeiro

Slide 2

Introdução “Filhos do DNA”: como criar uma teoria matemática para a evolução biológica? Biologia, “a ciência das exceções”; Como colocar em equações sistemas dinâmicos, complicados e cheios de particularidades?

Biologia Matemática: Métodos estatísticos, frequências de genes, genética de populações;

Biologia computacional: Algoritmos genéticos; Biologia sistêmica;

Porém, sempre modelos adaptativos! Queremos uma evolução open-ended! Como estudar a forma que os seres vivos se tornam mais complexos ou criativos?

2015

Metabiologia, Subcomputação e Hipercomputação

Slide 3

Introdução Metabiologia: o ser vivo como um programa Universalidade das máquinas de Turing. Teoria da informação algorítmica: Quão complexo ou criativo é um programa/organismo? A função Busy-Beaver, o número ômega e a função de aptidão;

Qual a probabilidade de um programa ocorrer ao acaso?

Evolução de software: Como e quão rápido os organismos/programas se tornam mais criativos? Estimar a quantidade média de mutações;

O que muda os organismos ao longo de tempo? Mutações algorítmicas; As mutações são programas que pegam os organismos/programas anteriores e levam em outros organismos/programas;

“Programar sem programador” (menos no Intelligent Design);

2015

Metabiologia, Subcomputação e Hipercomputação

Slide 4

Introdução

2015

P0

M1

M2

....

Mn

P0

P1

P2

....

P

Metabiologia, Subcomputação e Hipercomputação

Slide 5

Introdução Os modelos chaitinianos de evolução de programas Busca exaustiva Mutações algorítmicas aleatórias; Não leva em consideração o quanto um organismo anterior tem de informação (só permitimos mutações “burras”); Tempo de mutação exponencial em N;

Projeto inteligente A natureza “escolhe” as mutações ótimas para os organismos aumentarem sua complexidade mais rápido; Tempo de mutação linear em N;

Evolução cumulativa (“darwiniana”) Mutações algorítmicas aleatórias;

Leva em consideração o quanto um organismo tem de informação sobre o outro; Tempo de mutação aproximadamente quadrático em N;

2015

Metabiologia, Subcomputação e Hipercomputação

Slide 6

Nossas duas questões principais 1. E se quiséssemos simular essa evolução em um computador? A metabiologia cairia por terra? Como lidaríamos com a evolução open-ended de sistemas artificiais dentro de um sistema artificial? Para isso, a Natureza precisa ser emulável em um computador. A natureza nos modelos chaitinianos é um hipercomputador! E se o Universo “for” um gigantesco computador?

Os principais problemas são: como ficam os organismos e as mutações? Subprogramas;

como medimos quão complexo ou criativo é um organismo? Incomputabilidade relativa recursiva;

qual a velocidade de evolução? Análoga!

2015

Metabiologia, Subcomputação e Hipercomputação

Slide 7

Nossas duas questões principais 2. No sentido inverso, e se os seres vivos não forem computáveis? Organismos são hipercomputadores?

Hiperprogramas/organismos evoluem? Que tipo de hipercomputador seria a Natureza? Como ficam os organismos e as mutações? Organismo/Hiperprogramas; Mutações/programas;

Como medimos quão complexo ou criativo é um organismo? Incomputabilidade relativa oracular;

Qual a velocidade de evolução? Muito rápida! Mesmo com mutações “burras”;

2015

Metabiologia, Subcomputação e Hipercomputação

Slide 8

A evolução de subprogramas Os problemas de uma Natureza computável “Seleção natural” e o problema da parada. O conjunto de programas/organismos possíveis é muito restrito;

Nada nos garante que a evolução não se estagne (adaptação máxima) num certo nível. Em um certo ponto da evolução a complexidade de um organismo pode se tornar basicamente a mesma do meio-ambiente (função de aptidão);

E se nunca se estagnar, nada nos garante que a evolução seja capaz de elevar a complexidade ou criatividade indefinidamente. Pode haver um limite finito para a complexidade dos organismos;

Isso tudo se resume no problema de como medimos a complexidade ou criatividade dos organismos. Para resolver esse problema, definimos a subcomputação e a incomputabilidade relativa recursiva;

2015

Metabiologia, Subcomputação e Hipercomputação

Slide 9

A evolução de subprogramas O que é um subcomputador? Pode ser entendido como uma máquina rodando dentro de outra máquina mais poderosa; Um subsistema de um sistema;

O sistema sempre sabe tudo que o subsistema pode fazer; Qualquer programa rodando em um subcomputador “produz” um resultado;

Chamamos estes de subprogramas;

Sempre existe um programa que subprograma, se este se detém ou não;

computa,

para

qualquer

Dessa forma, podemos definir facilmente o que quer dizer não ser computável por um subcomputador e ser computável por um computador. Montamos uma função “irmã” da Busy-Beaver que apresenta tal característica: a Busy-Beaver Plus recursiva;

2015

Metabiologia, Subcomputação e Hipercomputação

Slide 10

A evolução de subprogramas A incomputabilidade relativa recursiva O “paradoxo” de Skolem: Teorema de Cantor;

O que é dito “de dentro” pode ser contrário com o que é dito “de fora”;

Aplicar essa ideia à incomputabilidade, à Busy-Beaver e à informação algorítmica infinita (nosso número “oracular”). Fazemos com Turing, Radó e Chaitin o que Skolem fez com Cantor! Versões relativas da função Busy-Beaver Plus, do número ômega e do próprio conceito de computabilidade;

O “paradoxo” da computabilidade: “Paradoxo” da intuição matemática; Consciência e livre-arbítrio; “Paradoxo” da computabilidade biológica e vida artificial; “Paradoxo” da computabilidade do Universo e o princípio de incerteza da computabilidade do Universo;

2015

Metabiologia, Subcomputação e Hipercomputação

Slide 11

A evolução de subprogramas Demonstrando a evolução de subprogramas Queremos construir um prova análoga às chaitinianas. Já sabemos definir as versões relativas da incomputabilidade, da BusyBeaver Plus e do número ômega; Para tanto, ainda precisamos de um subcomputador que seja capaz de rodar as versões relativas dos organismos e mutações utilizadas nas suas demonstrações;

A necessidade da autorreferência. Precisamos construir um subcomputador que se autodiagonalize através da Busy-Beaver Plus relativa; Perigo de entrar em “loop”; “Truque”: os subprogramas nunca dependem de si mesmos ou de subprogramas maiores para estarem bem definidos;

O “laço autorreferencial”. Os teoremas principais estão “amarrados” justamente pelo fato do subcomputador se autoreferir, se autodiagonalizar e, por isso, estar bem definido; 2015

Metabiologia, Subcomputação e Hipercomputação

Slide 12

A evolução de hiperprogramas A vida é computável ou não? Podemos emular um ser vivo num computador? Existem sistemas no Universo que não são computáveis?

Organismos são computadores analógicos? Físico-química; Redes neurais analógicas (Siegelmann, Sontag); Hipercomputador analógico (Doria, Da Costa);

Complexidade inalcançável dos organismos: As cadeias de aminoácidos numa proteína seriam aleatórias na prática (Jaques Monod); Versus: “paradoxo” da computabilidade biológica;

Organismos também podem ser hipercomputadores! Nossos organismos agora serão hiperprogramas ao invés de programas ou subprogramas.

2015

Metabiologia, Subcomputação e Hipercomputação

Slide 13

A evolução de hiperprogramas O que é um hiperprograma? Existe uma hierarquia de problemas que não são computáveis. Para resolver o problema da parada, um computador precisaria ter acesso a uma fonte de informação infinita (ex.: o número Ômega); Assim por diante;

Um hiperprograma é um programa rodando em um computador que tem acesso a fontes infinitas de informação. Máquinas de Turing de várias fitas; Acesso a “Oráculos”; São bit strings finitas;

Basicamente, a quantidade de oráculos que um hipercomputador tem acesso dita qual ordem este terá. Quanto maior a ordem de um hipercomputador, mais problemas incomputáveis ele pode “computar”. Nossos organismos serão hiperprogramas de ordem finita! 2015

Metabiologia, Subcomputação e Hipercomputação

Slide 14

A evolução de hiperprogramas Em direção à completude Saber todas as verdades aritméticas caracteriza um sistema completo (na aritmética).

Todo problema aritmético corresponde a hiperprograma e vice-versa (teorema de Post);

uma

ordem

de

Ter acesso a qualquer oráculo de ordem finita é suficiente para saber todas as verdades aritméticas.

Pode a evolução levar os hiperorganismos a sempre subir de ordem? O que assimptoticamente levaria à completude; Qual o tempo de mutação para a evolução construir um hiperorganismo capaz de resolver um problema aritmético? Busy-Beaver de ordem infinita como função de aptidão;

E a natureza? Hiperprograma de ordem infinita;

2015

Metabiologia, Subcomputação e Hipercomputação

Slide 15

A evolução de hiperprogramas Demonstrando a evolução de hiperprogramas Fazemos uma versão da busca exaustiva (mutações “burras”). Primeiro, provamos que para cada N bits de “hipercomplexidade”, existe um hiperprograma correspondente. Existe hiperprograma que calcula a Busy-Beaver de ordem infinita em função de N;

Segundo, provamos que esse hiperprograma é um bit string “conhecida”. Logo, existe uma mutação algorítmica que leva qualquer hiperorganismo arbitrário nesse outro. Pelo tamanho dessa mutação, calcula-se o tempo médio para ela ocorrer.

É, basicamente, um problema de nomeação de máquinas oraculares dado uma sentença aritmética. Isso só é possível porque qualquer hiperprograma/organismo é uma bit string finita, autodelimitada e que diz sua própria ordem (auto-ordenado); Além disso, o espaço de todos os hiperprogramas de ordem finita define um espaço de probabilidade;

2015

Metabiologia, Subcomputação e Hipercomputação

Slide 16

Conclusões e Provocações Metabiologia e biologia Podemos construir modelos de evolução metabiológica para a biologia evolucionária: Caso os seres vivos sejam computáveis; E, por isso, a natureza seja hipercomputável;

Caso a Natureza seja computável; E, por isso, os organismos sejam subcomputáveis;

Caso os seres vivos sejam hipercomputáveis; E, por isso, a Natureza seja mais incomputável ainda;

Evolução open-ended de sistemas Caso se atribua uma função de aptidão a um sistema arbitrário podemos construir uma evolução open-ended. Caso esses sistemas hipercomputáveis;

2015

sejam

computáveis,

subcomputáveis

Metabiologia, Subcomputação e Hipercomputação

ou

Slide 17

Conclusões e Provocações Quem está computando em relação a o quê? A incomputabilidade se mostrou essencial para a evolução openended. Incomputabilidade clássica para os modelos chaitinianos; Incomputabilidade hiperprogramas;

relativa

oracular

para

a

evolução

de

Incomputabilidade relativa recursiva para a evolução de subprogramas;

Tanto nas versões clássica como relativa ela parece ser a chave para o ganho de criatividade ao longo do tempo, i.e., para a evolução open-ended.

A vida é computável? Agora, nem o fato dos seres vivos “parecerem” não computáveis parece ser decisivo;

2015

Metabiologia, Subcomputação e Hipercomputação

Slide 18

Conclusões e Provocações Colocando-nos em “paradoxo” O pseudoparadoxo metalinguístico da computabilidade mostrou ter relação com questões da inteligência artificial, consciência, vida artificial e computabilidade da Física; Talvez, ele apareça em muitas relações entre sistema e subsistema;

Qual o limite da evolução? Até que ordem de hiperprogramas/organismos podemos construir modelos de evolução? Lembrar que fizemos somente para ordens finitas; E se permitirmos ordens infinitas (ordinais)?

Qual o nível máximo de complexidade da natureza? Dos números reais (do contínuo)?

De todos os conjuntos possíveis (classe própria)? 2015

Metabiologia, Subcomputação e Hipercomputação