Em uma palestra, um professor mencionou que os computadores modernos não têm tanto poder computacional quanto uma máquina de Turing porque não têm memória infinita e, como nenhum computador pode ter memória infinita, a máquina de Turing é, portanto, inatingível e simplesmente representa o limite superior. de computação. Existe uma medida ou definição de quais problemas (ou classe de problemas) estão além do alcance de nosso poder de computação por causa disso?
computability
JustAnotherSoul
fonte
fonte
Respostas:
Se pensarmos no universo como finito, qualquer coisa que precise de mais memória do que essa quantidade finita está além da nossa capacidade computacional.
No entanto, esse não é um bom modelo para estudar a computabilidade, o modelo da máquina de Turing funciona muito melhor na realidade e é por isso que o usamos para estudar a computação em computadores reais. Uma máquina de Turing realmente não precisa de uma quantidade infinita de memória, ela precisa apenas de uma quantidade ilimitada de memória. Por exemplo, podemos fornecer memória adicional a um computador ao longo do tempo (como o computador precisa de mais e mais memória) e, em seguida, temos algo semelhante a uma máquina de Turing. Se assumirmos que temos tempo e memória ilimitados para concluir nosso cálculo, a máquina de Turing captura esse conceito de computabilidade em princípio bastante bem.
Verifique o artigo da Wikipedia sobre máquinas de Turing, há uma seção que discute a relevância do modelo.
fonte
Você pode considerar o autômato vinculado linear e os idiomas correspondentes são os idiomas sensíveis ao contexto . Veja a Hierarquia de Chomsky para saber quais idiomas estão além do alcance de tais autômatos.
btw, em certo sentido, alguns problemas "inacessíveis" agora estão ao nosso alcance, devido ao poder de computação restrito!
Por exemplo, o problema de parada para máquinas de Turing é indecidível, mas é decidível para autômatos com limites lineares.
fonte
A teoria da computação é uma abstração do mundo real. De muitas maneiras, a abstração não é uma boa opção para o mundo real. Por um lado, não podemos fabricar computadores com memória ilimitada; portanto, não podemos nem fazer máquinas para reconhecer linguagens regulares arbitrárias - ou mesmo linguagens finitas arbitrárias!
Porém, isso não é um problema muito grande; no mundo real, não podemos sequer construir entradas de qualquer tamanho arbitrário e, mesmo que pudéssemos, não estaríamos por aqui o tempo suficiente para ver a resposta.
Num sentido estrito, então, não: a classe de computadores fisicamente realizáveis é estritamente menos poderosa do que a classe das máquinas de Turing. É estritamente menos poderoso que a classe de autômatos finitos também.
fonte