Bons recursos para aprender sobre modelos de computação?

Question

Por curiosidade, eu estou tentando identificar qual modelo de computação de um sistema que eu trabalho com é funcionalmente equivalente a, e provar a equivalência.O mais que eu gasto com esse problema o mais suspeito que o sistema não é Turing-equivalente.O meu entendimento de Máquinas de Turing e recursivamente enumerável línguas é boa, mas eu não sei muito sobre autômatos com menos recursos (por exemplo,pushdown automata), então eu não tenho certeza de como proceder.

Primeiro, alguém pode recomendar um bom recurso para aprender sobre os diferentes modelos de computação?Eu estou interessado em gramáticas, linguagens e autômatos, e como provar a equivalência e diferença entre todos eles.Idealmente, o recurso seria quebrar todos os elementos de cada modelo em grande detalhe e compará-los.

Segundo, há uma abordagem geral ou framework que deve ser utilizado quando se tenta ajustar um sistema para qualquer um desses modelos computacionais?

Answer 1

Eu recomendo um bom livro sobre ciência da computação (No meu Uni curso, eu estou estudando a partir Sipser Introdução à Teoria da Computação, o que é muito bom na minha opinião.Você também pode encontrar um livro-texto livre o que ensina o mesmo, mas eu não tenho nenhuma experiência com uma assim eu não recomendo).

A outra abordagem seria, provavelmente, apenas para ler na Wikipédia.Você pode realmente ter um monte de milhagem fora da Wikipédia com artigos, se você souber o que você está procurando e em que ordem.Além disso, se algo não estiver claro, você geralmente pode pesquisar no Google e encontre mais recursos sobre esse determinado assunto.

É claro que isso vai não ser tão bom como um verdadeiro livro, mas é um bom lugar para começar agora, e é gratuito.

Como um ponto de partida, eu recomendo a leitura sobre os seguintes tópicos (na ordem em que aparecem):

1. Determinista Autômato Finito
2. Não Determinístico Autômato Finito, e a sua equivalência com a DFAs.
3. Regular Idiomas, e a sua equivalência com a DFAs.
4. Pushdown Automata
5. Gramáticas independentes de contexto, e a sua equivalência com a Pushdown Automata.
6. Hierarquia De Chomsky
7. Máquinas De Turing

Que deve fornecer uma breve introdução para a maioria dos modelos computacionais pessoas sobre o que falar. 2:Eu recomendo um bom livro sobre ciência da computação (No meu Uni curso, eu estou estudando a partir Sipser Introdução à Teoria da Computação, o que é muito bom na minha opinião).A outra abordagem seria, provavelmente, apenas para ler na Wikipédia.Você pode realmente ter um monte de milhagem fora da Wikipédia com artigos, se você souber o que você está procurando e em que ordem.Além disso, se algo não estiver claro, você geralmente pode pesquisar no Google e encontre mais recursos sobre esse determinado assunto.Como um ponto de partida, eu recomendo a leitura sobre os seguintes tópicos (na ordem em que aparecem):1. 1: http://www.amazon.com/Introduction-Theory-Computation-Second-Michael/dp/0534950973/ref=sr_1_1?ie=UTF8&s=books&qid=1263282346&sr=8-1

Answer 2

As aulas em vídeo do link a seguir dá uma boa introdução à teoria da computação.Este é um dos melhores recursos sobre este tema.

Vídeo-Aulas de Teoria da Computação pelo Prof.Shai Simonson

Answer 3

Um antigo texto que pode ser difícil de encontrar é Hopcroft e Ullman de "Introdução à Teoria de Autômatos, Linguagens e Computação".Há um número de edições --- eu ouvi que '79 é o melhor, na medida em que ele puxa o menor número de socos na introdução de complexo de coisas.É legítimo, ainda que pequeno livro, e introduz o campo inteiro, não apenas o que você está procurando.Sugiro isso a vã esperança de que talvez um daqueles "mais complicado" provas de outras fontes deixar de fora pode ser a sua chave.

Como uma suave ponto de partida, existem algumas útil "benchmark" de línguas.

• Se o seu modelo pode reconhecer a língua de todas as cadeias onde há o mesmo número de as e Bs em uma seqüência de caracteres e, em seguida, pelo menos, é mais poderoso do que o FSM.
• Se não pode, então ele pode ser equivalente ao FSM.
• Da mesma forma, se o seu modelo pode reconhecer a língua de todas as cadeias onde há o mesmo número de Como, Bs e Cs em uma seqüência de caracteres e, em seguida, é mais poderoso do que uma CFG, ou PDA.

Estes "benchmark " línguas" são realmente apenas funções em disfarçar --- o primeiro é basicamente perguntando se 2 unário números são iguais, o segundo é o caso de se perguntar se 3 unário números são iguais.Eles são bons e simples, e são bem conhecidas para ser acima ou abaixo das capacidades de modelos específicos.Eu não sei mais simples para as mais complexas máquinas, de forma que você pode estar no seu próprio.

Note que para o modelo de "LBA", linearmente limitado autômatos, eu acredito que não é conhecida qualquer linguagem natural que é computável, com um TM, mas NÃO um com o LBA.Esta declaração é elaborado a partir da nebulosa memórias, portanto, não tome isso como uma prova formal.:)

Nota (finalmente) que o "benchmark" as línguas NÃO SÃO o ESTABELECIMENTO de IGUALDADE.Isto é, se o seu modelo não é possível comparar 2 unário números, que não não significa que ele é necessariamente equivalente a uma FSM, poderia ser ainda mais fraco.As línguas de apenas estabelecer o que é maior do que no poder, ou menos do que no poder.

Em um totalmente (completamente) pista diferente, Sipser do livro é fazer provas de equivalência entre regexes e FSM, bem como entre PDAs e CFGs.Eu não tenho certeza o quão útil que vai ser, como você são muito vagas sobre que tipo de modelo de computação que você está pensando, mas se você está morto-definir sobre a equivalência, esses podem ser bons pontos de partida.