Eu estava passando pela discussão sobre a questão Como definir máquinas de Turing quânticas? e sinto que a MT quântica e a MT não - determinística são a mesma coisa. As respostas para a outra pergunta não tocam nisso. Esses dois modelos são iguais? Se não, Quais são as diferenças entre quantum...
Encontrei abaixo a declaração de Alan M. Turing aqui : "A visão de que as máquinas não podem causar surpresas se deve, creio eu, a uma falácia à qual filósofos e matemáticos estão particularmente sujeitos. Essa é a suposição de que, assim que um fato é apresentado à mente, todas as conseqüências...
Atualmente, estou lendo um livro sobre algoritmos e complexidade. No momento, estou lendo sobre funções computáveis e não computáveis, e meu livro afirma que há muito mais funções que não são computáveis do que computáveis; na verdade, a maioria é não computável, diz. Em certo sentido, posso...
A tese de Church-Turing afirma que tudo o que pode ser fisicamente calculado, pode ser computado em uma máquina de Turing. O artigo "Computação analógica via redes neurais" (Siegelmannn e Sontag, Theoretical Computer Science , 131: 331–360, 1994; PDF ) afirma que uma rede neural de uma determinada...
Aprendemos sobre o conceito de enumerações de funções. Na prática, eles correspondem a linguagens de programação. Em uma observação de passagem, o professor mencionou que a classe de todas as funções totais (ou seja, as funções que sempre terminam para cada entrada) não é enumerável. Isso...
Todo problema indecidível que eu conheço se enquadra em uma das seguintes categorias: Problemas indecidíveis por causa da diagonalização (auto-referência indireta). Esses problemas, como o problema da parada, são indecidíveis, porque você pode usar um pretenso argumento para a linguagem construir...
Existem programas que podem 'traduzir' o código fonte entre dois idiomas (assumindo que o tradutor tenha acesso às bibliotecas necessárias)? Se houver, como eles funcionam (técnicas utilizadas, conhecimento necessário etc.)? Como eles poderiam ser construídos? Se não estiverem, quais são as...
O combinador de ponto fixo FIX (também conhecido como combinador Y) no cálculo lambda (sem tipo) ( ) é definido como:λλ\lambda FIXF λ f. ( λ x . f ( λ y. x x y ) ) ( λ x . f ( λ y. x x y ) ))≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda...
A Wikipedia e outras fontes que eu encontrei listam o voidtipo de C como um tipo de unidade, em vez de um tipo vazio. Acho isso confuso, pois me parece que voidmelhor se ajusta à definição de um tipo vazio / inferior. Nenhum valor habita void, até onde eu sei. Uma função com um tipo de retorno de...
O problema de parada afirma que não há algoritmo que determine se um determinado programa é interrompido. Como conseqüência, deve haver programas sobre os quais não podemos dizer se eles terminam ou não. Quais são os exemplos mais simples (menores) conhecidos de tais
Note que, embora eu saiba programar, sou bastante iniciante na teoria do CS. De acordo com esta resposta Turing completude é um conceito abstrato de computabilidade. Se um idioma é Turing completo, ele é capaz de fazer qualquer cálculo que qualquer outro idioma completo de Turing possa...
Estou tendo problemas para entender a prova da indecidibilidade do problema da parada. Se retorna se o programa interrompido ou não na entrada b , por que precisamos passar o código de P para ambos a e b ?a b P a bH( a , b )H(a,b)H(a,b)umaaabbbPPPumaaabbb Por que não podemos alimentar H(...
Claramente, não há problemas indecidíveis no NP. No entanto, de acordo com a Wikipedia : NP é o conjunto de todos os problemas de decisão para os quais as instâncias em que a resposta é "sim" têm [..] provas que são verificáveis em tempo polinomial por uma máquina determinística de Turing....
Esta questão foi migrada do Theoretical Computer Science Stack Exchange porque pode ser respondida no Computer Science Stack Exchange. Migrou há 6 anos . Encontrei muitas definições de linguagens recursivas e recursivamente enumeráveis. Mas eu não conseguia entender...
Esta questão foi migrada do Theoretical Computer Science Stack Exchange porque pode ser respondida no Computer Science Stack Exchange. Migrou há 7 anos . Eu só tive essa pergunta interessante. Qual é a função de crescimento mais rápido conhecida pelo homem? É castor...
Na teoria da computabilidade, funções computáveis também são chamadas de funções recursivas. Pelo menos à primeira vista, eles não têm nada em comum com o que você chama de "recursivo" na programação do dia-a-dia (isto é, funções que se denominam). Qual é o significado real de recursivo no...
Esta questão foi migrada do Theoretical Computer Science Stack Exchange porque pode ser respondida no Computer Science Stack Exchange. Migrou há 7 anos . "Alan Turing provou em 1936 que um algoritmo geral para resolver o problema de parada de todos os pares possíveis de...
Existe alguma linguagem "natural" indecidível? por "natural", quero dizer uma linguagem definida diretamente pelas propriedades das strings, e não através de máquinas e seus equivalentes. Em outras palavras, se o idioma se parecer com que é uma TM, DFA (ou exp regular), PDA (ou gramática) etc.,...
Estudei algo sobre a Complexidade Kolmogorov , li alguns artigos e livros de Vitanyi e Li e usei o conceito de Distância de compressão normalizada para verificar a estilometria dos autores (identifique como cada autor escreve alguns textos e agrupa documentos por sua semelhança). Nesse caso, os...
Talvez minha compreensão limitada do assunto esteja incorreta, mas é isso que eu entendo até agora: A programação funcional é baseada no Lambda Calculus, formulado pela Alonzo Church. A programação imperativa é baseada no modelo de máquina de Turing, feito por Alan Turing, aluno da Igreja. O...