Aprendi hoje que a análise de algoritmos difere com base no modelo computacional. É algo em que nunca pensei ou ouvi falar. Um exemplo dado a mim, que o ilustrou ainda mais, pelo usuário @chi foi: Por exemplo, considere a tarefa: dado retorne . Na RAM, isso pode ser resolvido em pois o...
No problema de parada, estamos interessados se existe uma máquina de Turing que pode dizer se uma determinada máquina de Turing pára ou não em uma determinada entrada . Geralmente, a prova começa assumindo que existe umEm seguida, consideramos um caso em que restringimos ao próprio e derivamos...
Estou tentando encontrar as respostas de duas perguntas sobre a máquina Universal Turing. Como a máquina Universal de Turing pode simular uma máquina de Turing se a que está sendo simulada possui um número maior de estados? Como a máquina Universal Turing pode simular uma máquina de Turing se a...
Este é provavelmente um pensamento bobo, mas suponha que temos um computador que está programado para executar uma sequência infinita de cálculos e suponha que o cálculo leva 1 / 2 i segundos para ser concluído. Então este computador pode fazer um número infinito de cálculos em uma quantidade...
No meio do período, houve uma variante da seguinte pergunta: Para um decidível, defina Mostre que não é necessariamente decidível.Pref ( L ) = { x | ∃ y r x y ∈ G } Pref ( L )LLLPref(L)={x∣∃y s.t. xy∈L}Pref(L)={x∣∃y s.t. xy∈L}\text{Pref}(L) = \{ x \mid \exists y \text{ s.t. } xy \in...
Uma máquina de Turing com permissão para ler e escrever símbolos de um alfabeto infinito é mais poderosa que uma TM comum (essa é a única diferença, a máquina ainda possui um número finito de estados)? A intuição não me diz, pois você precisa de um número infinito de estados para diferenciar cada...
Para provar que a 3 cores é decidível, basta dizer: Cada nó no gráfico possui 3 cores possíveis Portanto, podemos enumerar todas as possibilidades de e verificar se não há duas arestas conectando nós da mesma cor3n3n3^n Isso prova que a 3 cores é decidível? Ou preciso construir uma máquina de...
Estou tentando criar uma prova para o seguinte: Para qualquer idioma , existe uma linguagem B tal que A ≤ T B , mas B ≰ T A .AAABBBA≤TBA≤TBA \le_{\mathrm{T}} B≰TA≰TA\nleq_{\mathrm{T}} A Eu estava pensando em deixar ser um T M , mas eu percebo que nem todos os idiomas são Turing redutível a A T...
Por que os números computáveis (no sentido de Turing) são enumeráveis? Deve ser muito óbvio, mas atualmente não estou
Queremos ladrilhar m × mm×mm\times m quadrado usando dois tipos de ladrilhos: 1 × 11 1×1 11 \times 1 quadrado e 2×22×22 \times 2 quadrado, de forma que todos os quadrados subjacentes sejam cobertos sem sobreposição. Vamos definir uma função f(n)f(n)f(n) que fornece o tamanho do maior quadrado...
Lendo esta pergunta " Problemas indecidíveis de ER naturais, mas não completos de Turing ", veio à minha mente o seguinte idioma: Se for a função de castor ocupado (pontuação máxima atingível entre todas as máquinas de Turing de estado n de dois símbolos com parada do tipo descrito acima, quando...
Uma declaração do teorema de Rice é apresentada na página 35 de "Complexidade computacional: uma abordagem moderna" (Arora-Barak): Uma função parcial a partir de { 0 , 1 }∗{0 0,1 1}∗\{0,1\}^* a { 0 , 1 }∗{0 0,1 1}∗\{0,1\}^* é uma função que não está necessariamente definido em todas as suas...
Eu tenho lido alguns artigos formais de teoria da linguagem e me deparei com um termo que não entendo. O documento geralmente se refere a um conjunto "efetivamente fechado sob interseção" ou outras operações. O que "efetivamente" significa aqui? Como isso difere do fechamento normal? Para...
Ocorreu-me uma pergunta sobre o problema da interrupção e não consegui encontrar uma boa resposta on-line, imaginando se alguém poderia ajudar. É possível que o problema da parada seja decidível para qualquer TM em qualquer entrada, desde que a entrada não seja a própria TM?...
Hoje, no almoço, levantei essa questão com meus colegas e, para minha surpresa, o argumento de Jeff E. de que o problema é decidível não os convenceu ( aqui está uma publicação intimamente relacionada ao mathoverflow). Uma declaração de problema que é mais fácil de explicar ("é P = NP?") Também é...
Sou estudante de graduação apenas começando a ler sobre computação reversível. Eu sei que, por causa do princípio de Landauer, cálculos irreversíveis dissipam calor (e reversíveis não). Eu falei com meu professor, que nunca tinha ouvido falar em computação reversível antes, e ele estava tendo...
Recentemente, conversei com um amigo sobre um site que propunha desafios regex, combinando principalmente um grupo de palavras com uma propriedade especial. Ele estava procurando por um regex que corresponda a cadeias de caracteres como ||||||||onde o número de |é primo. Eu imediatamente disse a...
Este é o seguimento de outra pergunta aqui , e espero que não seja muito filosófico. Como Raphael apontou em um comentário na minha pergunta anterior, eu realmente não entendo a definição de "computável", mas de acordo com alguns artigos que li, a definição também não é muito clara quando se trata...
Vamos supor que eu tenho duas funções FFF e GGG e estou interessado em determinar se F(x)=∫G(x)dx.F(x)=∫G(x)dx.F(x) = \int G(x)dx. Vamos supor que minhas funções sejam compostas por funções elementares (polinômios, exponenciais, logs e funções trigonométricas), mas não, digamos, séries de...
Eu estava olhando para esta leitura do MIT sobre complexidade computacional e, às 15:00, Erik Demaine embarca em uma demonstração para mostrar o que é afirmado no título desta pergunta. No entanto, não posso seguir seu raciocínio, na prática o que ele diz é o seguinte: podemos declarar um problema...