Pode uma linguagem ser turing completa, mas incompleta de outras maneiras?

https://stackoverflow.com/questions/813657

03-07-2019
|

Pergunta

Por exemplo, existem certas coisas ao escrever um sistema operacional que não pode ser realizado em uma linguagem Turing completa?

Solução

No. ou pelo menos se você encontrou um que seria uma refutação do Igreja Turing Tese .

No entanto, existem línguas que são Turing completo, mas em que é uma dor completa no saco para escrever alguns programas, ou seja, processamento de strings em Fortran, programação numérica em COBOL, inteiro aritmética em sed, praticamente tudo em assembler x86 .

E depois, claro, há brainfuck .

Outras dicas

Sim, você pode ter uma linguagem que não permitem que você manipular o hardware diretamente. Seria difícil escrever um sistema operacional usando o shell Bourne, por exemplo. Mas estas limitações são menos do que você pensa. sistemas operacionais ter sido escrito em ML padrão, Scheme, e até mesmo Haskell !

Turing completo é a definição mais geral formal da completude. Existem recursos de linguagem que são necessárias para determinadas aplicações, mas estes não se encaixam nas definições formais.

Por exemplo, recursos gráficos, capacidade de desova processos em segundo plano, a capacidade de persistir o estado e capacidade de se conectar à rede são todos recursos úteis, mas não se relacionam com Turing-completude de uma língua. Então Python no Google App Engine ou um Applet Java que funciona em uma caixa de areia ainda é Turing completo.

Você vai notar que, em muitos casos, esses tipos de recursos são fornecidos por bibliotecas, ao invés da linguagem básica.

Se você está falando da pragmática, então certamente ... você pode imaginar uma linguagem de programação sem capacidade de ler ou arquivos de gravação (por exemplo, uma linguagem que pode computar qualquer função em números inteiros, mas é isso) ... Só porque um idioma não pode operar a minha torradeira não significa que ele não é Turing completo, mas isso não significa que há coisas que não pode fazer , então eu não sei como 'importante' ou útil esta distinção é .

Dependendo do contexto, "realizando algo em uma língua" significa coisas diferentes para pessoas diferentes. Turing é uma dessas pessoas, e ele definiu muito exatamente o que ele quer dizer com "completo".

Se uma língua (ou uma máquina teórica) é Turing completa, não há Turing cálculos não pode fazer. Isto não implica que a linguagem é onipotente, assim que é bom em somas. Há muitas "coisas" que não são Turing cálculos, e que, portanto, um computador Turing-completo pode não ser capaz de fazer.

"Seja um sistema operacional" não é uma computação Turing. Para ser um sistema operacional, você precisa fazer mais coisas do que apenas cálculos. Você também precisa manipular hardware.

Dada uma linguagem Turing completa, juntamente com um conjunto de operações para fazer toda a manipulação do hardware que você precisa, incluindo um conceito adequado de entrada e de tempo, você pode escrever um sistema operacional. Ou devo dizer, é possível escrever um sistema operacional. Se você, pessoalmente, pode fazê-lo depende de quão fácil a linguagem é trabalhar com, e sobre as limitações físicas que os ignora definição Turing, como se o programa resultante seria realmente se encaixam e executar na memória do dispositivo que você quer que ele funcione, e executar em um tempo realista.

Ignorando limitações práticas embora - sim, você pode escrever um sistema operacional em qualquer linguagem Turing completa, desde que a língua também tem operações suficiente para conduzir o hardware. "Biblioteca chama", se você deseja tomar a abordagem prática CS de distinguir a linguagem de bibliotecas. Turing não fez tal distinção, porque o seu modelo de computação não tem o conceito de uma "chamada" de qualquer maneira. Você também precisa resolver o problema de inicialização - quer pelo seu hardware deve executar diretamente o idioma que você está escrevendo em, ou então você precisa de um compilador para uma linguagem que o hardware for executado, ou então você precisa de um intérprete escrito em uma língua que o funcionamentos de hardware. Mais uma vez, Turing ignora tudo isso porque o seu modelo computacional utiliza hardware abstrato, enquanto que escrever um sistema operacional é tudo sobre o hardware.

Em Inglês (em vez de CompSciSpeak) é comum dizer que uma língua "carece de alguns recursos", e sem dúvida que é, portanto, "não está completa" por comparação com outra língua que eles tem. Alguém poderia contra-argumentar que é possível implementar fechamentos em C. Pode-se, por exemplo, escrever um programa C que é um intérprete de Lisp, e incorporá-lo em um programa Lisp como uma string. Voila, fechamentos em C. No entanto, isso não é o que a maioria das pessoas estão pedindo se eles dizem, "Eu desejo C teve fechamentos". Se você acha que todas as línguas precisa de encerramentos, então C é incompleta. Se você acha que todas as necessidades de linguagem estruturada de programação, então ARM assembler é incompleta. Se você acha que deve ser possível adicionar dinamicamente métodos para um objeto, em seguida, C ++ é incompleta, mesmo que seja perfeitamente possível escrever uma classe C ++ com "addMethod" e métodos "CallMethodByName" e falso até sua própria convenção método chamando de lá. E assim por diante.

Turing não pensa línguas precisa de nenhum desses conveniências: eles não afetam o que os cálculos podem ser realizados, o quão fácil é escrever alguns programas. O conceito de Turing completude não tem nada a dizer sobre o que os programas parecem, ou como eles estão organizados, única o que eles saída. Então, essas línguas são Turing completo, mas do ponto de vista do programador, há certas coisas que não podem ser realizadas nesses idiomas.

A linguagem pode ou não pode fazer coisas como - sub-rotinas, recursão, tipos de dados personalizados, laços, a definição de classes, Goto, etc. Conjunto de tais recursos de linguagem torna completa ou não. Por exemplo linguagem é incompleta se você não tem loops, gotos e sub-rotinas - você não pode executar qualquer operação cíclica. completude linguagem é muito teórica e uma coisa científica. Como, por exemplo, está provado que, mesmo se o seu idioma não permite chamar funções de forma recursiva, mas permite ponteiros de função -. Você pode simular a recursividade, ou seja, com y-combinator

Coisas como trabalhar com arquivos e hardware muitas vezes não é uma parte da linguagem. Para realizar qualquer tarefa de programação que você precisa mais do que linguagem. Você precisa de ambiente seu programa funciona. Em x86 como idioma você tem instrução "int" com parâmetro único, mas cabe ao sistema operacional para executar determinadas operações quando você executar "21h int".

Idioma só precisa de alguma forma de se comunicar com o ambiente e ser completo - então cabe a ambiente para trabalhar com ele. É válido para escrever em ASM x86 "mov ax, bx", mas cabe à sua CPU para executar esta operação.

Ser incompleto de alguma outra forma - fácil, basta definir a sua própria versão de completude. ou seja, eu odeio trabalho sem OOP baseado em classes, então vamos definir que a linguagem não é Feldman-completo se ele não tem recursos de linguagem apoio OOP baseado em classes. Ok seguida, C e Javascript não é F-completo. Você ainda pode fazer nada nessas línguas, e OOP baseado em classe até mesmo simular a algum nível.

No que diz respeito OS - você ainda precisa de processador que executa instruções e compilador que traduz língua para instruções da CPU. Eu posso imaginar compilador traduzir qualquer coisa para códigos de máquinas. Como, a seguir é o código JS válida

for(var i=0;i<10;i++){
 mov("ax",i);
 int(0x21);
}

e ele não deve ser tão difícil de compilá-lo em código de máquina.

No mundo moderno você escolher não só idioma, você também escolher a plataforma, bibliotecas padrão e não padrão, literatura, comunidade, apoio, etc. Todas essas coisas afetam sua capacidade de fazer determinada coisa, e eles tomaram completamente pode ser ou pode não ser "bastante completa" para a sua tarefa. Mas se eu não posso compilação de código C ++ para Java applet, isso não significa que ele é um c ++ incompletude idioma. É apenas ausência de compilador que irá transformar o código C ++ para algo que pode ser carregado por JVM.

Se você quiser, você pode projetar uma linguagem com recursos de linguagem como "OpenFile, PingNetworkHost, DownloadMpeg4FileOverHttpsAndPlayBackwards". Mas se a linguagem não tê-los, eles ainda podem ser implementadas com outros recursos de linguagem e suporte ambiente, portanto ausência de tais características não faz linguagem incompleta. Se sua língua é como C, mas sem Goto operador, operador de loop (para, ao mesmo tempo, fazer enquanto) e funções, então você não pode escrever programa cíclica e nenhum ambiente e bibliotecas pode ajudá-lo.

A resposta é um sim mais definidas. Turing completude implica apenas que uma linguagem Turing completa pode ser usado para computar qualquer função computável. Por um lado, ele não diz nada sobre a complexidade de um cálculo.

Você geralmente pode esperar que qualquer algoritmo de tempo polinomial pode ser expressa como um algoritmo de tempo polinomial em qualquer outra Turing linguagem completa, mas que é sobre ele. Especialmente quaisquer requisitos de tempo real (macios ou duros) ir para fora da janela, se o seu único foco é Turing completude.

Outra coisa importante é a expressividade de uma linguagem, que é em grande parte uma propriedade subjetiva, mas pode-se apreciar que os programas são muito mais difíceis de escrever em qualquer código de máquina do que, digamos, Java.

Como para os sistemas operativos, uma interface para o hardware é uma obrigação, mas qualquer linguagem pode ser equipado com esses utilitários.

[Edit] Outra coisa que eu poderia acrescentar é que nenhuma implementação efectiva de qualquer linguagem de programação é Turing completa pela natureza de nossas máquinas de computação finitos. Embora a tese de Church-Turing, juntamente com descobertas seminais relacionadas (como o problema da parada), estabelecer uma base para a nossa compreensão da computação, eles raramente se encontram no mundo da computação prática.

usabilidade incompleta:)

Quando a conversa é sobre línguas, é geralmente assumido que as línguas correr em algumas máquinas muito simples. Como tal, qualquer conceito de leitura de um arquivo ou acessar a rede normalmente não é considerado no que diz respeito ao poder de uma linguagem.

Há diferentes classes de linguagens que são frequentemente utilizados em teoria da computabilidade (cada um com quase infinitas modificações)

autômato finito. Esta é a classe mais simples de máquinas e eles podem reconhecer a menor classe de linguagens, que passa a ser o exata línguas que as expressões regulares pode reconhecer, ou seja. se uma seqüência começa com dois 'A e final com d. Eles não podem ser usados ??para reconhecer se uma seqüência contém um conjunto equilibrado de parênteses, fx.

Empurre autômato. Esta é essencialmente uma extensão da finitos Autômatos com uma pilha. Ao contrário das máquinas de estados finitos, que pode ser usado para dizer se uma determinada seqüência contém um conjunto equilibrado de parênteses. Os idiomas que empurrar para baixo autômatos pode reconhecer é exatamente do conjunto do que pode ser descrito usando gramática livre de contexto e são muitas vezes utilizados para o código-fonte de análise.

Máquinas de Turing. Estes são os mais poderosos da classe de máquinas aqui, mas isso não significa que eles podem ser usados ??para responder a todas as perguntas. Eles são incapazes de responder à pergunta se esta cadeia descrever uma máquina de Turing que será executado para sempre? Na verdade, qualquer uma máquina de Turing não pode dizer nada sobre as propriedades não-triviais de qualquer máquina de Turing (Rice Teorema).

Assim sim uma máquina de Turing tem limitações, e há classes de máquinas que podem fazer algo uma máquina de Turing não pode, mas eles têm (todos com toda a probabilidade) só já existia em teoria, mais recente na prática.

Eu não acho definições de completude que não Turing (ou expressões regulares, ou autômatos push-down) são relevantes para idiomas . Mas essa completude é apenas com relação às instalações de computação numéricos ou simbólicos.

As coisas que você está mencionando me parece ser mais uma função do tempo de execução e meio ambiente do que a língua. Há uma distinção importante, e noções formais de completude normalmente se aplicam apenas aos idiomas si mesmos.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow