Estimado Claudio, Fiz meu doutorado na intersecção entre teoria da computabilidade e teoria da complexidade, sob orientação do Prof. Walter Carnielli. Na sequência realizei um pós-doutoramento sobre complexidade computacional quântica, sob supervisão do Prof. Marcelo Finger. Depois de um longo hiato para aprimorar minha formação matemática, estou de volta à pesquisa, e, como sempre mantive o carinho pela computabilidade, gostaria de compartilhar minha impressão sobre o questionamento que você levantou.
Concordo com sua posição de que a computabilidade clássica é, atualmente, uma área com baixa demanda e produtividade. A variedade temática do CiE expressa o fato de que ela passa por uma espécie de crise de identidade. Existem muitas discussões sobre quais devem ser seus temas e problemas, seu papel, onde situa-se - é matemática? Informática? Até mesmo o nome da área é um tema controverso: certa vez o Friedman disse que, para que todos ficassem felizes, ela deveria chamar-se teoria da incomputabilidade! Afora possíveis questionamentos sobre como uma teoria matemática pode ser causa de felicidade ou infelicidade para as pessoas - uma questão existencial por natureza! -, penso que há uma componente ontológica e outra epistemológica como origem dessa crise de identidade. De um ponto de vista ontológico, falta unidade ontológica para a teoria da computabilidade e, penso, equacioná-la com o estudo dos graus de incomputabilidade piora o quadro. Ao longo dos anos os resultados da teoria da computabilidade passaram a ter impacto pequeno na lógica matemática e ela também, em grande medida, passou a integrar o que hoje chama-se de teoria da computação, dentro da qual formulações complicadas sobre incomputabilidade não parecem interessar. Acrescenta-se a isso que a teoria da computabilidade clássica fragmentou-se. Hoje o lambda cálculo, por exemplo, está mais para teoria dos tipos, teoria da prova e programação funcional do que como uma abordagem da computabilidade clássica. Já estudos sobre máquinas de Turing enquadram-se melhor na teoria dos automatos e como fundamento para o desenvolvimento da complexidade computacional. Existem programas de pesquisa em computabilidade estrutural (Montalbán e outros) e computabilidade analógica (Brattka e outros) que apresentam respostas sofisticadas para perguntas pontuais, sem uma perspectiva unificadora. Há também o problema epistemológico de saber qual é o papel da teoria da computabilidade. Como bem observou o Rodrigo, a teoria dos conjuntos, a despeito dos altos e baixos, sempre preservou seu papel fundacional. É debatível o quanto deve-se conhecer de teoria dos conjuntos para fazer matemática - um espectro que vai desde apenas saber as operações conjuntistas até dominar conceitos e métodos sobre cardinais inacessíveis -, mas todo estudante, em algum momento da sua formação matemática, defronta-se com uma prova que usa o lema de Zorn, uma prova da não-enumerabilidade dos números reais, a perplexidade dos conjuntos de Cantor, o teorema de Tychonoff e sua relação com o axioma da escolha, etc. Já a teoria da computabilidade... O que conhecimentos sobre máquinas de Turing, lambda cálculo, saltos, redutibilidade truth-table (vero-tabelar?), método de prioridade tem haver com ser matemático? Por outro lado, na informática não é raro que cursos sobre teoria da computação sejam postergados para o final da formação, e, mesmo quando neles, os estudantes entram em contato com muito pouco da teoria da computabilidade. Convenhamos: Para quê preocupar-se com graus de incomputabilidade se a vida tentando encontrar algoritmos, linguagens adequadas para a resolução dos problemas, implementações que passem em todos os testes, etc, já é uma dor de cabeça gigantesca? Sim, temos uma tradição que passa por Turing, Godel, Church, Kleene, Post, Julia Robinson, Dana Scott, entre tantos outros nomes bem conhecidos entre os lógicos. Essa tradição precisa ser preservada. Aqui no Brasil, temos o livro do Walter, em co-autoria com o Richard Epstein, sobre computabilidade, o qual é muito usado mundo afora graças à sua clareza. Tenho um livro recente do Matias Francisco Dias sobre o assunto também. Se considerarmos que estudos lógicos da teoria da complexidade devem ser parte da teoria da computabilidade - vale lembrar dos axiomas do Blum -, então temos outras guerreiras e guerreiros no front. O Marcelo, em parceria com o Glauber de Bona, tem trabalhos interessantes sobre complexidade e probabilidade no contexto do problema da satisfatibilidade. Não se pode, outrossim, deixar de lembrar do trabalho da Ana Teresa Martins e do Francicleber Ferreira sobre complexidade descritiva. Creio que deve haver mais pessoas próximas que tem trabalhado na área, e também espero, Claudio, poder conhecê-las. Apesar de muito ter escrito aqui, nada falei sobre o que talvez possa ter sido sua motivação inicial, Claudio: Afinal, quais são exatamente os problemas interessantes que estão em aberto na computabilidade? Ao estilo auto-referente característico da área, penso que seu maior problema em aberto é determinar justamente quais devem ser seus problemas em aberto! Abraços, Anderson Em ter., 9 de jun. de 2020 às 12:10, Rodrigo Freire <[email protected]> escreveu: > Caro Claudio, > > Obrigado pela interessante mensagem. > > Não trabalhei com teoria da computabilidade, apenas uma vez me ocorreu um > problema. Queria saber se um semireticulado para cima com jump parcial e > enumerável que eu havia definido poderia ser mergulhado nos graus de > Turing. A dificuldade é que o jump não é total, mas parece que isso segue > de um resultado geral de Montalbán, publicado em 2003: EMBEDDING JUMP > UPPER SEMILATTICES INTO THE TURING DEGREES. Era um problema muito isolado e > não teve continuidade nos meus projetos. > > Sobre a preocupação geral com a área colocada em sua mensagem, olhei o > mathoverflow, por curiosidade. A tag "computability theory" teve 69 > questões esse ano, e 687 no total. Não acho que seja pouco, mas é bem menor > que a tag "set theory", com 3852 questões no total. É preciso cuidado para > interpretar esses dados. Não estou afirmando que esse viés significa um > problema de saúde geral da área. Contudo, vai um pouco na direção da sua > preocupação. > > Acho que é importante para a saúde geral de uma área que ela tenha > "objetivos maiores" a partir dos quais vários problemas são colocados. > Mencionei a área de "set theory". A busca por novos axiomas ou pela melhor > teoria de conjuntos que podemos ter é um exemplo do que entendo por > "objetivo maior" que uma área pode ter. > Mas é igualmente importante que seja possível fazer progresso em direção a > esses grandes objetivos, como acontece no caso da busca por novos axiomas. > Pode ser que uma área tenha um grande objetivo, mas que pouco ou nenhum > progresso pode ser feito neste momento. Aí não adianta ter um grande > objetivo. > > > Abraço > Rodrigo > > > > > > > > On Mon, Jun 8, 2020 at 7:17 PM Claudio Andrés Callejas Olguín < > [email protected]> wrote: > >> Boa noite a todos(as), >> >> Essa é uma excelente notícia! >> >> Gostaria de aproveitar a oportunidade para compartilhar uma preocupação >> minha, sobre a escassez de trabalhos recentes na área de teoria da recursão >> ou sobre quaisquer das outras abordagens à computabilidade clássica. >> Acredito que cada vez é mais dificil encontrar um problema que não tenha >> sido resolvido anteriormente. Isso me aconteceu algumas veces no meu >> doutorado, pensava num problema e depois encontrava que alguém já o tinha >> resolvido e uma vez cheguei até resolver mesmo um problema sobre conjuntos >> produtivos, mas depois descubri que Dekker o tinha resolvido em 1955. Até >> que finalmente consegui contribuir na área e acabou dando tudo certo. >> >> A continuação embaço superficialmente o motivo desta preocupação: >> >> Entre os tutoriais, as palestras convidadas, e as sessões especiais deste >> CiE2020 não têm nenhuma que seja sobre teoria da recursão ou sobre >> quaisquer das outras abordagens à computabilidade clássica. Depois ao >> verificar a lista de 23 artigos aceitos apenas encontrei os seguintes três >> que provavelmente sejam sobre computabilidade clássica: >> - Lars Kristiansen and Juvenal Murwanashyaka. On Interpretability between >> some weak essential undecidable theories >> - Russell Miller. Non-coding enumeration operators >> - Iosif Petrakis. Functions of Baire class one over a Bishop topology >> >> Inclui o terceiro na lista, porque as funções totais (não necessariamente >> computáveis) formam um espaço de Baire. >> >> E entre as 14 apresentações informais apenas encontrei uma que pode ser >> que seja sobre computabilidade clássica: >> - James Walsh and Patrick Lutz. Incompleteness and jump hierarchies. >> >> Em dezembro de 2018 participei no CCR2018 e lá aconteceu algo similar: >> somente dois trabalhos foram sobre computabilidade clássica, um era de Rod >> Downey e o outro foi o meu junto com o meu orientador prof. Benjamín >> Bedregal. >> >> Gostaria de saber se vocês têm a mesma percepção minha e se tem mais >> alguém dentro do Brasil que trabalhe com computabilidade clássica. >> >> Abraços, >> Claudio Callejas. >> >> >> >> >> >> El lun., 8 jun. 2020 a las 16:19, Joao Marcos (<[email protected]>) >> escribió: >> >>> Note: "Registration is now open and free of charge." >>> >>> JM >>> >>> ---------- Forwarded message --------- >>> >>> COMPUTABILITY IN EUROPE 2020 CALL FOR PARTICIPATION >>> >>> CiE 2020: >>> Virtually in Salerno, Italy >>> Due to the Covid-19 outbreak, this edition will be an online conference. >>> >>> >>> June 29 - July 3, 2020 >>> https://www.acie.eu/cie-conference-series/cie2020 >>> https://www.acie.eu >>> >>> IMPORTANT DATES: >>> >>> 15 JUNE: REGISTRATION DEADLINE >>> >>> Registration (https://www.acie.eu/cie-conference-series/cie2020) is now >>> open and free of charge. Registration is mandatory to attend the talks. >>> >>> CiE 2020 is the 16th conference organized by CiE (Computability in >>> Europe), a European association of mathematicians, logicians, computer >>> scientists, philosophers, physicists and others interested in new >>> developments in computability and their underlying significance for the >>> real world. >>> >>> Previous meetings have taken place in Amsterdam (2005), Swansea (2006), >>> Siena (2007), Athens (2008), Heidelberg (2009), Ponta Delgada (2010), >>> Sofia (2011), Cambridge (2012), Milan (2013), Budapest (2014), Bucharest >>> (2015), Paris (2016), Turku (2017), Kiel (2018), and Durham (2019). >>> >>> TUTORIALS >>> >>> _Fine-Grained Complexity_ - Virginia Vassilevska Williams (MIT) >>> _Computable Analysis_ - Martin Ziegler (Korea Advanced Institute of >>> Science and Technology) >>> >>> INVITED TALKS: >>> >>> _Centralities in Network Analysis_ -- Paolo Boldi (University of Milan) >>> _A game-theoretic approach for the automated synthesis of complex >>> systems _-- Véronique Bruyère (University of Mons) >>> On-the-fly classification of structures -- Ekatarina Fokina (Vienna >>> University of Technology) >>> _A Survey on Analog Models of Computation_ -- Amaury Pouly (CNRS Paris) >>> _On the Repetitive Structure of Words_ -- Antonio Restivo (University of >>> Palermo) >>> _Molecular algorithms using reprogrammable DNA self-assembly_ -- Damien >>> Woods (Maynooth University) >>> >>> HOSTED BY: >>> >>> Department of Computer Science, University of Salerno >>> Due to the Covid-19 outbreak, this edition will be an online conference. >>> >>> >>> SPECIAL SESSIONS: >>> >>> Algorithmic Learning Theory >>> Combinatorial String Matching >>> Computable Topology >>> HAPOC session on Fairness in Algorithms >>> Large scale Bioinformatics and Computational Sciences >>> Modern aspects of Formal Languages >>> >>> The CiE conferences serve as an interdisciplinary forum for research in >>> all aspects of computability, foundations of computer science, logic, >>> and theoretical computer science, as well as the interplay of these >>> areas with practical issues in computer science and with other >>> disciplines such as biology, mathematics, philosophy, or physics. >>> >>> -- >>> Você está recebendo esta mensagem porque se inscreveu no grupo >>> "LOGICA-L" dos Grupos do Google. >>> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, >>> envie um e-mail para [email protected]. >>> Para ver esta discussão na web, acesse >>> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAO6j_Lh21%3DoALN9FEpJmAA1KrvXSmSbPYTdYnCF%2BYVRNmrqL8w%40mail.gmail.com >>> . >>> >> -- >> Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos >> Grupos do Google. >> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, >> envie um e-mail para [email protected]. >> Para ver essa discussão na Web, acesse >> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAE_57e0dLDAC8Fuqz%3DHjriXTtMw3M2tnfXszqpPCx5QB%3DoO_2Q%40mail.gmail.com >> <https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAE_57e0dLDAC8Fuqz%3DHjriXTtMw3M2tnfXszqpPCx5QB%3DoO_2Q%40mail.gmail.com?utm_medium=email&utm_source=footer> >> . >> > -- > Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos > Grupos do Google. > Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie > um e-mail para [email protected]. > Para ver essa discussão na Web, acesse > https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAExWzUJRUcKvdGa-bRnnrgoo-b%3D4Tr5N%3Dsm%2BJ-tp2ubRMicMNw%40mail.gmail.com > <https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAExWzUJRUcKvdGa-bRnnrgoo-b%3D4Tr5N%3Dsm%2BJ-tp2ubRMicMNw%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos Grupos do Google. Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para [email protected]. Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAJrBeCWgXqEQAs3THWE5OvUmi1TF%3DYpSGEmVtH7m1pkvoa%3DnBg%40mail.gmail.com.
