O objetivo de Turing ao construir seu conceito era formalizar como os humanos fazem o raciocínio abstrato. Agora me corrija se eu estiver errado, mas esse raciocínio parece apenas um exercício em que você manipula um conjunto de declarações formais, ou seja, strings sem nenhuma semântica associada...
A máquina de Turing foi inventada por uma mente humana. Presumivelmente, nada menos poderoso do que uma máquina de Turing pode inventar uma máquina de Turing. No entanto, uma máquina de Turing possui fita infinita, enquanto a mente está situada em um universo finito e, portanto, só pode ser uma...
Sabe-se que qualquer máquina de Turing (determinística, com uma única fita) que executa no tempo decide um idioma regular (por exemplo, consulte este link ). Assim, existe uma máquina de Turing equivalente que roda no tempo . Em outras palavras, se entãoo(nlogn)o(nlogn)o(n\log...
É o que se sabe sobre o problema da parada e a semi-decidibilidade: O problema de parada diz que, para uma dada entrada xe uma máquina H, não podemos dizer se a máquina H pára ou não na entrada x. Diz-se que um idioma é semi-decidível se existir uma máquina de Turing que pare se uma palavra...
Existe uma definição equivalente para a classe NLNL\mathsf{NL}com verificador. Esses verificadores são máquinas de Turing determinísticas que podem ler a fita testemunha apenas uma vez, de uma maneira, da esquerda para a direita. Dada uma função f:N→Nf:N→Nf:\mathbb{N}\to\mathbb{N} nós dizemos isso...
Estou me sentindo um pouco confuso com a direção das reduções usadas para mostrar que certos idiomas não são recursivos. Por exemplo, digamos que queremos determinar se o problema de parada (HA LTTMHALTTMHALT_{TM}) é indecidível. Eu sei que podemos assumir que é decidível e tentar construir uma...
Entre os graus de Turing estão os graus da forma 0n0n0^n, por exemplo 000, 0′0′0', 0′′0″0''etc. Vou provar isso rápido por uma questão de integridade. Espero que ninguém tenha dúvidas com esta breve prova: Lema: Qualquer conjunto contável de conjuntos de números naturais pode ser codificado...
Alguém sabe o quão eficiente foi a primeira máquina de Turing fabricada por Alan Turing? Quero dizer, quantos movimentos ele fez por segundo, mais ou menos ... Só estou curioso. Também não foi possível encontrar nenhuma informação sobre isso na