Diferença entre uma máquina de turing e uma máquina de estado finito?

27

Estou fazendo uma apresentação sobre as máquinas de Turing e queria dar uma base sobre os FSMs antes de apresentar as máquinas de Turing. O problema é que eu realmente não sei o que é MUITO diferente um do outro.

Aqui está o que eu sei que é diferente:

O FSM possui estados seqüenciais, dependendo da condição correspondente atendida, enquanto as máquinas de Turing operam em uma "fita" infinita com um cabeçote que lê e grava.

Há mais espaço para erro nos FSMs, pois podemos cair facilmente em um estado sem fim, enquanto não é tanto para as máquinas de Turing, pois podemos voltar e mudar as coisas.

Mas, além disso, não conheço muito mais diferenças que tornam as máquinas Turing melhores que as FSM.

Você pode por favor me ajudar?

terminology turing-machines finite-automata machine-models Julio Garcia
fonte
2
Não é difícil pesquisar no Google por "FSM vs. Turing Machine"! Essa é a parte divertida de fazer sua própria pesquisa. A principal diferença é que uma máquina de Turing tem "memória" infinita, mas um FSM não.
Dai #
Ok, eu trapacei um pouco lá>.> ;; Peguei vocês! Obrigado!
Julio Garcia
3
o argumento sobre "erro" não está correto. Tente a wikipedia e os livros de cursos. Veja quais são suas diferenças básicas, o objetivo de usar cada uma delas (por exemplo, quando não podemos escolher um FSM em vez de TM?) E sua relação.
Parham
@MahmoudAlimohamadi, o que quero dizer é que há uma chance maior de um fsm pousar em um estado sem fim.
Julio Garcia
@Dai: É mais correto dizer que uma máquina de Turing pode usar uma quantidade arbitrariamente grande de memória. A quantidade usada nunca é infinita.
Reinierpost

Respostas:

24

A principal distinção entre como os DFAs (Deterministic Finite Automaton) e as TMs funcionam é em termos de como eles usam a memória.

Intuitivamente, os DFAs não têm memória "zero"; a configuração de um DFA é totalmente explicada pelo estado em que se encontra atualmente e seu progresso atual na leitura da entrada.

Intuitivamente, as TMs têm uma memória "zero" na forma de fita; a configuração de uma TM consiste em seu estado atual e no conteúdo atual da fita, que a TM pode alterar à medida que é executada.

Um DFA pode ser considerado uma TM que não altera nenhum símbolo da fita nem move a cabeça para a esquerda. Essas restrições tornam impossível o reconhecimento de determinados idiomas que podem ser aceitos pelas TMs.

Observe que eu uso o termo "DFA" em vez de "FSM", pois, tecnicamente, consideraria uma TM uma máquina de estado finito, pois, por definição, as TMs têm um número finito de estados. A diferença entre DFAs e TMs está no número de configurações, que é igual ao número de estados para um DFA, mas é infinitamente grande para uma TM.

Patrick87
fonte
Ah, entendi. Uma pergunta sobre a parte "sem memória": vi um exemplo de máquina de venda automática que somava as moedas dispensadas. Como eles sabem quanto dinheiro existe se não tem memória?
Julio Garcia
@JulioGarcia É difícil dizer sem saber exatamente o que você viu. Existem máquinas Moore e Mealy que podem gerar símbolos nas transições. A atividade de uma máquina de venda automática pode ser melhor modelada por um desses mecanismos. Um DFA de baunilha só aceita e rejeita seqüências de caracteres ... uma máquina de venda automática deve "aceitar" qualquer "sequência" de cunhagem. Dependendo de como você modela os efeitos colaterais extras da alteração, o tipo de memória de trabalho necessária pode ser o acesso aleatório inexistente ou infinito.
Patrick87
Sem ver seu exemplo, não posso ter certeza absoluta, mas tenho duas suposições. Um é que ele não sabe quanto dinheiro existe: apenas assume que há o suficiente. Você não gostaria de construir uma máquina de venda real dessa maneira, mas ainda é um exemplo útil do conceito. A outra possibilidade é que não seja realmente um FSA "puro": ele está conectado a um sensor que pode obter esses dados de "fora" da máquina de alguma forma. A máquina não sabe nem se importa de onde vêm os dados, e não pode armazenar nada no sensor (portanto, não é realmente "memória"), mas ainda pode agir de acordo com o que vê lá.
O Spooniest
16

As máquinas de Turing descrevem uma classe muito maior de idiomas, a classe de idiomas recursivamente enumeráveis. Máquinas de estados finitos descrevem a classe de linguagens regulares.

Máquinas de estados finitos não têm "memória", são limitadas por seus estados.

Uma máquina de estado finito é uma máquina de Turing restrita, na qual o cabeçote só pode executar operações de "leitura" e sempre se move da esquerda para a direita.

Tome este idioma como um exemplo:

L={aibi| i>=0}

Como as máquinas de estados finitos são limitadas no sentido de que não têm memória, um FSM que aceita L não pode ser construído.

Para resumir:

Máquinas de estado finito descrevem uma pequena classe de linguagens em que nenhuma memória é necessária.

Máquinas de Turing são a descrição matemática de um computador e aceitam uma classe de linguagens muito maior do que os FSMs.

As máquinas de Turing têm mais poder computacional que o FSM. Existem tarefas que nenhum FSM pode executar, mas que a Turing Machines pode executar.

mrjasmin
fonte
3

Eu tinha a mesma dúvida e vi dois vídeos muito esclarecedores e uma explicação sobre o Quora da seguinte forma:

Uma máquina de estados finitos é apenas um conjunto de estados e transições. A única memória que possui é em que estado está. Assim, o número de estados de memória é ... finito.

Uma máquina de Turing é uma máquina de estado finito mais uma memória de fita. Cada transição pode ser acompanhada de uma operação na fita (mover, ler, escrever).

Entendi que uma máquina de turing usa / possui uma máquina de estado finito como parte de seu procedimento operacional, além de adicionar alguma memória editável a ela.

Por favor, assista também esses dois vídeos, eles são esclarecedores!

https://youtu.be/gJQTFhkhwPA

https://youtu.be/E3keLeMwfHY

user5193682
fonte
2

Tanto quanto eu entendo as diferenças entre (modelo padrão) Turing e (modelo padrão) Mealy Machines:

  • As Turing Machines leem e escrevem na mesma fita vs. Mealy Machines leem em uma fita de entrada e escrevem em outra fita de saída
  • As máquinas de Turing podem alterar a "direção da fita" (prosseguir para a esquerda ou para a direita [ou parar]) vs. as máquinas Mealy só podem avançar para a direita (é por isso que não há nenhuma direção definida {L, R, H} na função de transição da máquina Mealy [é implicitamente {R}, o que significa que não há escolha]]
  • A Turing Machines pode parar em qualquer célula de fita vs. Mealy Machines lê a entrada completa e, em seguida, deixa de aceitá-la ou rejeitá-la
Michael Klaube
fonte
-3

Uma máquina de Turing pode armazenar, como parte da fita, coisas que deseja lembrar.

Richard Mullins
fonte
5
Não está claro o que você quer dizer com "isso", mas as máquinas de Turing e os FSMs podem fazer isso, então não faz diferença.
David Richerby
@DavidRicherby Mas um FSM pode armazenar apenas uma quantidade predeterminada, enquanto as máquinas de Turing podem armazenar o quanto quiserem. Essa é a diferença fundamental.
Gilles 'SO- stop be evil'
11
@ Gilles concordou, mas não é isso que a resposta diz.
David Richerby