4-espaço complexo projetivo onde coisas excitantes acontecem especialistas de cuidado de artrite de maryland

Se ela se autodestrói prematuramente, depende dos sinais que recebeu de seus vizinhos. Efetivamente, a máquina recebe um sinal (um inteiro positivo entre 1 e 7, inclusive) de cada um dos vizinhos (até quatro), e um 0 a partir de quaisquer espaços vazios se houver menos de quatro vizinhos. Em seguida, calcula a quantidade, em que (a, b, c, d) são os quatro sinais de entrada e os índices em uma tabela de consulta do elemento 4096 para recuperar um valor entre 0 e 7 (o novo “estado” da máquina). Se 0, ele se autodestrói imediatamente sem construir filhos; se diferente de zero, constrói uma máquina filha em cada espaço livre. Finalmente, transmite o novo estado como um sinal para todos os quatro vizinhos, antes de se autodestruir de qualquer maneira.

Ao fazê-lo, esse replicador semelhante a um loop se comporta como uma única célula em qualquer autômato celular de quatro estados de oito estados; a regra é especificada pela tabela de consulta dentro do replicador. Chamamos isso de construção de uma metacélula porque ela emula uma única célula em um autômato celular (de 8 estados) usando uma grande coleção de células no autômato celular subjacente (2 estados de 9 vizinhos).

Esta não é a primeira metacélula (a célula de vida da unidade do sino de david é o primeiro exemplo), mas é única em ter um estado fundamental de 0-população. Como tal, ao contrário da célula vital da unidade (que requer que todo o plano seja revestido com infinitas cópias), qualquer padrão finito na regra emulada pode ser percebido como um padrão finito na regra subjacente.

Se considerarmos o determinante da matriz M formada pelos coeficientes desses polinômios, obtemos um polinômio homogêneo grau ½ n (n − 1) nas raízes n (n − 1). Esse determinante pode ser visto como invariante ao adicionar uma constante a todas as raízes, mas não é invariante em escala porque o grau é diferente de zero. Isso pode ser alterado dividindo-se por uma constante de normalização, gerando uma função racional δ:

Note que δ não é apenas invariante em escala e em translação, mas também é invariante ao mesmo tempo em que substitui todas as raízes por seus recíprocos. Isto significa que δ é invariante sob a totalidade do grupo möbius, que corresponde naturalmente ao grupo de transformações projetivas de preservação de orientação que fixam a bola unitária. Como δ é adimensional, é razoável conjeturar o seguinte problema mais forte:

Atiyah distribuiu esse problema para tantos matemáticos quanto pôde, oferecendo uma garrafa de champanhe e um convite para o próximo HLF como recompensa para quem pudesse resolvê-lo. Fiquei perplexo com o fato de que atiyah – que é um “construtor de teoria” em vez de um “solucionador de problemas” (e.G. Erdös) – estaria interessada em um problema que, apesar de elegante, aparentemente não tem conexão com a matemática séria da pesquisa. Eu me perguntei se ele estava seguindo os passos da pequena floresta, que costumava usar versões disfarçadas da hipótese de riemann e dar a estudantes de doutorado como problemas de pesquisa.

Claro, eu não sabia na época qual grande problema que atiyah havia reduzido a esse lema. No ano passado, no entanto, ele fez uma palestra em Cambridge apresentando uma prova dessa desigualdade geométrica. Eu não estava na palestra, mas aparentemente envolvia expressar o logaritmo de | δ | (possivelmente negada) como a entropia de von neumann de algum sistema, e provando que a versão mais forte da conjectura como um corolário da entropia não é decrescente.

Na manhã de segunda-feira, no entanto, atiyah estará apresentando uma prova da hipótese de riemann em uma palestra de 45 minutos no fórum de laureado de heidelberg, três anos depois que ele nos apresentou esse problema. O resumo da próxima palestra menciona que ela se baseia no trabalho de von neumann, que é tentadoramente consistente com a minha previsão de que sua conjectura de “aponta em uma bola” era meramente o lema restante necessário para resolver um enorme problema não resolvido!

Uma rede de classificação é um algoritmo de ordenação muito mais restrito, em que a única operação permitida é a instrução de intercâmbio de comparação CMPX (i, j). Isso compara os objetos nas posições i e j, trocando-os se estiverem na ordem errada e não revelando nenhuma informação. Aqui estão as redes de triagem mais conhecidas em 9 e 12 elementos, fotografadas da arte da programação de computadores de Donald Knuth:

Eu continuei a transcrever a rede de triagem do diagrama acima para o código CUDA. Como um mero mortal, eu não estava totalmente convencido de tê-lo copiado sem falhas, então recorri à construção de um teste para verificar a exatidão da rede transcrita. Preferindo fazer isso em uma linguagem de alto nível como python, recorri aos meus truques habituais de escrever um único arquivo que é válido em duas linguagens e incorporá-lo ao código-fonte por meio de uma linha inócua: #include “sorting_network. Py ”

Examinando o componente python do código, você pode notar que ele testa apenas as 2 ^ 12 sequências binárias diferentes, em vez das 12! Diferentes conjuntos totalmente ordenados. É uma propriedade geral das redes de comparação que basta apenas testar sequências binárias para provar que a rede pode ordenar sequências arbitrárias; isso é conhecido como o princípio 0-1. Fusão do bitonter de Batcher

Qual é o número mínimo de portas CMPX necessárias para classificar n objetos? E qual é a profundidade mínima do circuito? O algoritmo ingênuo de classificação de bolhas mostra que uma contagem de portas de O (n ^ 2) e uma profundidade de circuito de O (n) são ambas atingíveis. Da mesma forma, a contagem de gate deve ser pelo menos o logaritmo binário de n! (como acontece com qualquer algoritmo de ordenação baseado em comparação) que fornece um limite inferior de Ω (n log n) para a contagem de portas e Ω (log n) para a profundidade.

Concentrando-se apenas na metade não constante, nossa tarefa é reduzida ao problema mais simples de ordenar uma sequência binária que alterna no máximo duas vezes entre uma série de zeros e uma sequência de uns. Podemos dividir o efeito da caixa rosa em dois módulos: um que inverte uma das duas metades (decidimos qual metade!), Seguido por um que se comporta de maneira idêntica a uma caixa marrom. Observe que, como antes, uma das duas metades da caixa rosa deve, portanto, ser constante, e a outra deve ser novamente uma seqüência binária que comuta no máximo duas vezes. Por indução, o resultado segue.

Uma versão simplificada da construção (por paterson, 1990) é descrita aqui. O documento original fornece constantes explícitas, mostrando que uma profundidade ~ 6100 log (n) é possível, em comparação com ~ ½ log (n) ^ 2 para o mergesort bitônico do batcher. Em outras palavras, o limite para a mudança de fusões bitônicas para a variação de AKS do paterson ocorre quando n é aproximadamente 2 ^ 12200.

Uma melhoria adicional por chvatal reduz a constante assintótica de 6100 para 1830, e realmente fornece uma ligação explícita (não-assintótica): desde que n ≥ 2 ^ 78, há uma rede de triagem de profundidade 1830 log (n) – 58657. Isto reduz o ponto de cruzamento para exatamente n ≥ 2 ^ 3627. Como Knuth observou, isso ainda é muito maior do que o número de átomos no universo observável, então a utilidade prática do algoritmo de classificação do AKS é questionável.

Curiosamente, esta não é a primeira vez que existe um algoritmo assintoticamente impressionante chamado AKS após seus autores: um conjunto de três estudantes indianos de graduação em tecnologia {agrawal, kayal, saxena} encontrou o primeiro algoritmo de tempo polinomial determinístico incondicional para testar se um o número de n dígitos é primo. Este algoritmo O (n ^ (6 + o (1)) tende a não ser usado na prática, porque todos acreditam na hipótese generalizada de riemann e sua implicação de que o O (n ^ (4 + o (1)) determinístico miller-rabin algoritmo está correto.