Computadores reais têm apenas um número finito de estados; então, qual é a relevância das máquinas de Turing para computadores reais?

42

Computadores reais têm memória limitada e apenas um número finito de estados. Portanto, eles são essencialmente autômatos finitos. Por que os cientistas teóricos da computação usam as máquinas de Turing (e outros modelos equivalentes) para estudar computadores? Qual é o sentido de estudar esses modelos muito mais fortes em relação aos computadores reais? Por que o modelo de autômatos finitos não é suficiente?

Rahul
fonte
7
@Kaveh As pessoas geralmente acenam com a mão que sim, os computadores usados ​​na prática são FSMs, mas os FSMs são muito grandes e as propriedades estruturais interessantes são perdidas na exibição do FSM. Eu nunca vi uma explicação não-ondulada. Portanto, a questão está no tópico aqui.
Martin Berger
15
A verdadeira questão é: por que estudar máquinas de Turing, quando usamos o modelo de RAM quando analisamos algoritmos?
Yuval Filmus
39
Porque às vezes é uma aproximação melhor para que . 10000000000000000000000000000000 1000000000000000000000000000000000001000000000000000000000000000000010000000000000000000000000000000
21316 Andrej Bauer
30
Lembre-se, o problema não resolvido mais famoso da ciência da computação teórica hoje é: pode um tipo de computador imaginário fisicamente impossível resolver problemas tão rapidamente quanto um computador imaginário fisicamente impossível ? Não confunda ciência da computação teórica com engenharia de computação prática; os detalhes do mundo físico não são particularmente relevantes.
Eric Lippert
23
Os materiais reais são feitos de átomos e são de natureza discreta; então, por que estudar integrais?
Peter Shor

Respostas:

32

Há duas abordagens ao considerar esta questão: histórica que diz respeito à forma como os conceitos foram descobertos e técnicos, o que explica por que certos conceitos foram adotados e outros abandonados ou mesmo esquecidos.

Historicamente, a Máquina de Turing é talvez o modelo mais intuitivo de vários desenvolvidos tentando responder ao problema de Entscheidung . Isso está intimamente relacionado ao grande esforço das primeiras décadas do século XX em axiomatizar completamente a matemática. A esperança era que, depois de provar que um pequeno conjunto de axiomas estava correto (o que exigiria um esforço substancial), você poderia usar um método sistemático para obter uma prova da afirmação lógica em que estava interessado. Mesmo que alguém considere autômatos finitos nesse contexto, eles seriam rapidamente descartados, pois falham em calcular funções simples.

Tecnicamente, a afirmação de que todos os computadores são autômatos finitos é falsa. Um autômato finito possui memória constante que não pode ser alterada, dependendo do tamanho da entrada. Não há nenhuma limitação, em matemática ou na realidade, que impedia o fornecimento de fita adicional, discos rígidos, RAM ou outras formas de memória, uma vez que a memória na máquina estava sendo usada. Acredito que isso costumava ser empregado nos primeiros dias da computação, quando até cálculos simples podiam encher a memória, enquanto agora, para a maioria dos problemas e com a infraestrutura moderna que permite um gerenciamento de memória muito mais eficiente, na maioria das vezes isso não é um problema. .


EDIT: Eu considerei os dois pontos levantados nos comentários, mas optei por não incluí-los em termos de brevidade e tempo que eu tinha disponível para escrever a resposta. Este é o meu raciocínio sobre o motivo pelo qual acredito que esses pontos não diminuem a eficácia das máquinas de Turing na simulação de computadores modernos, especialmente quando comparados aos autômatos finitos:

  • Deixe-me primeiro abordar a questão física de um limite de memória pelo universo. Antes de tudo, não sabemos realmente se o universo é finito ou não. Além disso, o conceito de universo observável, que é por definição finito, também é, por definição, irrelevante para um usuário que pode viajar para qualquer ponto do universo observável para usar a memória. A razão é que o universo observável se refere ao que podemos observar a partir de um ponto específico, a Terra, e seria diferente se o observador pudesse viajar para um local diferente no universo. Assim, qualquer argumentação sobre o universo observável se volta para a questão da finitude do universo. Mas vamos supor que, através de alguma inovação, adquirimos conhecimento de que o universo é realmente finito. Embora isso tenha um grande impacto em questões científicas, Duvido que isso tenha algum impacto no uso de computadores. Simplificando, pode ser que, em princípio, os computadores sejam realmente autômatos finitos e não máquinas de Turing. Mas, para a grande maioria dos cálculos e com toda a probabilidade todos os cálculos em que os humanos estão interessados, as máquinas de Turing e a teoria associada nos oferecem uma melhor compreensão. Em um exemplo grosseiro, embora saibamos que a física newtoniana está essencialmente errada, duvido que os engenheiros mecânicos usem principalmente a física quântica para projetar carros ou máquinas industriais; os casos de canto onde isso é necessário podem ser tratados em um nível individual. Mas, para a grande maioria dos cálculos e com toda a probabilidade todos os cálculos em que os humanos estão interessados, as máquinas de Turing e a teoria associada nos oferecem uma melhor compreensão. Em um exemplo grosseiro, embora saibamos que a física newtoniana está essencialmente errada, duvido que os engenheiros mecânicos usem principalmente a física quântica para projetar carros ou máquinas industriais; os casos de canto onde isso é necessário podem ser tratados em um nível individual. Mas, para a grande maioria dos cálculos e com toda a probabilidade todos os cálculos em que os humanos estão interessados, as máquinas de Turing e a teoria associada nos oferecem uma melhor compreensão. Em um exemplo grosseiro, embora saibamos que a física newtoniana está essencialmente errada, duvido que os engenheiros mecânicos usem principalmente a física quântica para projetar carros ou máquinas industriais; os casos de canto onde isso é necessário podem ser tratados em um nível individual.

  • Quaisquer restrições técnicas, como barramentos e endereços, são simplesmente limitações técnicas do hardware existente e podem ser superadas fisicamente. O motivo para isso não ser verdade para os computadores atuais é porque o endereçamento de 64 bits nos permitiu mover o limite superior do espaço de endereço para alturas que poucos aplicativos podem alcançar. Além disso, a implementação de um sistema de endereçamento "extensível" poderia ter um impacto na grande maioria dos cálculos que não precisam dele e, portanto, é ineficiente. Nada impede você de organizar um sistema hierárquico de endereçamento, por exemplo, para dois níveis, o primeiro endereço pode se referir a qualquer um dos bancos de memória e, em seguida, cada banco possui 2 64264264endereços diferentes. Essencialmente, a rede é uma ótima maneira de fazer isso, toda máquina cuida apenas da memória local, mas pode calcular em conjunto.

chazisop
fonte
4
A segunda parte desta resposta está errada. Os computadores são autômatos de estado finito, mesmo que você tenha comprado toda a RAM e outro hardware possível. A quantidade de RAM que você pode conectar a um computador é limitada pela largura do barramento de endereços e o mesmo vale para discos e outros periféricos.
Emil Jeřábek apoia Monica
12
@ EmilJeřábek não é verdade. As interfaces seriais não têm um barramento de endereços e a quantidade de dados que posso acessar na Internet não é limitada por nenhuma propriedade do meu computador.
parar de prejudicar Monica
5
@OrangeDog mas o universo ainda iria colocar um limite para a quantidade de dados podem ser armazenados no observável universo
aberração catraca
9
@ratchetfreak como a máquina de Turing demonstra, você só precisa de acesso local - o "fim" actual da necessidade de fita não estar dentro do universo observável;)
parar de prejudicar Monica
6
Ao mencionar a história, vale a pena citar a revisão da Igreja sobre o artigo de Turing, que as máquinas de Turing têm "a vantagem de tornar a identificação com eficácia ... evidente imediatamente". Ou seja, para as pessoas que tentam se convencer de que haviam realmente capturado tudo o que podia ser calculado, a definição de Turing era convincente.
Jim Hefferon
44

Para completar as outras respostas: Eu acho que a Turing Machine é uma melhor abstração do que os computadores fazem do que os autômatos finitos. De fato, a principal diferença entre os dois modelos é que, com autômatos finitos, esperamos tratar dados maiores que o espaço de estado, e a Turing Machine é um modelo para o contrário (espaço de estado >> dados), fazendo o estado espaço infinito. Esse infinito pode ser percebido como uma abstração de "muito grande na frente do tamanho dos dados". Ao escrever um programa de computador, você tenta economizar espaço para obter eficiência, mas geralmente assume que não será limitado pela quantidade total de espaço no computador. Essa é parte da razão pela qual as Máquinas de Turing são uma abstração melhor dos computadores do que os autômatos finitos.

Denis
fonte
14
Esta é IMHO a resposta certa. As razões são puramente pragmáticas: as máquinas de Turing se saem melhor do que os autômatos finitos ao explicar o que os computadores fazem nas escalas envolvidas.
Emil Jeřábek apoia Monica
3
Eu concordo com isso, exceto a frase "você geralmente assume que não será limitado pela quantidade total de espaço no computador". Pelo contrário, quase qualquer programa não trivial é limitado pelo espaço disponível e os programadores fazem um grande esforço para lidar com isso (por exemplo, coleta de lixo para reutilização automática da memória), mas (1) não há nada que possamos fazer sobre isso e (2) nos restringimos a insumos suficientemente pequenos. É digno de nota que as TMs nos dão uma noção natural do tamanho do problema e que os algoritmos tendem a ser fechados para baixo por essa noção natural de tamanho do problema.
22816 Martin Berger
2
@MartinBerger Re "quase todo programa não trivial é limitado pelo espaço disponível e os programadores se esforçam bastante para lidar com isso (por exemplo, coleta de lixo para reutilização automática de memória)": eu diria que os programas escritos para sistemas com coleta de lixo consideram esse sistema, incluindo o gc , como a máquina contra a qual eles programam. O coletor de lixo não faz parte do programa; faz parte de um esforço para fornecer exatamente o que Denis disse: Uma máquina para programar contra a qual possui recursos de memória praticamente ilimitados.
Peter - Restabelece Monica
2
@ PeterA.Schneider Eu meio que não concordo. A razão de usar o GC fornecido pelo tempo de execução da linguagem é uma das economias do desenvolvimento de software: o mecanismo de gerenciamento de memória específico do programa é mais eficiente que o GC e a maioria dos programadores preferiria se pudesse executá-lo com segurança e baixo custo. Mas eles não podem, portanto, joguem pelo seguro e usem o GC ambiente cujo custo é amortizado por um grande número de programas. Nesse sentido, o uso do GC é muito útil para lidar com a memória de finitude.
Martin Berger
2
Máquinas de Turing não são abstrações do que computadores fazem, são abstrações do que a computação faz, e os computadores foram construídos depois disso. Os computadores fazem a maioria de seus cálculos usando uma quantidade fixa de memória de trabalho interna, mas a Turing Machines não foi inventada para raciocinar sobre computação com uma quantidade limitada de memória de trabalho.
reinierpost
10

Andrej Bauer deu uma razão importante nos comentários:

1000000000000000000000000000000010000000000000000000000000000000

Deixe-me completar as outras respostas com alguns pontos, que provavelmente eram óbvios demais para mencionar:

  • Se o seu objetivo é estudar computadores reais, os autômatos finitos e as máquinas de Turing geralmente serão modelos muito simples para as questões relevantes. Os computadores reais têm vários núcleos de processamento com uma hierarquia de cache (ou algum outro esquema de gerenciamento inteligente), acesso a uma quantidade razoável de memória rápida, acesso a uma quantidade enorme de memória externa lenta (discos rígidos) e podem se comunicar com outros computadores velocidade aproximadamente comparável à velocidade de acesso à lenta memória externa.
  • Se agora você se pergunta por que precisa de todos esses detalhes, seu objetivo real é o estudo de instâncias de problemas e a eficiência com que você pode resolvê-las. Se você está falando de computadores reais, isso também pode significar que você executa experimentos com instâncias de problemas reais em diferentes tipos de arquiteturas de computadores (reais).
  • O modelo de computadores reais descrito acima ainda é idealizado, porque ignora os vários modos de falha dos computadores reais. Como a falha no desligamento pode ser mais frequente que a falha no disco rígido (e os discos rígidos podem ter backups de qualquer maneira), certos domínios com problemas, como operação confiável do banco de dados, podem precisar levar isso em consideração.
  • Π10
Thomas Klimpel
fonte
8

Um formalismo é útil ou não, com base no que as pessoas querem usar o formalismo para modelar e entender.

A máquina de Turing é um formalismo útil para entender programas . Vale a pena entender os programas; a maior parte da computação real é realizada por programas, e não por máquinas para fins especiais. O formalismo da máquina de Turing nos permite modelar importantes preocupações do mundo real, como complexidade do tempo e do espaço. É muito menos natural tentar estudar essas noções usando autômatos de estados finitos.

Máquinas de Turing não são muito úteis ao tentar estudar a complexidade da computação de funções finitas (digamos, funções cujo domínio consiste em entradas de comprimento no máximo 10 milhões). A complexidade do circuito é muito melhor para descrever a complexidade das funções finitas ... mas as máquinas de Turing, por sua vez, têm sido muito úteis para entender a complexidade do circuito.

Autômatos finitos também foram úteis para entender a complexidade do circuito; todos esses modelos têm seu lugar no arsenal matemático.

Rejeito o argumento que diz que os autômatos de estados finitos são um modelo melhor da realidade apenas porque os computadores do mundo real têm apenas um número finito de estados internos. O estudo de autômatos de estado finito lida crucialmente com entradas provenientes de um conjunto infinito de strings, enquanto computadores do mundo real lidam com entradas de apenas um comprimento máximo fixo (a menos que você acredite que vivemos em um universo infinito, seja em termos de espaço ou hora).

Um modelo deve ser julgado em termos de sua utilidade na compreensão dos aspectos da realidade com os quais nos preocupamos. Ou (em alternativa) em termos de sua utilidade na compreensão de um universo matemático que as pessoas consideram suficientemente convincente, mesmo que esse universo matemático não tenha manifestação física óbvia.

Máquinas de Turing, máquinas de estado finito e circuitos (e outros modelos além) provaram sua utilidade.

Eric Allender
fonte
6

Computadores reais não são FSAs. Um computador real é um computador universal, no sentido de que podemos descrever um computador para um computador emular e o computador o emulará. Para muitos exemplos, procure "máquina virtual".

É possível construir uma Universal Turing Machine - uma TM que recebe uma descrição de outra TM e emula a operação dessa TM em uma entrada fornecida.

n22n

Para um ponto de partida na literatura, posso recomendar " Sobre a existência de autômatos finitos ou pushdown universais ", que estuda a inexistência de autômatos universais. Você também pode olhar para as referências (e assim por diante).

Eric Towers
fonte
3
Essa é uma abordagem útil para captar intuitivamente diferentes níveis de "poder computacional". No entanto, o OP parece pensar que computadores reais são FSMs porque o número de estados é limitado, por exemplo, devido à RAM finita. Pelo seu argumento, isso significa que computadores reais são mais parecidos com FSMs do que Turing Machines, porque não posso dobrar livremente o número de estados em uma máquina simulada; Não tenho uma fita infinita como armazenamento.
amon
11
As máquinas de Turing também não precisam ter uma fita infinita. Os computadores podem usar uma quantidade arbitrariamente grande de armazenamento externo em seus cálculos (e isso se torna particularmente fácil com os provedores de nuvem que temos hoje); portanto, eles são fundamentalmente como Turing Machines e não FSMs.
reinierpost
11
Se assumirmos que um computador possui uma quantidade fixa de memória, ele ficará sem memória ao simular um computador com mais memória; portanto, com essa suposição, não é realmente universal.
Kaveh
3

O que torna a máquina de Turing especial é que, embora seja muito, muito simples, ela pode executar todos os (classes de) algoritmos em que podemos pensar. Não existe uma máquina conhecida que seja mais poderosa (pois pode executar algoritmos dos quais a máquina de Turing não é capaz).

Sendo mecanicamente simples, é fácil mostrar se, ou em que grau, outras máquinas são equivalentes a uma máquina de Turing. Isso, por sua vez, torna relativamente fácil mostrar se um determinado computador (ou linguagem de computador) é verdadeiramente universal (c / f "Turing-complete").

AnoE
fonte
A questão é sobre a relação do modelo da máquina de Turing com computadores reais. Se assumirmos que um computador possui uma quantidade fixa de memória, não é realmente universal.
Kaveh
1

Por que o modelo de autômatos finitos não é suficiente?

Enquanto outras respostas já mencionam muitos aspectos relevantes, acredito que a grande vantagem das máquinas de Turing sobre os autômatos finitos é a separação de dados e programa . Isso permite que você analise um programa bastante finito e faça declarações sobre como esse programa lidaria com entradas diferentes, sem restringir o tamanho da entrada.

Embora seja teoricamente possível descrever um computador real e algo como uma máquina de Turing com fita finita como uma máquina de estados, isso não é realmente viável: o número de estados é exponencial na quantidade de memória que sua máquina possui e o valor finito geral o formalismo do autômato de estado exige que você liste explicitamente as transições entre esses estados. Portanto, para um autômato de estado finito geral desse tamanho, é inviável fazer deduções com base em uma enumeração completa de todas as transições de estado.

Obviamente, em um computador real, as transições de estados não podem acontecer arbitrariamente. Não há comando para trocar um terço dos bits na memória em uma única etapa da computação. Assim, você pode tentar criar uma especificação mais compacta para as transições de estado. Algo como a especificação do conjunto de instruções da sua arquitetura. Obviamente, arquiteturas de computador reais são complicadas por causa do desempenho, então você pode simplificar ainda mais isso, para um conjunto de instruções muito simples, que apenas executa etapas muito pequenas usando entradas e saídas muito limitadas. No final, você pode achar que sua arquitetura se assemelha a algo como um intérprete de máquina de Turing: usando alguns bits de código de programa e um pouco de entrada, gere um pouco de saída e mova-se no código do programa.

Uma alternativa seria usar os estados de um autômato de estado finito apenas para representar os dados que estão sendo processados ​​pelo programa, enquanto codifica o próprio programa nas transições de estado. Isso implicaria o mesmo problema de como enumerar todos os estados, e uma representação compacta pode estar novamente próxima do que uma máquina de Turing faz.

Qual é o sentido de estudar esses modelos muito mais fortes em relação aos computadores reais?

No geral, eu diria que uma máquina de Turing com fita finita provavelmente seria um modelo melhor para computadores reais. Mas, para muitas questões científicas, a distinção entre uma fita finita, porém grande e uma fita infinita é irrelevante; portanto, apenas reivindicar uma fita infinita facilita as coisas. Para outras perguntas, a quantidade de fita usada é o cerne da questão, mas o modelo permite que você fale facilmente sobre a quantidade de uso de fita sem o incômodo de especificar o que acontece se a computação ficar sem fita.

MvG
fonte
1

A maioria dos problemas requer máquinas de Turing de tamanho finito

Embora suponha que a fita não acoplada seja uma simplificação útil, a maioria dos problemas / algoritmos exige, de fato, uma quantidade finita de fita, e os limites da memória necessária (possivelmente dependendo do tamanho da entrada) podem ser analisados ​​e frequentemente comprovados.

Isso também costuma generalizar para outros tipos de computadores (para os quais a análise ou prova vinculada pode ser muito mais confusa do que em uma máquina de Turing) e permite estimar a quantidade de armazenamento temporário necessário para um problema específico - isso pode ser feito em uma quantidade fixa do espaço? Proporcional à entrada? Requer quantidades exponenciais de espaço à medida que os insumos crescem?

Peter é
fonte
1

Uma característica importante das máquinas de turing que os autômatos finitos não compartilham é que elas podem escalar a quantidade de memória necessária para resolver o problema com o tamanho do problema .

nn2

O ponto: muitos problemas têm soluções naturais que usam mais memória, quanto maior o problema. Portanto, é natural descrever essas soluções com representações que podem usar memória infinita - não porque uma instância utilize quantidades infinitas, mas porque existe uma instância que usa cada quantidade. Você pode fazer isso com máquinas de turing, mas também com sequências de autômatos finitos.

josinalvo
fonte
Em uma nota relacionada, se uma máquina de Turing com N estados for iniciada com uma fita que tenha um número finito de caracteres em branco C antes e após a posição inicial, haverá algum número T (N, C), como qualquer máquina que terminará em algum momento pode ser emulado por uma máquina cuja máquina foi limitada a caracteres T (N, C).
Supercat
-2

Computadores reais têm memória limitada e apenas um número finito de estados. Portanto, eles são essencialmente autômatos finitos.

Máquinas de Turing são derivadas de autômatos finitos. As máquinas de Turing são praticamente da arquitetura de von Nuemann.

Jesse Enjaian
fonte