Fwd: CfPart CiE 2020, Virtual, 29 Jun - 3 Jul 2020

[Joao Marcos]

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.

[Claudio Andrés Callejas Olguín]

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.

--
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 logica-l+u...@dimap.ufrn.br.
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.

[Rodrigo Freire]

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

--
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 logica-l+u...@dimap.ufrn.br.

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.

[Anderson Beraldo de Araújo]

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

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.