Perguntas com a marcação «turing-machines»

Existe uma relação entre a Máquina de Turing e o cálculo Lambda - ou eles surgiram na mesma

Eu tenho três subquestões relacionadas, destacadas pelos pontos abaixo (não, eles não podem ser divididos, se você estiver se perguntando). Andrej Bauer escreveu, aqui , que algumas funções são realizáveis ​​através de uma máquina de Turing, mas não através do cálculo lambda. Um passo fundamental...

Entendo que o modelo de Turing tenha se tornado o "padrão" ao descrever a computação. Estou interessado em saber por que esse é o caso - ou seja, por que o modelo da MT se tornou mais amplamente utilizado do que outros modelos teoricamente equivalentes (ao meu conhecimento), por exemplo, a...

Computadores reais têm memória limitada e apenas um número finito de estados. Portanto, eles são essencialmente autômatos finitos. Por que os cientistas teóricos da computação usam as máquinas de Turing (e outros modelos equivalentes) para estudar computadores? Qual é o sentido de estudar esses...

Todas as funções computáveis ​​no tempo t em uma máquina de Turing de fita única usando um alfabeto do tamanho k = O ( 1 ) podem ser computadas no tempo O ( t ) em uma fita única máquina de Turing usando um alfabeto de tamanho 3 (por exemplo, 0 , 1 , e em branco)?f: { 0 , 1 }∗→ { 0 , 1...

Estou procurando uma resposta definitiva para saber se a geração de números "verdadeiramente aleatórios" é computável por Turing. Não sei como expressar isso com precisão. Esta pergunta do StackExchange sobre "algoritmos eficientes para geração de números aleatórios" chega perto de responder à...

Paul Wegner e Dina Goldin publicam há mais de uma década artigos e livros, argumentando principalmente que a tese de Church-Turing é frequentemente deturpada na comunidade da Teoria da CS e em outros lugares. Ou seja, é apresentado como abrangendo todo o cálculo quando, de fato, se aplica apenas ao...

Na introdução e explicação das classes de complexidade P e NP, muitas vezes dadas pela máquina de Turing. Um dos modelos de computação é o cálculo lambda. Entendo que todos os modelos de computação são equivalentes (e se podemos introduzir algo em termos de máquina de Turing, podemos introduzi-lo...

Se alguém restringir as máquinas de Turing a uma fita finita (ou seja, para usar o espaço limitado ), o problema de parada será decidido, essencialmente porque após várias etapas (que podem ser calculadas a partir do número de estados , e , e o tamanho do alfabeto), uma configuração deve ser...

Estou querendo codificar uma simples máquina de Turing nas regras de um jogo de cartas. Eu gostaria de torná-la uma máquina universal de Turing para provar sua integridade. Até agora, criei um estado de jogo que codifica a máquina de Turing de 2 estados e 3 símbolos de Alex Smith . No entanto,...

Um computador que recebe um fluxo infinito de bits verdadeiramente aleatórios é mais poderoso que um computador sem um. A questão é: ela é poderosa o suficiente para resolver o problema da parada? Ou seja, um computador probabilístico pode determinar se um programa determinístico é interrompido ou...

Se seguirmos o livro (ou qualquer outra versão da especificação da linguagem, se você preferir), quanta energia computacional pode uma implementação C? Observe que “implementação C” tem um significado técnico: é uma instanciação específica da especificação da linguagem de programação C em que o...

Em este artigo da Wikipedia sobre Turing completude afirma que: O cálculo lambda não digitado é Turing completo, mas muitos cálculos lambda digitados, incluindo o Sistema F, não são. O valor dos sistemas digitados é baseado em sua capacidade de representar a maioria dos programas de computador...

Sabemos que (ver, por exemplo, Teoremas 1 e 3 de [1]), grosso modo, sob condições adequadas, funções que podem ser computadas eficientemente pela máquina de Turing em tempo polinomial ("computável eficientemente") podem ser expressas por redes neurais polinomiais com tamanhos razoáveis ​​e,...

Suponha que eu quisesse formalizar a prova de Turing sobre o problema da parada, para que uma máquina pudesse verificá-la. Alguns dos conhecidos sistemas automatizados de prova de teoremas incluem Mizar, Coq e HOL4. Fiz o download e experimentei o Coq, mas ele não possui uma biblioteca para...

Vamos fixar uma codificação sem prefixo de máquinas de Turing e uma máquina de Turing universal que na entrada (codificada como o código sem prefixo de seguido de ) produza o que produz na entrada (possivelmente ambos correndo para sempre). Defina a complexidade de Kolmogorov de , , como a duração...

Não consigo pensar em nenhum modelo desse tipo, talvez alguma forma de cálculo lambda digitado? algum autômato celular elementar? Isso quase refutaria o "Princípio da Equivalência Computacional" de Wolfram: Quase todos os processos que não são obviamente simples podem ser vistos como cálculos...

Uma pergunta muito específica, eu sei, e duvido que seja respondida por qualquer um que ainda não esteja familiarizado com as regras da Magia. Postagens cruzadas para Draw3Cards . Aqui estão as regras abrangentes para o jogo Magic: the Gathering . Veja esta pergunta para obter uma lista de todos os...

Tenho dificuldade em ensinar o conceito de funções computáveis. Tentei desenvolver a idéia de por que pesquisadores como Hilbert / Ackermann / Godel / Turing / Church / ... inventaram a noção de 'computabilidade'. Os alunos imediatamente perguntaram: "o que significa computabilidade?" e não posso...

Lendo alguns tópicos recentes sobre computação quântica ( aqui , aqui e aqui ), lembro-me de uma pergunta interessante sobre o poder de algum tipo de máquina de preservação -norm.ℓpℓp\ell_p Para as pessoas que trabalham com a teoria da complexidade na complexidade quântica, um excelente texto...