achei um texto que tinha feito pra universidade falando sobre máquinas de turing, processos computáveis, teoria da computação e outras noias. vale o registro.
As limitações computacionais são norteadas pela velocidade e capacidade dos processamentos de informações? O ser humano usa a tecnologia para se (re)descobrir? O que pode ser computado? E o que não pode ser computado?
Existem máquinas abstratas que foram modeladas matematicamente para cumprir tarefas de decisão, semi decisão, gerar linguagens e computar funções. A máquina abstrata mais conhecida é a do matemático britânico Alan Turing. Ele mostrou como um sistema de autômatos poderia manipular símbolos e linguagens de um sistema de regras próprias. Até hoje essa máquina é estudada por teóricos da computação, pesquisadores de Inteligência Artificial, artistas do Ciberespaço.
A máquina de Turing pode ser dividida naquela que é computável e na efetivamente computável, ou também, caracterizada como máquinas que semi decidem ou decidem uma linguagem. As máquinas computável ou as que semi decidem não são úteis para formular algoritmos computacionais porquê nunca saberemos quando a máquina, por ser infinita, vai parar. Só vamos considerar algoritmos as máquinas que páram, que são efetivamente computável. Essa discussão é base da tese proposta por Alan Turing e Alonzo Church, que concluíram que não é possível construir um artefato de cálculo mais poderoso que um computador. Turing descreveu: “Toda ‘função que seria naturalmente considerada computável’ pode ser computada por uma Máquina de Turing.”
Devido à imprecisão do conceito e por ser uma tese, não pode ser nem
provada nem refutada. Até hoje, pesquisadores desenvolvem técnicas para
explorar o poder das Máquinas de Turing, evidenciando também suas
limitações.
Com base nessas informações podemos concluir que: a capacidade dos
dispositivos computacionais só semidecidem ou decidem uma fração
infinitesimal do conjunto de todas possíveis linguagens. Mas qual seria
a base real da computação? Máquinas de Turing de (Máquinas de Turing)?
0000000011111111000000000111111111111110000000011100011
