Máquinas de Turing equivalentes: diferenças entre revisões

Nós resolvemos esse problema ao introduzir uma máquina de Turing de ''k''-cadeia com entrada e saída. Isso é o mesmo que uma máquina de Turing de ''k''-cadeia ordinária, exceto que a função de transição <math>\delta</math> é limitada, de modo que a fita de entrada nunca pode ser alterada, e assim como a cabeça de saída nunca pode se mover para a esquerda. Este modelo nos permite definir classes de espaço determinísticas menores do que a linear. Máquinas de Turing com entrada-e-saída também tem a mesma complexidade de tempo que as outras máquinas de Turing; em outras palavras de Papaditriou 1994 Prop 2.2:

 

 

Máquinas de Turing de ''k''-cadeia com entrada e saída são frequentemente usadas em definições formais de recursos de complexidade [[DSPACE]] em, por exemplo, Papadimitriou 1994 (Def. 2.6).