OS SISTEMAS DE INFORMAÇÃO

...

A entrada que está inscrita na fita antes do início da computação deve consistir de um número finito de símbolos. No entanto, a fita é de comprimento ilimitado - para o objetivo de Turing era mostrar que há tarefas que estas máquinas são incapazes de executar, mesmo tendo memória de trabalho ilimitada e tempo ilimitado.

[pic 1]

Uma máquina de Turing

A cabeça de leitura / gravação é programável. É útil pensar na operação de programação como consistindo em alterar a cablagem interna da cabeça por meio de um arranjo de quadro de conectores. Para calcular com o dispositivo, você programa-lo, inscrever a entrada na fita (em código binário ou decimal, digamos), coloque a cabeça sobre o quadrado contendo o símbolo de entrada mais à esquerda e defina a máquina em movimento. Uma vez concluído o cálculo, a máquina para com a cabeça posicionada sobre o quadrado que contém o símbolo mais à esquerda da saída (ou em qualquer outro lugar se programado).

Estados

A cabeça contém um sub dispositivo que eu chamo de indicador. Esta é uma segunda forma de memória de trabalho. O indicador pode ser configurado para qualquer um de um número de 'posições'. No jargão da máquina de Turing, a posição do indicador a qualquer momento é chamada o estado da máquina naquele tempo. Para dar um exemplo simples da função do indicador, ele pode ser usado para acompanhar se o símbolo encontrado pela última vez foi '0' ou '1'. Se '0', o indicador é ajustado para sua primeira posição, e se '1', para sua segunda posição.

Operações atômicas

Existem apenas seis tipos de operações fundamentais que uma máquina de Turing realiza no decurso de uma computação. Pode:

- Ler (ou seja, identificar) o símbolo atualmente sob a cabeça

- Escreva um símbolo no quadrado sob a cabeça (depois de apagar primeiro o símbolo já escrito, se houver)

- Mover a fita para a esquerda um quadrado

- Mova a fita para a direita um quadrado

- Estado de alteração

- Parar

Estas são chamadas operações primitivas ou atômicas da máquina. Uma computação complicada pode consistir em centenas de milhares, ou mesmo milhões, de ocorrências desses átomos

Computadores comercialmente disponíveis são hard-wired para executar operações primitivas consideravelmente mais sofisticadas do que as de uma máquina de Turing - adicionar, multiplicar, decrementar, armazenar em endereço, ramo, e assim por diante. A constituição precisa da lista de primitivos varia de fabricante para fabricante. É um fato notável que nenhum desses computadores pode superar uma máquina de Turing. Apesar da simplicidade austera da máquina de Turing, é capaz de computar qualquer coisa que qualquer computador no mercado possa computar.

De fato, uma vez que é uma máquina abstrata ou nocional, uma máquina de Turing pode calcular mais do que qualquer computador físico. Isso ocorre porque (1) o computador físico tem acesso a apenas uma quantidade limitada de memória, e (2) a velocidade de operação do computador físico é limitada por várias restrições do mundo real.

Às vezes é dito, incorretamente, que uma máquina de Turing é necessariamente lenta, já que a cabeça está continuamente mexendo para trás e para frente, um quadrado de cada vez, ao longo de uma fita de comprimento ilimitado. Mas uma vez que uma máquina de Turing é um dispositivo idealizado, não tem restrições no mundo real sobre sua velocidade de operação.

A tabela de instruções

Um programa ou "tabela de instruções" para uma máquina de Turing é uma coleção finita de instruções, cada uma exigindo que certas operações atômicas sejam executadas se certas condições forem atendidas. Cada instrução é da forma:

Se o estado atual é n e o símbolo atualmente sob a cabeça for x, então escreva y no quadrado atualmente sob a cabeça [y pode ser idêntico a x], vá para o estado m [m pode ser n] e - - - .

Em lugar de - - - pode ser escrito quer 'mover para a esquerda um quadrado' ou 'mover para a direita um quadrado' ou 'parar'.

Um exemplo

A máquina neste exemplo começa a trabalhar com uma fita em branco. A fita é infinita. O problema é configurar a máquina para que, se o scanner estiver posicionado sobre qualquer quadrado e a máquina for colocada em movimento, ele imprimirá dígitos binários alternados na sua cassete, 0 1 0 1 0 1 ..., trabalhando para a direita A partir do seu ponto de partida, e deixando um quadrado em branco entre cada dígito.

Para fazer seu trabalho a máquina faz uso de quatro estados, rotulados ' a ', ' b ', ' c ' e ' d '. A máquina está no estado a quando começa a trabalhar.

A tabela de instruções para esta máquina é a seguinte. A linha superior da tabela lê: se você estiver no estado a eo quadrado que você está digitalizando estiver em branco, em seguida, imprima 0 no quadrado escaneado, mova um quadrado para a direita e entre em estado b.

Estado

Símbolo digitalizado

impressão

mover

Próximo estado

uma

em branco

0

R

B

B

em branco

R

C

C

em branco

1

R

D

D

em branco

R

uma

Uma máquina