Máquina de Turing universal

Em ciência da computação, uma máquina de Turing universal (MTU) é uma máquina de Turing que consegue simular outra máquina de Turing arbitrária com uma entrada arbitrária. Essencialmente, essa máquina universal realiza a simulação lendo tanto a descrição da máquina a ser simulada quanto sua respectiva entrada representada pelo conteúdo de sua fita. Alan Turing apresentou essa máquina em 1936–1937. Este modelo é considerado por alguns (por exemplo, Martin Davis (2000)), como a origem do computador com programa armazenado —usado por John von Neumann (1946), que atualmente leva seu nome: a Arquitetura de von Neumann. Esta máquina também é conhecida como máquina de computação universal, máquina universal, máquina U ou simplesmente U.Em termos de complexidade computacional, uma máquina de Turing universal multi-fita é mais lenta apenas por um fator logarítmico comparada às máquinas que ela simula.