Qual é a relação exata entre linguagens de programação e máquinas de Turing?
Eu não sei muito sobre yacc, bison, flex ou lex e, por favor, me corrija se eu estiver errado, mas uma linguagem de programação também é uma máquina de Turing e uma máquina de Turing é definida como a tupla ( Q , Γ , b , Σ , δ,q0 0, F)(Q,Γ,b,Σ,δ,q0,F) Onde QQ, ΓΓ, b ∈ Γb∈Γ, Σ⊆Γ∖{b}Σ⊆Γ∖{b} como entrada, δ:Q×Γ→Q×Γ×{L,R,N}δ:Q×Γ→Q×Γ×{L,R,N} como função de transição onde LL = número de etapas à esquerda, RR = número de etapas à direita, NN = "espera", q0∈Qq0∈Q é o estado inicial e F⊆QF⊆Q é o conjunto de estados finais.
Qual a similaridade entre implementar uma linguagem de programação e implementar uma máquina de Turing? Pode-se dizer que o que é feito quando uma linguagem de programação é implementada é que uma máquina de Turing como a acima é definida? Se sim, por que não podemos simplesmente usar um modelo que se parece com a definição de uma máquina de Turing quando uma linguagem de programação é definida? Em vez disso, algo como o BNF parece ser o padrão.
A relação exata é esta: as máquinas de Turing são uma linguagem de programação específica.
A forma BNF, Backus-Naur pode ser pensada como um sistema de representação CFL . a maioria das linguagens de programação são CFLs. um compilador [em geral] converte o programa de entrada e a especificação CFL em código de objeto. (a linguagem assembly é um exemplo de uma linguagem não-CFL). portanto, pode haver mais de uma pergunta aqui.
@vzn: Eu não sei como o que você diz se relaciona com a pergunta, mas é errado em qualquer caso .
o que está errado? repita, a maioria das linguagens de programação são CFLs (ou possuem um analisador central do tipo CFL) com várias qualificações técnicas.
O que há de errado é que você pensa em linguagens de programação em termos de gramática, quando é melhor pensar nelas como modelos computacionais.
Talvez eu esteja interpretando mal a pergunta, mas parece que há alguma confusão na comparação entre máquinas de Turing e linguagens de programação.
A definição e o método de definição de uma máquina de Turing constituem uma linguagem de programação. Máquinas de Turing representam programas nesse idioma.
A sintaxe e a semântica da linguagem (por exemplo, no BNF) podem constituir uma linguagem de programação, e os artefatos que satisfazem essas restrições sintáticas e semânticas são programas nessa linguagem.
Portanto, não é realmente preciso (IMHO; é claro que podemos pensar sobre o que as TMs fazem de maneiras diferentes e, em algumas dessas maneiras de ver as TMs, você pode pensar nas TMs individuais como definindo linguagens de programação. Na verdade, um Turing universal construído de forma clássica machine define uma linguagem de programação muito clara, isto é, representações de máquinas de Turing como strings) para comparar a implementação de uma linguagem de programação com a implementação de uma máquina de Turing. Implementar uma linguagem de programação envolve definir as regras do jogo, assim como Turing definiu as regras do jogo (ou quem quer que fosse, seja o que for) quando ele definiu o que significava que algo seria uma máquina de Turing.
"Implementar" uma linguagem de programação e definir máquinas de Turing é uma atividade muito difícil. Escrever programas em um idioma e definir máquinas de Turing específicas também é uma atividade difícil. Mas são atividades bem diferentes (exceto nos casos excepcionais em que você está escrevendo uma máquina de Turing para atuar como intérprete; nesse caso, talvez faça sentido falar em projetar uma linguagem de programação escrevendo uma TM ... mas eu ' não tenho certeza de que era isso que você procurava).
O modelo de máquina de Turing é um modelo teórico sobre o que é "computação". Como modelo teórico, ele foi projetado para que seja simples manipular e provar coisas sobre ele, especificamente para explorar o que pode ou não ser computado. Ele também serve como um modelo simples para discutir (e provar coisas) o tempo necessário para fazer um cálculo ou quanto espaço (memória) é necessário. A ênfase está na simplicidade (especialmente no uso apenas de conceitos matemáticos básicos).
Uma linguagem de programação, ao contrário, é projetada para facilitar a escrita (e a leitura!) De seres humanos, geralmente também de forma que os conceitos de sua área de aplicação sejam tratados diretamente. Por exemplo, uma linguagem como Perl lida com operações em strings, mesmo coisas complexas, como procurar por padrões, diretamente. O SQL é adaptado para operar em bancos de dados relacionais, fazendo consultas procurando dados com certas restrições e manipulando o banco de dados. E assim por diante.
A tese de Church-Turing afirma que qualquer coisa que possa ser calculada em qualquer sentido significativo do termo pode ser calculada por uma máquina de Turing. Este é o resultado final de um frenesi de uma década ao criar modelos de computação, os quais resultaram equivalentes. Então, em teoria, sim, eles são equivalentes (na medida em que a definição da linguagem e sua implementação e a máquina na qual ele roda estão corretas). Mas, como diz o ditado, em teoria, teoria e prática são a mesma coisa; na prática, eles são muito diferentes. Escrever uma máquina de Turing para executar até tarefas simples é muito trabalhoso e pode ser apenas uma linha simples na sua linguagem de programação favorita.
Temos que ter em mente que computadores reais fazem coisas não cobertas pelo modelo de TM, por exemplo, E / S.
É verdade que todas as linguagens de programação (de uso geral) são consideradas equivalentes à máquina de Turing. (De acordo com a tese de Church-Turing, eles não calcularão mais, e geralmente fica claro como simular uma MT no seu idioma favorito). Isso não significa que a programação de uma máquina de Turing seja prática. Longe disso. Para fazer uma programação real, linguagens melhores são desenvolvidas. De fato, essas linguagens evoluem com o tempo, quando aprendemos quais recursos tornam as linguagens de programação mais simples de usar ou menos propensas a erros.
Ainda assim, a máquina de Turing está por aí. Serve como uma vareta para definir a complexidade e a computabilidade.
(adicionado.) Como observado nos comentários, nem toda linguagem de programação é projetada para ter o poder de Turing, alguns lidam com tarefas específicas, como expressões regulares. Por outro lado, existem linguagens exóticas poderosas, identificadas de maneira a tornar a programação praticamente impossível. Para se divertir.
@DaveClarke Indeed. Era isso que pretendia afirmar, mas você está certo: eficiência não é complexidade. Eu vou mudar a palavra. obrigado.
"É verdade que todas as linguagens de programação são equivalentes à máquina de Turing, veja a tese de Church-Turing". - equivalência de uma linguagem de programação e TMs podem ser (e é) comprovada (quando verdade, existem línguas menos poderosos!), E é não a tese de Church-Turing.
Além disso, devemos ter em mente que computadores reais fazem coisas não cobertas pelo modelo de TM, por exemplo, E / S.
@Raphael. Tento reformular a parte de Church-Turing. Obrigado. Concordo que uma TM não é um computador real, mas a E / S (leitura e gravação) é uma das coisas que você pode fazer com uma TM.
Boa resposta, mas também acho um pouco forte dizer que todas as linguagens de programação (úteis e não exóticas) são equivalentes às máquinas de Turing. Quero dizer, baunilha SQL (sem complementos sofisticados) e expressões regulares (nem mesmo do tipo teórico) são dois exemplos de "linguagens de programação" úteis que não são equivalentes a Turing, mas são muito úteis.
Uma linguagem de programação é um equivalente cuidadosamente construído de uma Universal Turing Machine.
— ramseysdream111
boa pergunta, mas você está pensando demais nisso. se perdendo nos símbolos. vamos analisar tudo de uma maneira simples e básica. uma linguagem de programação está em ASCII ou diz apenas 0/1 bits para caracteres. Agora imagine que o TM possui 0/1 bits para simplificá-lo ou diga ASCII como caracteres de entrada.
A principal realização e analogia é que a tabela de estados da TM também funciona como leitura do conjunto de caracteres de entrada e contendo a linguagem de programação / codificação do programa.
isso pode ser realizado construindo ou examinando TMs simples e suas tabelas de estados para calcular cálculos básicos, por exemplo, somas ou o que for. outra abordagem muito útil é jogar com simuladores de MT. [3]
tudo isso seria muito mais óbvio se, em algumas aulas, eles ensinassem CS usando compiladores reais de TM que pegariam um programa arbitrário ( código-fonte ) e o compilariam em uma tabela de estado de TM (semelhante ao código de objeto ). infelizmente, ninguém acredita que seja útil no momento. [1] (plz vote para reabrir se você discordar! =)
mas se você jogar com simuladores de TM, isso ajudará você a criar essa intuição básica. [2] é possivelmente o mais sofisticado disponível no mundo atualmente.
[1] /cs/2916/is-there-a-compiler-from-high-level-language-to-turing-machine
[2] Compilador TM em rubi com código-fonte / objeto de exemplo e saída (para um não-asfaltado)a+b=b+aa+b=b+a verificador comutativo da lei de adição)