Computare

O problema mais notório da Ciência da Computação Teórica permanece em aberto, mas as tentativas de resolvê-lo levaram a profundas percepções. Os jornalistas de ciência e tecnologia se orgulham da capacidade de explicar ideias complicadas de maneiras acessíveis, mas existem alguns princípios técnicos que encontramos com tanta frequência em nossos relatórios que parafraseando-os ou escrevendo em torno deles começam a sentir falta de uma grande parte da história. Assim, em uma nova série de artigos chamada "Explained", a equipe do MIT News Office irá explicar algumas das ideias centrais nas áreas que eles cobrem, como pontos de referência para futuros relatórios sobre a pesquisa do MIT. No episódio de Halloween de Os Simpsons de 1995, Homer Simpson encontra um portal para a misteriosa Terceira Dimensão, atrás de uma estante de livros, e desesperado para escapar de suas cunhadas, ele mergulha. Ele se encontra vagando por uma superfície escura gravada com ...

Assumimos que o leitor esteja familiarizado com as noções de Indecidibilidade, Reduções de Turing, Complexidade de Kolmogorov, Problema da Parada e assuntos relacionados. A prova de que a incomputabilidade da Complexidade de Kolmogorov implica a indecidibilidade do Problema da Parada pode ser encontrada em muitas palestras, notas e livros; geralmente, a prova assume que o Problema da Parada é decidível e deriva a computabilidade da complexidade de Kolmogorov, que é uma contradição. Em outras palavras, dado um oráculo para o Problema da Parada, podemos calcular a complexidade de Kolmogorov de uma cadeia x. Mas também podemos derivar a incomputabilidade da Complexidade de Kolmogorov a partir da indecidibilidade do Problema da Parada; a prova é "menos popular", mas mesmo assim pode ser encontrada depois de algumas pesquisas no Google. Por exemplo, o relatório técnico: Gregory J. Chaitin, Asat Arslanov e Cristian Calude: Program-size Complexity Computes the Halting Prob...

Um grande avanço revela conexões profundas entre as classes de problemas que os computadores podem  —e não podem— possivelmente fazer. À primeira vista, a grande novidade da conferência de verão sobre a teoria da computação pareceu ser uma decepção. Por mais de 40 anos, pesquisadores tentaram encontrar uma maneira melhor de comparar duas sequências arbitrárias de caracteres, como as longas sequências de letras químicas dentro das moléculas de DNA. O algoritmo mais usado é lento e não é tão inteligente: ele segue passo a passo as duas listas, comparando valores em cada etapa. Se um método melhor para calcular essa "distância de edição" pudesse ser encontrado, os pesquisadores seriam capazes de comparar rapidamente genomas completos ou grandes conjuntos de dados, e cientistas da computação teriam uma nova ferramenta poderosa com a qual poderiam tentar resolver problemas adicionais no campo. No entanto, em um artigo apresentado no ACM Symposium on Theory of Computing, doi...

Uma corrida para decifrar os algoritmos do cérebro pode revolucionar o aprendizado de máquina. Leve uma criança de três anos para o zoológico e ela intuitivamente sabe que a criatura de pescoço comprido mordiscando folhas é a mesma coisa que a girafa em seu livro de fotos. Essa façanha superficialmente fácil é, na realidade, bastante sofisticada. O desenho animado é uma silhueta congelada de linhas simples, enquanto o animal vivo é inundado de cor, textura, movimento e luz. Ele pode se contorcer em diferentes formas e parece diferente de todos os ângulos. Os seres humanos se destacam nesse tipo de tarefa. Podemos facilmente compreender os recursos mais importantes de um objeto de apenas alguns exemplos e aplicar esses recursos ao desconhecido. Os computadores, por outro lado, normalmente precisam classificar um banco de dados inteiro de girafas, mostrado em muitos cenários e de diferentes perspectivas, para aprender a reconhecer com precisão o animal. A ident...