Máquinas de Turing

19 março 2010, 14:30 • José Félix Costa

Máquinas de Turing.
Tempo de execução e espaço de trabalho das máquinas de Turing: tempo de computação de uma máquina determinística relativamente a um input, tempo de execução de uma máquina determinística, tempo de computação de uma máquina não determinística relativamente a um input, tempo de execução de uma máquina não determinística, espaço de computação de máquinas determinísticas e não determinísticas relativamente a um input, espaço de trabalho de máquinas determinísticas e não determinísticas.
Linguagem decidida por uma máquina (determinística, não determinística) em (tempo, espaço) f.