Turing Machine
What is it?
Uma Máquina de Turing é um modelo matemático de computação que define uma máquina
abstrata que contém uma fita teoricamente infinita. Seguindo um conjunto de regras, esta
manipula símbolos em cada célula (ou pequeno intervalo) da fita,. Dado qualquer algoritmo
na computação, uma máquina de Turing equivalente pode ser construída aplicando a lógica
deste algoritmo.
a-machine
1936
How does it work?
1. uma fita teoricamente infinita, que é dividida em células contendo símbolos de um
alfabeto finito
2. uma cabeça (ou cabeçote) para leitura ou escrita das células na fita
3. um registro de estados, que armazena o estado atual da máquina
4. um grupo finito de instruções que, dado o estado da máquina e o símbolo lido pela
fita, diz a máquina o que fazer em seguida.
Existem variações da máquina de Turing baseadas em diferentes modelos; em alguns, a
cabeça só pode ler, apenas ir para frente, apenas escrever, ou combinações destes e
outros diferentes parâmetros.
Na fita, há símbolos que a máquina pode ler e escrever, contanto que se contenha a
apenas uma leitura e uma possível escrita por célula. A operação exata da máquina
depende do grupo de instruções finito providenciado. Exemplos seriam:
“no estado 5, se o símbolo visto é 0, escreva 1.
se o símbolo visto é 1, mude para o estado 4.
se o símbolo visto é 0, escreva 1 e mude para o estado 2…” e assim em diante.
Em sumo, é uma abstração de uma máquina capaz de executar um algoritmo qualquer.
Turing Test
What is it?
O Teste de Turing, originalmente chamado de jogo da imitação, é um teste da habilidade de
uma máquina de exibir comportamento inteligente indistinguível de um humano.
How does it work?
O jogo da imitação original consiste em um cenário com três participantes: um homem
(representado pela letra A), uma mulher (B) e um interrogador (C). Neste cenário, o homem
tenta se passar por uma mulher, enquanto esta tem que provar que ela é a mulher de
verdade. O papel do interrogador é decifrar qual dos dois participantes é a verdadeira
mulher e qual não é.
A proposição de Turing é: “...dado um computador D, caso seja modificado para ter o
armazenamento necessário, tenha sua velocidade de computação aumentada, e
providenciado com um programa apropriado, ele pode tomar a parte de ‘A’ no jogo da
imitação, sendo B tomado por um outro humano?”
Logo, o verdadeiro teste (como definido e interpretado atualmente) consiste no interrogador
a fazer perguntas, e obter respostas, em linguagem natural escrita, para determinar qual
dos dois participantes é um computador e qual não é. Perguntas que envolvem sentimentos
humanos complexos, moralidade, opiniões pessoais e interpretação avançada de texto
podem ser utilizadas, como no exemplo “você deixaria um adulto morrer para salvar duas
crianças, ou duas crianças morrerem para salvar cinco adultos?”.
Perguntas tais como esta podem ser usadas para determinar, baseado na resposta obtida,
se estamos lidando com uma máquina ou um humano.
AUTOMATA
What are they?
Um autômato (na computação e na matemática) pode ser definido, formalmente, como um
dispositivo abstrato que opera a si mesmo (até um certo ponto) seguindo uma sequência de
operações, ou respondendo a instruções predeterminadas.. No mundo real, consistem em
máquinas, dispositivos e sistemas que operam sozinhos, e necessitam de pouca ou
nenhuma interferência humana no seu funcionamento.
How can they be classified as?
As principais famílias de autômatos são:
- Autômatos de pilha (ou autômatos de pushdown), uma máquina de estado finito
mais avançada, onde é possível utilizar o topo de uma pilha para decidir qual
transição irá ocorrer, e a própria pilha pode ser manipulada como parte da transição.
- Máquinas de Turing, que, como descrito anteriormente, são autômatos que
permitem (pela sua natureza infinita, iterável e adaptável) descrever qualquer
algoritmo, seja este com estados finitos ou infinitos.
- Autômatos linearmente limitados, que são, efetivamente, máquinas de Turing não-
determinísticas (ou seja, existe mais de uma ação possível resultante das mesmas
situações; Seu próximo estado não é completamente determinado pela ação atual e
o símbolo que ela vê, ao contrário da Máquina de Turing estandarte).
FINITE AUTOMATA
What is it?
Um autômato finito define-se por uma máquina abstrata que pode possuir diferentes
estados, sendo o número destes estados limitado (ou finito). Esta máquina pode, por meio
de entradas alimentadas a ela, passar por uma transição e mudar entre estes estados.
Um exemplo clássico seria o semáforo, com três possíveis estados: vermelho, amarelo e
verde. A transição entre estes depende (normalmente) do tempo passado. Outro exemplo
seria uma catraca, que possui apenas dois estados: travada e destravada. Para transicionar
do estado travado para destravado, é utilizado uma moeda; na direção contrária, é
necessário empurrar a catraca. Nenhuma das duas operações (inserir a moeda ou empurrar
a catraca) modifica os estados opostos (destravado -> inserir a moeda ou travado ->
empurrar).
How can they be classified as?
Autômatos finitos determinísticos são aqueles cujas mudanças de estado são sempre
previsíveis no sentido de uma entrada sempre resultar em um específico estado.
Autômatos finitos não-determinísticos, por sua vez, apresentam um comportamento
contrário: uma entrada pode causar a mudança do estado para qualquer estado diferente.
MERRIAM-WEBSTER, Definition of Automaton, 2011.
Acesso em 08/04/2022.
Disponível em:
[Link]
SAYGIN et al., Turing Test: 50 Years Later, 2000.
Acesso em 07/04/2022.
Disponível em:
[Link]
SMITH, Alex. Proof that the Turing Machine is Universal, 2007.
Acesso em 08/04/2022.
Disponível em:
[Link]