Teoria da computacao

Máquina de Turing

A máquina de Turing também conhecida como maquina universal e considerada como o primeiro computador, foi criada pelo matemático Alan Turing (1912-1954) “pai da computação” com a intenção de desvendar os códigos da máquina enigma, a mesma é um modelo abstrato de um computador restringindo apenas no seu aspecto lógico de seu funcionamento.

Uma máquina de Turing possui:

Uma fita: Que é dividida em células e cada célula possui um símbolo de um alfabeto finito

Um cabeçote: Responsável por ler e escrever os símbolos na fita movendo da esquerda para a direita.

Um registador: Armazena o estado da máquina.

Tabela de ação: Diz a máquina qual símbolo deve escrever e como deve mover o cabeçote.

Quais os componentes de uma máquina de Turing?

Fita, cabeçote, registrador e uma tabela de ação.

Computabilidade

Computabilidade é a habilidade de resolver problemas de uma forma efetiva com a utilização de um algoritmo para a solução do mesmo.

Computadores possuem capacidade de receber como entrada de dados uma sentença (um programa) escrito em uma linguagem artificial computável (a linguagem suportada pelo computador) e executar tarefas bem definidas, baseadas na interpretação da sentença recebida. O ato de interpretação desta sentença (isto é, o programa) corresponde à execução do programa.

Durante sua execução o programa recebe entradas de dados informadas pelo usuário e produz saídas de dados que são captadas pelo usuário.

A entrada de dados efetuada pelo usuário do programa também é formada por sentenças em uma linguagem, visto que o conjunto de símbolos que o usuário digita também é composto conforme um alfabeto e regras de formação bem definidas. Sendo assim, a entrada de dados do programa pertence à linguagem artificial definida pelo programador (a linguagem usada pelo usuário do programa).

A ideia de computabilidade surge de um determinado problema onde possa ser resolvido através de uma tarefa dentro da computação, podendo ser:

Problemas de decisão: fixam um conjunto S, que pode conter strings, números naturais, ou outros objetos retirados de um conjunto maior U. Uma instancia particular do problema é decidir, dado um elemento de u de U, se u está contido em S. O Teste de Primalidade é um desses exemplos.

Problemas de função: Os problemas de função consistem de uma função f de um conjunto U para um conjunto V. Uma instância do problema é computar, dado um elemento u de U, o elemento correspondente f(u) em V. Por exemplo, U e V podem ser o conjunto de todas as strings binárias, e f pode ser uma função que recebe uma string e retorna a string obtida ao reverter todos os dígitos da entrada (logo, f(0101) = 1010).

O que significa computabilidade?

A maneira de solucionar um problema de uma forma efetiva através de algum algoritmo.

Programas, Maquinas e Computações

Programas:

Conjunto estruturado de instruções que capacitam uma máquina a aplicar sucessivamente certas operações básicas e testes sobre os dados iniciais fornecidos com o objetivo de transformar esses dados numa forma desejável, podemos ser

Monolíticos: desvios condicionais e incondicionais

Iterativos: estruturas de iteração

Recursivos: sub-rotinas recursivas

Maquinas: Possui uma interpretação para cada operação ou teste que constituem o programa.

Computação: Histórico do funcionamento da máquina para o programa e um dado valor inicial

Qual a importância dos programas?

Muito importante

...