Máquinas de Turing e teoria da computação

Em 1936, para calcular qualquer função computável, a máquina inventada por “Alan Turing" foi chamado "Turing Machine (TM)”. Na ciência da computação, a TM é o modelo matemático abstrato de computação e construção teórica primária. Máquinas de Turing trabalham através de um número incontável pré-programado de instruções. Ele desempenha um papel importante e ajuda os usuários a encontrar o cálculo delimitando o “Funções computáveis”.

Este artigo explicará brevemente as máquinas Turing, sua teoria de trabalho e computabilidade.

O que é Turing Machine?

A máquina de Turing foi inventada por Alan Turing. Inicialmente, foi nomeado um “Machine A (máquina automática)”. Mais tarde, esse termo foi alterado para “Máquina de Turing" por "Igreja de Alonzo”, Que foi o consultor de doutorado de Turing.

Uma máquina de Turing é um modelo matemático de computação baseado em conjuntos de instruções infinitas usadas para implementar qualquer algoritmo de computador. A manipulação de símbolos é feita de acordo com uma tabela de regras em uma faixa de fita.

Como funciona a máquina Turing?

A máquina de Turing funciona com uma fita de memória infinita dividida em células individuais. Cada célula pode manter um símbolo desenhado de um conjunto infinito de símbolos. Esses símbolos são conhecidos como o alfabeto da máquina. A máquina tem um “CABEÇA”Isso aponta para o estado inicial de implementar o algoritmo de computação.

Além disso, pode ser movido sobre uma dessas células para serem posicionadas. A seleção de “estado”Pode ser feito a partir de um conjunto de estados finitos. Head lê o símbolo (alfabetos da máquina) da célula em cada etapa. Depois de ler o símbolo da célula, o novo símbolo pode ser adicionado à mesma célula pela máquina Turing. Na base do novo símbolo, ele pode mover o ponteiro da cabeça um passo para a direita ou para a esquerda. Pode ser possível que o processo de computação pare.

O que é compatibilidade e tese da igreja?

A compatibilidade não é apenas a máquina A (máquina de Turing), uma função recursiva, linguagem de programação Pascal ou cálculo, mas a combinação de todos. A Alonzo Church, consultora de doutorado de Turing, apresentou esse conceito conhecido como “Tese da igreja”. Também é chamado de “Tese de ator de igreja”.

Além disso, não é um teorema, mas é usado para comparar a função computável com as funções que podem ser calculadas por a-máquina. Essas funções que não são computáveis ​​pelas máquinas A não podem ser calculadas por outro método. Quando o conceito de tese da igreja foi formulado, naquela época, as pessoas não sabiam sobre a capacidade dos computadores modernos, e foi uma conquista tão significativa.

Máquinas de Turing e teoria da computação

Um conjunto de números naturais é um conjunto computável decidível ou turing. Por exemplo, temos uma máquina de Turing com o número “m”, Que se torna interrompido quando a saída é 1 se“m”Está no conjunto computável. Por outro lado, ele pára quando a saída é 0 se “m”Não está no conjunto de números naturais. Uma função "r”De um número natural para um número natural é um“Turing computável”. Pode -se observar que nem todo conjunto de números natural é computável.

Explicamos o conceito da máquina de Turing e a teoria da computação.

Conclusão

A máquina de Turing foi inventada por “Alan Turing”Em 1938, para calcular qualquer função computável. É o modelo matemático abstrato de computação e uma construção teórica central na ciência da computação. Uma máquina de Turing é um modelo matemático de computação baseado em conjuntos de instruções infinitas usadas para implementar qualquer algoritmo de computador. A manipulação de símbolos é feita de acordo com uma tabela de regras em uma faixa de fita. Este artigo demonstrou os conceitos de máquinas de Turing e teoria da computação.