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, \Gamma, b, \Sigma, \delta, q_0, F)$ Onde $Q$, $\Gamma$, $b \in \Gamma$, $\Sigma \subseteq \Gamma \smallsetminus \{ b \}$ como entrada, $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{ L, R, N \}$ como função de transição onde $L$ = número de etapas à esquerda, $R$ = número de etapas à direita, $N$ = "espera", $q_0 \in Q$ é o estado inicial e $F \subseteq 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.

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.

É 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.

Uma linguagem de programação é um equivalente cuidadosamente construído de uma Universal Turing Machine.

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+a$ verificador comutativo da lei de adição)

[3] /cs/10379/top-turing-machine-simulators-on-the-web