Inteligência Artificial
Os computadores estão ficando cada vez mais poderosos e capazes, mas tudo tem limites. Yuichiro Chino/Moment via Getty Images
Limites da computação: um cientista da computação explica por que, mesmo na era da IA, alguns problemas são muito difíceis.
Jie Wang não trabalha, consulta, possui ações ou recebe financiamento de qualquer empresa ou organização que se beneficiaria deste artigo e não revelou nenhuma afiliação relevante além de sua nomeação acadêmica.
Fortalecidos por tecnologias de inteligência artificial, os computadores hoje podem se envolver em conversas convincentes com pessoas, compor músicas , pintar pinturas , jogar xadrez e ir , e diagnosticar doenças , para citar apenas alguns exemplos de suas proezas tecnológicas.
Esses sucessos podem ser usados para indicar que a computação não tem limites. Para ver se esse é o caso, é importante entender o que torna um computador poderoso.
Existem dois aspectos no poder de um computador: o número de operações que seu hardware pode executar por segundo e a eficiência dos algoritmos que executa. A velocidade do hardware é limitada pelas leis da física. Algoritmos – basicamente conjuntos de instruções – são escritos por humanos e traduzidos em uma sequência de operações que o hardware do computador pode executar. Mesmo que a velocidade de um computador atinja o limite físico, os obstáculos computacionais permanecem devido aos limites dos algoritmos.
Esses obstáculos incluem problemas que são impossíveis de serem resolvidos por computadores e problemas que são teoricamente solucionáveis, mas na prática estão além das capacidades até mesmo das versões mais poderosas dos computadores atuais imagináveis. Matemáticos e cientistas da computação tentam determinar se um problema pode ser resolvido testando-o em uma máquina imaginária.
Uma máquina de computação imaginária.
A noção moderna de algoritmo, conhecida como máquina de Turing, foi formulada em 1936 pelo matemático britânico Alan Turing . É um dispositivo imaginário que imita como os cálculos aritméticos são feitos com um lápis no papel. A máquina de Turing é o modelo no qual todos os computadores atuais são baseados.
Para acomodar cálculos que precisariam de mais papel se fossem feitos manualmente, supõe-se que o suprimento de papel imaginário em uma máquina de Turing seja ilimitado. Isso é equivalente a uma fita ilimitada imaginária, ou “fita”, de quadrados, cada um dos quais está em branco ou contém um símbolo.
A máquina é controlada por um conjunto finito de regras e começa com uma sequência inicial de símbolos na fita. As operações que a máquina pode realizar são mover-se para um quadrado vizinho, apagar um símbolo e escrever um símbolo em um quadrado em branco. A máquina calcula realizando uma sequência dessas operações. Quando a máquina termina, ou “pára”, os símbolos que permanecem na fita são a saída ou o resultado.
O que é uma máquina de Turing?
A computação geralmente envolve decisões com respostas sim ou não. Por analogia, um exame médico (tipo de problema) verifica se a amostra de um paciente (uma instância do problema) tem um determinado indicador de doença (resposta sim ou não). A instância, representada em uma máquina de Turing em formato digital, é a sequência inicial de símbolos.
Um problema é considerado “resolvível” se uma máquina de Turing pode ser projetada para parar para cada instância, seja ela positiva ou negativa, e determinar corretamente qual resposta a instância produz.
Nem todo problema pode ser resolvido.
Muitos problemas podem ser resolvidos usando uma máquina de Turing e, portanto, podem ser resolvidos em um computador, enquanto muitos outros não. Por exemplo, o problema do dominó, uma variação do problema dos ladrilhos formulado pelo matemático sino-americano Hao Wang em 1961, não tem solução.
A tarefa é usar um conjunto de dominós para cobrir uma grade inteira e, seguindo as regras da maioria dos jogos de dominó, combinar o número de pontos nas extremidades dos dominós adjacentes. Acontece que não existe um algoritmo que possa começar com um conjunto de dominós e determinar se o conjunto cobrirá ou não completamente a grade.
Mantendo-o razoável
Vários problemas solucionáveis podem ser resolvidos por algoritmos que param em um período de tempo razoável. Esses “ algoritmos de tempo polinomial ” são algoritmos eficientes, o que significa que é prático usar computadores para resolver instâncias deles.
Milhares de outros problemas solucionáveis não são conhecidos por terem algoritmos de tempo polinomial, apesar dos intensos esforços contínuos para encontrar tais algoritmos. Estes incluem o Problema do Caixeiro Viajante.
O Problema do Caixeiro Viajante pergunta se um conjunto de pontos com alguns pontos diretamente conectados, chamado grafo, tem um caminho que começa em qualquer ponto e passa por todos os outros pontos exatamente uma vez, e volta ao ponto original. Imagine que um vendedor deseja encontrar uma rota que passe por todas as residências de um bairro exatamente uma vez e retorne ao ponto de partida.
O Problema do Caixeiro Viajante fica rapidamente fora de controle quando você vai além de alguns destinos.
Esses problemas, chamados de NP-completos , foram formulados e demonstrados de forma independente no início dos anos 1970 por dois cientistas da computação, o americano canadense Stephen Cook e o ucraniano americano Leonid Levin . Cook, cujo trabalho veio primeiro, recebeu o Prêmio Turing de 1982, o mais alto em ciência da computação, por este trabalho.
O custo de saber exatamente.
Os algoritmos mais conhecidos para problemas NP-completos buscam essencialmente uma solução a partir de todas as respostas possíveis. O Problema do Caixeiro Viajante em um gráfico de algumas centenas de pontos levaria anos para ser executado em um supercomputador. Esses algoritmos são ineficientes, o que significa que não há atalhos matemáticos.
Algoritmos práticos que abordam esses problemas no mundo real podem oferecer apenas aproximações, embora as aproximações estejam melhorando . Se existem algoritmos eficientes de tempo polinomial que podem resolver problemas NP-completos está entre os sete problemas abertos do milênio publicados pelo Clay Mathematics Institute na virada do século 21, cada um com um prêmio de US$ 1 milhão.
Além de Turing.
Poderia haver uma nova forma de computação além da estrutura de Turing? Em 1982, o físico americano Richard Feynman , ganhador do Prêmio Nobel, apresentou a ideia de computação baseada na mecânica quântica.
O que é um computador quântico?
Em 1995, Peter Shor, um matemático aplicado americano, apresentou um algoritmo quântico para fatorar números inteiros em tempo polinomial . Os matemáticos acreditam que isso é insolúvel por algoritmos de tempo polinomial na estrutura de Turing. Fatorar um inteiro significa encontrar um inteiro menor maior que 1 que possa dividir o inteiro. Por exemplo, o inteiro 688.826.081 é divisível por um inteiro menor 25.253, porque 688.826.081 = 25.253 x 27.277.
Um algoritmo importante chamado algoritmo RSA , amplamente utilizado para proteger as comunicações de rede, baseia-se na dificuldade computacional de fatorar inteiros grandes. O resultado de Shor sugere que a computação quântica, caso se torne realidade, mudará o cenário da segurança cibernética .
Um computador quântico completo pode ser construído para fatorar números inteiros e resolver outros problemas? Alguns cientistas acreditam que pode ser. Vários grupos de cientistas ao redor do mundo estão trabalhando para construir um, e alguns já construíram computadores quânticos de pequena escala.
No entanto, como todas as novas tecnologias inventadas antes, é quase certo que surgirão problemas com a computação quântica que imporiam novos limites.
Autor
Jie Wang
Professor de Ciência da Computação, UMass Lowell
declaração de divulgação.
Acreditamos no livre fluxo de informações
Republique nossos artigos gratuitamente, online ou impressos, sob licença Creative Commons.republicar este artigo.
Crédito: https://theconversation.com
Tradução: https://vega-conhecimentos.com
