Uma máquina de Turing sem a capacidade de escrever em células em branco é menos poderosa que a Turing padrão?

Uma máquina de Turing sem a capacidade de escrever em células em branco é menos poderosa que a Turing padrão?

Acho que a resposta é sim, mas não consigo encontrar um cálculo que a máquina padrão de Turing possa fazer, mas esta máquina não pode.

Alguma ideia?

Em outras palavras, " Um computador com memória limitada seria menos poderoso que um computador com memória ilimitada "?

Nat

Respostas:

O tipo de máquina de Turing que você descreve é um autômato delimitado linear (ele só pode escrever nas partes da fita que contém a entrada). Os LBAs são os aceitadores de linguagens sensíveis ao contexto; portanto, para encontrar um exemplo específico de um problema que não pode ser resolvido com essa restrição, mas que pode ser resolvido em geral por uma máquina de Turing, você só precisa de uma linguagem que seja decidível, mas não contextual. sensível.

O exemplo dado na Wikipedia é:

Um exemplo de linguagem recursiva que não é sensível ao contexto é qualquer linguagem recursiva cuja decisão seja um problema difícil do EXPSPACE, digamos, o conjunto de pares de expressões regulares equivalentes com exponenciação.

Para mais exemplos, consulte Existe um exemplo de uma linguagem recursiva que não é sensível ao contexto?

roctothorpe
fonte

$\textsf{DSPACE}(O(n))$

ordenação rápida
fonte

Você não pode apenas fornecer um sufixo suficientemente longo, para qualquer problema específico, de símbolos especiais no final da fita que possam ser usados como espaços em branco?

gen

@gen Não em geral. No caso mais geral, observe que conhecer um sufixo tão longo tornaria o problema de parada decidível. Conseqüentemente, calcular um prefixo suficientemente longo pode ser indecidível, em geral - portanto, não é razoável supor que esse sufixo seja fornecido.

chi

Seria preciso interpretar essa resposta como " Máquinas de Turing com memória limitada não terão memória suficiente para executar qualquer programa arbitrário, pois alguns programas podem exigir mais memória do que o que eles têm ".

Nat

@ Nat: Gostaria de dizer que "a quantidade de memória que um programa pode exigir é geralmente desconhecida até que o programa seja executado". O curioso (um grande paradoxo matemático) é que, para qualquer trigêmeo inteiro X, Y, Z, existe um limite superior ao número de células de fita necessárias para programas que terminarão e que contêm no máximo estados X, em fitas que podem conter na maioria dos tipos de símbolos Y, e são inicializados com símbolos Z na fita, mas esse limite superior não é possível, exceto por valores triviais de X, Y e Z. #

307