Debora_Problema da parada Ladrilhos

Prévia do material em texto

Nome: Debora Chaia Stadler
Problema da Parada
Na teoria da computação o experimento mental do problema da parada é um problema de decisão que 
pode ser declarado informalmente da seguinte forma:
Dado uma descrição de um programa e uma entrada finita, decida se o programa termina de rodar ou 
rodará indefinidamente, dada essa entrada.
Dada a descrição de uma linguagem simples, um programa escrito nessa linguagem e uma entrada para 
esse programa, você deve determinar se o programa dado pára com a entrada dada e, em caso positivo, 
qual a saída produzida.
Esta linguagem só trabalha com números inteiros de 0 a 999 (inclusive). Sendo assim, o sucessor de 
999 é 0, e o antecessor de 0 é 999. Além disso, ela possui dez variáveis (R0 a R9), sendo que a R0 
sempre é atribuído o valor de chamada do programa (ou seja, o parâmetro de entrada) e a R9 é sempre 
atribuído o valor de saída (o retorno). No início da execução do programa, é atribuído o valor 0 a todas 
as variáveis, com exceção de R0 que recebe o parâmetro de entrada.
Por exemplo, em pseudocódigo, o programa:
enquanto Verdadeiro: continue
Não para, pelo contrário, entra em loop infinito. Por outro lado, o programa:
imprimir "Hello World!"
Para muito rapidamente.
Um programa mais complexo pode ser mais difícil de se analisar. O programa pode rodar por um tempo 
fixo e se ele não parar, não há um jeito de saber se o programa irá parar eventualmente ou se ele irá 
continuar   rodando para  sempre.  Turing  provou que não há  um algoritmo que pode ser  aplicado a 
qualquer programa arbitrário,  com uma entrada,  para decidir  se o programa pára ou não com esta 
entrada.
Problema do Ladrilho
O Problema do Ladrilhamento foi proposto por Hao Wang em 1960. Os dados de entrada são um 
conjunto finito, T, de tipos de ladrilhos.
O problema é determinar se podemos ladrilhar qualquer grade n x n, com ladrilhos detipos indicados no 
conjunto T. Uma grade n x n é uma região quadrada do plano subdividida em n x n celas iguais e 
uniformes.
As seguintes condições devem ser respeitadas:
• Os ladrilhos não podem ser girados, i.e., rotacionados.
• Podemos usar tantos ladrilhos quantos forem necessários, desde que idênticos a um daqueles 
contidos no conjunto de tipos T. Ou seja, temos um estoquepotencialmente ilimitado de cada 
tipo de ladrilho.
• As cores nas faces de ladrilhos  que se  tocam, ao serem posicionados na grade,  devem ser 
idênticas.
• Na área quadrada demarcada, não podemos deixar regiões sem ladrilhar.
Uma região 3 por 3 do plano poderia ser ladrilhada com este conjunto de ladrilhos.
Por redução como é demonstrado que Correspondência em Post é nãosolucionável, então o problema de 
ladrilhamento é não solucionável. E como existem casos em que o algoritmo pára então e ele é não 
solucionável, logo é um problema parcialmente solucionável. CQD.
O Problema do Ladrilhamento é Não Solucionável. Fora deduzido por meio deredução, com uso dos 
teoremas e definições constantes neste artigo que o problemaproposto por Hao Wang em 1960 pertence 
a classe das linguagem Enumeráveis Recursivamente, e como tal, comportar­se como uma função não 
solucionável.