As máquinas de Turing assumem algo infinito em algum momento?

Em uma pergunta anterior O que exatamente é um algoritmo? , Perguntei se ter um "algoritmo" que retorna o valor de uma função com base em uma matriz de valores pré-computados era um algoritmo.

Uma das respostas que chamou minha atenção foi esta:

O exemplo fatorial entra em um modelo diferente de computação, chamado computação não uniforme. Uma Máquina de Turing é um exemplo de um modelo uniforme de computação: possui uma descrição única e finita e funciona para entradas de tamanho arbitrariamente grande. Em outras palavras, existe uma TM que resolve o problema para todos os tamanhos de entrada.

Agora, poderíamos considerar a computação da seguinte forma: Para cada tamanho de entrada, existe uma TM (ou algum outro dispositivo computacional) que resolve o problema. Esta é uma pergunta muito diferente. Observe que uma única TM não pode armazenar o fatorial de cada número inteiro, uma vez que a TM possui uma descrição finita. No entanto, podemos fazer uma TM (ou um programa em C) que armazene os fatoriais de todos os números abaixo de 1000. Em seguida, podemos criar um programa que armazene os fatoriais de todos os números entre 1000 e 10000. E assim por diante.

Toda TM realmente não assume alguma maneira de lidar com o infinito? Quero dizer, mesmo uma TM com uma descrição finita que computa o fatorial de qualquer número N através do algoritmo

 int fact(int n) 
 { 
 int r = 1; 
 for(int i=2;i<=n;i++) 
 r = r*i; 
 return r; 
 } 

contém a suposição de que uma TM possui o "hardware" para comparar números de tamanho arbitrário por meio do comparador "<=" e também ADDers para incrementar i até um número arbitrário, além disso , a capacidade de representar números de tamanho arbitrário.

Estou esquecendo de algo? Por que a abordagem que apresentei na minha outra pergunta é menos viável em relação ao infinito do que esta?

<=<=$Q$$\Sigma$

<=$|Q|$$|\Sigma|$

As máquinas de Turing não "realmente lidam com o infinito": elas lidam com coisas finitas ilimitadas, pelo menos em sua definição padrão. A entrada é uma sequência finita e, após qualquer número finito de etapas, a máquina apenas examinou ou gravou em um número finito de células de fita. Não há limite no tamanho da entrada ou no número de etapas da computação, mas a entrada é finita e, após qualquer número finito de etapas, apenas uma quantidade finita de saída foi produzida.

Penso que a distinção importante a fazer é que a descrição da máquina de Turing é finita, assim como a entrada da máquina, enquanto a fita que ela usa como memória é infinita. O TM é uma máquina principalmente finita, que usa uma fita finita. Considere a fita como composta de células, onde cada célula pode conter um único valor. A entrada para a TM está gravada na fita.

A descrição de uma TM é um conjunto finito de tuplas <current state, input, output, move, next state>.

A cada passo, o que deve ser feito é encontrado combinando o estado e a entrada atuais. Por exemplo, estamos no estado 0, e lemos um 1, então encontramos a tupla que começa e <0, 1, ...>depois escrevemos um novo valor na célula atual, movemos para a esquerda ou para a direita (acho que a definição clássica também permite permanecer na mesma célula também) e, em seguida, mude para um novo estado.

Portanto, para o seu exemplo, você precisaria de uma descrição infinitamente grande da TM (um número infinito de <current state, input, output, move, next state>tuplas) ou incluiria as informações de pesquisa na entrada da TM. Acredito que a entrada para uma TM é definida como finita. Portanto, isso provavelmente não é algo que você possa fazer com uma máquina de Turing definida de forma clássica.

O exemplo de Fibonacci, por outro lado, pode ser calculado em binário com um número finito de tuplas para descrever a MT e possui uma entrada finita.

Em poucas palavras : a Turing Machine pode fazer cálculos infinitos (finitamente especificados) em dados infinitos (finitos) e produzir resultados infinitos (especificados finamente). A idéia básica é que esses infinitos possam ser definidos como o limite de entidades finitas, definidas de maneira matematicamente apropriada. Essa é a base da semântica matemática da computação. Se você considerar programas em vez de Máquinas de Turing, esses programas também poderão conter (infinitamente especificadas) estruturas de dados infinitas. O caso de uma função tabulada factcomo um possível algoritmo é analisado no final, como um programa ou como um modelo de TM, com uma dica sobre a relação com a avaliação lenta de objetos infinitos.

Com muito mais detalhes

Em relação à sua pergunta final, uma TM não calcula números arbitrários, mas a representação simbólica desses números como longas sequências arbitrárias (sem limites) de símbolos que os representam. Por uma codificação adequada do módulo, é correto que eles possam comparar ou fazer aritmética com esses números através dessas representações.

Mas a pergunta original é sobre o papel do infinito nas Máquinas de Turing em geral.

Uma resposta comum a essa pergunta é que as Máquinas de Turing nunca lidam com o infinito. Eles são definidos de forma finita, e o que quer que computem é calculado em tempo finito em uma parte finita da fita (portanto, uma fita finita maior é suficiente). O que é verdade é que os requisitos de tempo de espaço da TM são ilimitados, o que não é o mesmo que infinito.

Portanto, qualquer resposta calculada por uma TM também pode ser calculada por um autômato de estado finito (FSA), que é "até certo ponto" uma maneira de analisar a tabulação. A dificuldade é que alguns tamanhos de entrada (quase sempre chega a isso, apenas para ler a entrada) excederão o tamanho do autômato. Mas então, podemos apenas usar um maior. Portanto, se quisermos considerar o tamanho da entrada ilimitada, precisamos de uma sequência infinita de FSA que possa fazer o cálculo. Na verdade, podemos precisar de uma máquina de estado finito um pouco mais complexa do que a FSA tradicional, pois pode haver uma saída a ser calculada (em vez de uma resposta sim-não), mas provavelmente um transdutor de estado finito deve ser necessário.

Portanto, se estivermos olhando para um problema que possui um conjunto infinito de instâncias, como calcular um GCD ou simplesmente usar aritmética em números inteiros de tamanho arbitrário, veremos que o infinito está voltando para nós pela porta dos fundos, como esse infinito conjunto de FSA.

$\pi$

Por outro lado, podemos substituir isso por uma sequência infinita de cálculos finitos por máquinas finitas. Mas estamos trapaceando.

Do ponto de vista físico, é o melhor que podemos fazer. Sabemos apenas construir máquinas finitas, pelo menos de acordo com o atual estado da arte da física, que não se espera que mude muito sobre esse assunto no futuro próximo.

Mas como podemos lidar com esses infinitos de maneira consistente e tratável do ponto de vista matemático.

Quando você considera um conjunto infinito de FSA que podem cooperar para calcular um conjunto infinito de respostas, não é possível fazê-lo arbitrariamente. Você precisa de algumas salvaguardas para garantir que o que você está fazendo faça sentido. É sabido que você pode criar trivialmente qualquer conjunto com uma união infinita de conjuntos regulares, na verdade com uma união infinita de conjuntos singleton. Portanto, considerar uniões infinitas arbitrárias de autômatos sem nenhuma restrição o levará a lugar nenhum. Você até considera o mesmo conjunto de autômatos que fornece respostas inconsistentes.

O que você realmente deseja é definir uma noção de consistência. Mas isso requer algumas precauções. Vamos supor que você esteja usando uma sequência infinita de autômatos para simular uma MT que responda sim ou não ou não pare. O problema é que uma FSA sempre interromperá com uma resposta, como sim ou não. Mas se você usar um FSA que não seja realmente grande o suficiente para a entrada escolhida, o que deve responder. Sim e não são reservados para os casos em que a FSA realmente encerrou o cálculo da MT, e o uso de uma dessas respostas com um cálculo inacabado só levaria à confusão. O que você quer é uma resposta que diga: " desculpe, eu sou muito pequena e não posso dizer. Por favor, tente com um cara maior da família ". Em outras palavras, você deseja uma resposta como excesso ou não sabe$\bot$

Portanto, você precisa de autômatos com três tipos de estados: aceitando, não aceitando e indefinido. Um estado indefinido pode ser visto como um estado que representa uma parte ausente do autômato que força a computação a parar. Portanto, quando a computação pára, dependendo do estado em que ele pára, você obtém a resposta sim , não ou indefinida .

Agora, você vê que o que você deseja são sequências infinitas de autômatos que são consistentes . Ambos sim e não são consistentes com indefinido , mas sim não é consistente com nenhuma . Então, dois autômatos são consistentes quando fornecem respostas consistentes na mesma entrada.

$\pi$$3.14\bot\bot\bot\bot...$$3.1415\bot\bot\bot\bot...$$\bot.\bot5159\bot\bot\bot\bot...$$3.1416\bot\bot\bot\bot...$$3.1416\bot\bot\bot\bot...$$\pi$

Não desenvolverei mais esses aspectos teóricos, o que é um pouco estranho quando baseado em Máquinas de Turing. O ponto é que esses conceitos levam à idéia de que os domínios da computação (sejam dados ou máquinas) formam estruturas matemáticas como redes, nas quais objetos infinitos podem ser adequadamente definidos como os limites de seqüências infinitamente crescentes (isto é, melhor e melhor definidas) de objetos finitos. Definir as seqüências infinitas requer um pouco mais de aparato e uma noção de continuidade. Fundamentalmente, trata-se da teoria da semântica de Dana Scott e fornece uma visão um pouco diferente dos conceitos de computabilidade.

Então, máquinas de Turing ou outros dispositivos formais que podem fazer "computação infinita" podem ser definidos como limites de sequências de aproximações finitas das máquinas, cada vez mais definidas. O mesmo vale para quaisquer dados que as máquinas calculem, sejam de entrada ou de saída.

O documento mais simples que eu já li sobre isso é um conjunto escrito à mão de notas de aula de Dana Scott, muitas vezes referidas como notas de aula de Amsterdã. Mas não consegui encontrá-lo na web. Qualquer ponteiro para uma cópia (mesmo incompleta, como eu tenho parte dela) seria bem-vindo. Mas você pode olhar para outras publicações anteriores de Scott, como o esboço de uma teoria matemática da computação .

Voltar ao exemplo inicial da pergunta

Esses conceitos de aproximação se aplicam aos dados e aos programas. A função facté definida recursivamente, o que significa que é o ponto menos fixo de uma funcional que pode ser usada para calcular uma sequência convergente de aproximação finita de fact. Essa sequência de funções finitas cada vez mais definidas converge para uma entidade infinita que é o que você chama de função fact.

fact$\bot$

É verdade que, se você considerar o modelo elementar de computação da MT, uma matriz infinita não poderá ser expressa nesse formalismo. Isso não significa que não faria sentido. Uma máquina de Turing poderia ter uma segunda fita que deveria ser inicializada com os valores tabulados de algumas funções, como fact. Ele não altera o poder computacional da TM, desde que essa função seja computável, ou seja, desde que a tabela possa ser inicializada com um cálculo infinito de outra TM que possa calcular todos os pares de valor de argumento para a função relevante.

Mas, na prática, você não pode concluir um cálculo infinito. Portanto, a maneira correta de fazer isso é calcular a tabela preguiçosamente, ou seja, preencher as entradas somente quando necessário. É exatamente isso que é feito com a memorização, que é a resposta que lhe dei, com justificativas diferentes, para sua pergunta anterior.

A essência desta resposta é que as Máquinas de Turing podem imitar qualquer coisa que possamos programar e programamos cálculos em, com e de objetos infinitos.

Esta é uma segunda resposta focada mais na pergunta específica do que no arcabouço teórico geral que justifica a resposta, e seria definitivamente necessária para responder ao título mais geral da pergunta. É totalmente compatível com minhas respostas anteriores às perguntas do OP, ambas O que exatamente é um algoritmo? e As máquinas de turing assumem algo infinito em algum momento? , respostas nas quais desenvolvi mais o contexto teórico. Isso pode ser visto como resposta a ambas as perguntas.

As máquinas de Turing têm a capacidade de lidar com o infinito , como todos os modelos computacionais completos de Turing, embora apenas com o infinito infinito. Nosso problema é que podemos observar apenas parte desse infinito, mas temos que considerar o todo, já que a parte que podemos observar é ilimitada.

O outro problema é que só podemos lidar com entidades especificadas finitamente. Na verdade, toda a estrutura da ciência, tal como a conhecemos, cai se considerarmos entidades que não são especificadas finitamente, uma vez que torna-se impossível verificar a consistência das definições, até saber quais são as definições, pois podemos acessar apenas parte delas em um tempo finito.

Possivelmente, existe outra questão fundamental que é algo semelhante ao fato de que o fechamento sob união infinita define qualquer conjunto que você deseja, a menos que você possa restringir de forma adequada o que é permitido em tal união. Mas não tenho certeza se entendi completamente esse problema.

Como eu disse, as máquinas de Turing têm a capacidade de lidar com o infinito . Estou contradizendo outras respostas bem votadas de alguns usuários de alta reputação, que devem saber o que falam sobre um tópico tão elementar.

O problema é que Turing escolheu um modelo de computação muito elementar para atingir seu objetivo teórico. Quanto mais simples, melhor. É para modelos de computação mais avançados / sofisticados praticamente o que a linguagem de máquina é para programação: algo muito obscuro onde você não pode reconhecer nenhum dos conceitos que fazem sentido na programação de alto nível. O fato é que, como a linguagem de máquina, a TM pode imitar muito mais do que pode expressar diretamente.

$23{rd}$ Mas ainda assim seria implementado como um cálculo infinito que é artificialmente parado quando a resposta certa é obtida.

Na verdade, todos os usuários que afirmam que tudo é finito, mas ilimitado em uma TM, são bastante cuidadosos ao acrescentar que consideram as Máquinas de Turing em sua definição padrão . O problema é que a definição padrão é apenas um dispositivo para simplificar a teoria, mas é praticamente irrelevante ao tentar entender as estruturas computacionais.

Na verdade, a única coisa que importa em computação é que tudo deve ser especificado finitamente de uma maneira computável, não que seja finito .

Estamos assumindo que uma máquina de turing deve ser um objeto finito. Mas isso não é verdade. Você pode definir um modelo de máquina de Turing usando uma segunda fita que é somente leitura e contém uma função tabulada para todos os valores inteiros, sem nenhum limite. Isso é infinito. Mas ele não lhe fornece nenhum poder de computação extra, desde que o conteúdo dessa fita seja especificado computavelmente (a computabilidade implica que ela é especificada finitamente). A fita extra poderia muito bem ser substituída por uma máquina TM incorporada na outra e forneceria as respostas, em vez de procurá-las na fita extra. De um nível superior, a diferença não é visível.

Do ponto de vista da realização prática, poderíamos ter uma fact máquina de calcular os fatoriais e tabulá-los na fita extra, enquanto outra TM usaria o fatorial tabulado da fita extra, apenas aguardando na primeira TM sempre que a tabulação ainda estivesse faltando entrada. Mas a segunda máquina supõe que o conteúdo da fita seja infinito. A máquina de tabulação nem precisa trabalhar o tempo todo, mas deve retomar a computação sempre que os dados são solicitados da tabela e não são encontrados lá.

Voltando à questão, a principal diferença entre números inteiros ilimitados e a tabela infinita é apenas que os números inteiros são finitos, ilimitados, mas completamente calculados em tempo finito. A tabela infinita é calculada indefinidamente, finita, mas ainda crescendo o tempo todo até o infinito. Isso não é um problema, mas é uma diferença. Objetos infinitos são acessíveis apenas através de aproximações finitas, ... mas eles são infinitos. Números irracionais computáveis ​​são, nesse sentido, objetos infinitos, pelo menos para sua representação como números binários.

Todos os algoritmos são definidos no contexto de alguma teoria matemática. E uma pesquisa de tabela junto com uma tabela infinita é um algoritmo. Mas é um algoritmo em uma teoria matemática que possui um conjunto infinito de axiomas finitamente definido que especificam extensivamente (e não intensivamente) os valores de uma função que axiomatiza para cada argumento inteiro. (veja minha resposta à sua pergunta anterior ). Então é sempre legítimo fazê-lo, pois você sempre pode adicionar afirmações comprovadamente verdadeiras aos axiomas de uma teoria.

As declarações de Usul, reproduzidas na sua pergunta atual, estão na minha opinião incorretas (embora tudo também seja uma questão de definição). Sua conclusão em sua resposta , que você não reproduziu, é que o uso de uma tabela infinita não pode ser considerado um algoritmo, porque só pode ser implementado por um modelo de computação não uniforme, por uma coleção de máquinas diferentes e, portanto, usos " não têm uma descrição finita que possa ser implementada para resolver o problema" inteiro "para qualquer tamanho de entrada$\pi$

A maneira como essas entidades infinitas são computadas na prática é por meio de uma avaliação preguiçosa , computando qualquer parte necessária a qualquer momento e retomando a computação para alguns dos demais sempre que necessário. Isso é exatamente o que é proposto acima com o factfatorial de computação preguiçosa da máquina a ser armazenado em uma tabela, sempre que mais dados forem necessários da tabela.

De certa forma, isso parece justificar a afirmação (na resposta de DanielV ) de que o espaço de código deve ser finito, pois a avaliação lenta será realmente baseada em algum código finito. Mas a computabilidade é um jogo generalizado de codificação, de modo que, entre outras coisas, distinguir código de dados está sempre nos olhos de quem vê. De fato, muitas linguagens de programação modernas não fazem muita diferença entre a especificação intensional e extensional de valores, e a Denotational Semantics realmente não distingue "2 + 2" de "4". Semântica é realmente o que estamos falando quando fazemos uma pergunta como " O que é X ? ".

Essa visão da finitude do código, também vista como estática, é outra razão pela qual uma tabela infinita (considerada como parte do código) não é vista em pé de igualdade com números inteiros ilimitados usados ​​como dados. Mas essa é outra ilusão que não sobrevive à prática de programação conhecida em metaprogramação , linguagens reflexivas e no uso da evalfunção. Nesses idiomas, o código pode ser estendido sem limites pelo próprio programa em execução, enquanto o computador estiver em execução. De fato, pode-se considerar as Máquinas de Turing que modificam suas próprias regras de transição, aumentando seu número sem limites. Isso é bem parecido com o funcionamento das máquinas Universal Turing.

Ao projetar estruturas teóricas, há sempre uma tensão entre simplicidade e perspicácia ou expressividade. A simplicidade simplifica a análise da estrutura, principalmente quando se trata de provar propriedades específicas ou reduzi-la a outras estruturas. Mas muitas vezes é inconveniente para expressar conceitos de alto nível que devem ser codificados. Não programamos com máquinas de Turing, mas com linguagens de alto nível muito mais expressivas e perspícuas, e ao mesmo tempo podemos apagar algumas barreiras, como a distinção entre código e dados, com base na equivalência semântica. As máquinas de Turing parecem simples, mas podem ir muito além de sua definição elementar.

A resposta curta: não . Máquinas de Turing não assumem nada infinito em nenhum momento.

Essa é uma das razões pelas quais eles são válidos como modelo para computação. Não faz sentido descrever a computação como algo executado por um dispositivo infinito.

No entanto, sua operação pode ser infinita: pode não terminar. Essa é outra razão pela qual eles são válidos como modelo para computação. Os dispositivos que só podem executar operações com garantia de término sempre não podem expressar todos os cálculos possíveis.

Além do mais: a operação requer memória ilimitada : embora a quantidade real de memória em uso seja sempre finita, ela pode aumentar arbitrariamente. Portanto, você não pode fornecer toda a memória que qualquer operação precisará com antecedência. Os dispositivos que podem executar apenas operações garantidas para nunca usar mais do que uma certa quantidade fixa de memória não podem expressar todos os cálculos possíveis.

"pensando fora da caixa" e generalizando essa questão que chega a um certo ponto da abstração das máquinas de Turing, e chegando a um ângulo diferente ainda não respondido: sim, as máquinas de Turing têm alguns aspectos intrínsecos de "assumir infinitos" apenas como o conceito é intrínseco à matemática. TMs são uma abstração de máquinas físicas. os conceitos físicos de tempo e espaço são usados ​​propositalmente na teoria da MT, mas como abstrações, porém também com aspectos de suas contrapartes reais.

em resumo, a MT pode funcionar para sempre na teoria , também conhecida como problema de parada . a fita é infinita, mas apenas uma quantidade finita dela pode ser gravada em um determinado momento. uma MT que corre para sempre basicamente pressupõe que o tempo e o espaço são ilimitados, ou seja, "infinito". de fato, existe uma hierarquia de tempo e espaço / "continuum" correspondente que é infinita.

mas nenhuma realização física desse conceito abstrato é possível assumindo que o universo físico esteja limitado (espaço, tempo, matéria, o último dos quais é algo análogo a "símbolos" ou "tinta" na máquina de Turing). de maneira semelhante / analogamente, na física, às vezes, o universo é considerado ilimitado / infinito, mas apenas como uma abstração. Para inverter isso, é também por isso que a "modelagem" de um computador moderno como uma máquina de Turing é em si uma abstração, porque o computador pode ter apenas memória finita etc.

outra comparação útil é a linha numérica em matemática. a linha numérica é infinita, mas indica números finitos. todo número na linha numérica representa uma quantidade finita, mas existe um número infinito dessas quantidades finitas. a fita da máquina de Turing tem uma forte semelhança com o conceito de linha numérica da matemática. Turing poderia facilmente defini-lo como infinito em apenas uma direção, mas definiu-o como infinito em ambas as direções, bem como a linha numérica da matemática, com posições negativas "deixadas" na fita e posições positivas "certas".