Perguntas sobre problemas que não podem ser resolvidos por nenhuma máquina de Turing.
Foi-nos dado o seguinte exercício. Deixei f( n ) = { 10 00 0n ocorre na representação decimal de πoutrof(n)={10n occurs in the decimal representation of π0else\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}...
Eu já mencionei que os sistemas do tipo dependente não são inferíveis, mas são verificáveis. Fiquei me perguntando se existe uma explicação simples de por que isso é assim e se existe ou não um limite de "dependência" onde os tipos podem ser indexados por valores, abaixo de qual inferência de tipo...
Resumo: De acordo com o teorema de Rice, tudo é impossível. E, no entanto, faço essas coisas supostamente impossíveis o tempo todo! Obviamente, o teorema de Rice não diz simplesmente "tudo é impossível". Diz algo bastante mais específico: "Todas as propriedades de um programa de computador não...
O teorema de Rice nos diz que as únicas propriedades semânticas das Máquinas de Turing (ou seja, as propriedades da função computada pela máquina) que podemos decidir são as duas propriedades triviais (ou seja, sempre verdade e sempre falsas). Mas existem outras propriedades das máquinas de Turing...
Entendo a prova da indecidibilidade do problema da parada (dada, por exemplo, no livro de Papadimitriou), com base na diagonalização. Embora a prova seja convincente (eu entendo cada etapa dela), não é intuitivo para mim no sentido de que não vejo como alguém a derivaria, partindo apenas do...
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...
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....
A lógica construtivista é um sistema que remove a lei do meio excluído, bem como a dupla negação, como axiomas. É descrito na Wikipedia aqui e aqui . Em particular, o sistema não permite provas por contradição. Eu estou querendo saber, alguém está familiarizado com como isso afeta os resultados em...
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.,...
É sabido que a inferência do tipo Hindley-Milner (o -calculus de digitação simples com polimorfismo) tem uma inferência de tipo decidível: você pode reconstruir os tipos de princípio para qualquer programa sem nenhuma anotação.λλ\lambda A adição de classes de tipo no estilo Haskell parece...
Considere os problemas de decisão declarados em uma linguagem formal "razoável". Digamos fórmulas na aritmética Peano de ordem superior com uma variável livre como quadro de referência, mas estou igualmente interessado em outros modelos de computação: equações diofantinas, problemas de palavras ao...
Deixe . Preciso decidir se F é decidível ou recursivamente enumerável. Eu acho que é decidível, mas não sei como provar.F={⟨M⟩:M is a TM which stops for every input in at most 50 steps}F={⟨M⟩:M é uma TM que para para cada entrada em no máximo 50 etapas}F = \{⟨M⟩:\text{M is a TM which stops for...
O problema da parada não pode ser resolvido no caso geral. É possível criar regras definidas que restringem as entradas permitidas e o problema de parada pode ser resolvido para esse caso especial? Por exemplo, parece provável que uma linguagem que não permita loops, por exemplo, seria muito fácil...
Configuração: expressões regulares com referências anteriores idioma unário (alfabeto de 1 símbolo) O seguinte problema é decidível nessa configuração: Dada uma expressão regular com referências anteriores, ela define um idioma regular? Por exemplo, (aa+)\1define um idioma regular, enquanto...
Quero saber se o seguinte problema é decidível e como descobrir. Todos os problemas que vejo podem dizer "sim" ou "não" a ele; portanto, a maioria dos problemas e algoritmos é decidível, exceto alguns (que são fornecidos aqui )? Entrada: Um gráfico direcionado e finito , com v e u como vértices....
Não existe uma solução analítica geral para o problema do corpo n que possa produzir uma função analítica que possa ser usada para fornecer o estado de um sistema n corpo no tempo arbitrário t com precisão exata. No entanto, existem alguns casos especiais de sistemas com n corpos, pelos quais é...
O problema de dois autômatos de pushdown reconhecerem o mesmo idioma é indecidível. O problema de decidir se um autômato de empilhamento reconhece o idioma vazio é decidível; portanto, também é decidível se ele reconhece um determinado idioma finito. É indecidível se o idioma aceito por um autômato...
Existem propriedades indecidíveis de autômatos limitados lineares (evitando o truque de linguagem de conjunto vazio)? Que tal um autômato finito determinístico? (deixe de lado a intratabilidade). Gostaria de obter um exemplo (se possível) de um problema indecidível definido sem o uso explícito de...
Sabe-se que o idioma das palavras que contêm número igual de 0 e 1 não é regular, enquanto o idioma das palavras que contêm número igual de 001 e 100 é regular ( veja aqui ). Dadas duas palavras w1,w2w1,w2w_1,w_2 , é decidível se o idioma das palavras que contêm o mesmo número de e é...
Eu tenho essas perguntas de um exame antigo que estou tentando resolver. Para cada um dos problemas, a entrada é uma codificação de uma máquina de Turing .MMM Para um número inteiro e os três problemas a seguir:c > 1c>1c>1 É verdade que, para cada entrada , M não passa na posição ao...