Existeix algun mètode que permeti saber si un problema matemàtic té solució o no?

Aquesta és la pregunta que va formular David Hilbert en la primera meitat del segle XX i a la qual Alan Turing va intentar trobar una resposta. A primer cop d'ull és una qüestió difícil de contestar i  l'existència d'aquest mètode pot semblar impossible. Imagineu-vos, per un instant, que existeix i el coneixem. Aleshores hauríem pogut determinar fàcilment la resposta a grans enigmes de la història, tals com l'enigma de Fermat!

Alan Turing

Alan Turing va ser un gran matemàtic que va destacar en el camp de la lògica, i actualment és considerat un dels pares de la informàtica moderna, en part gràcies a la invenció de la Màquina de Turing, creada amb l'objectiu de trobar una resposta a la pregunta inicial. Aquest innovador aparell estava format per una cinta dividida en cel·les de contingut modificable, que es podia moure cap a un costat o cap a l'altre segons unes instruccions determinades. A més, la màquina està basada en algorismes o algoritmes i a la seva època va suposar una gran revolució.

Esquema de la màquina de Turing

Què és un algorsime o algoritme?

Un algorisme o algoritme és un conjunt de regles ordenades que ens permeten estructurar un problema matemàtic. Fixem-nos, però, que també són aplicables a problemes o situacions ben  quotidians. Vege-m'ho amb un exemple senzill.

Imaginem-nos que, ara que fa tanta calor, volem anar a la platja per bronzejar el nostre cos. Un possible algoritme que utilitzaríem seria:

1. Porto el banyador?

1a. SI > Passa al punt 2

1b. NO: Posa't el banyador > Torna al punt 1

2. He agafat la tovallola?

2a. SI > Passa al punt 3

2b. NO: Agafa la tovallola > Torna al punt 2

3. Porto crema solar?

3a. SI > Ja pots marxar a la platja

3b. NO: Agafa la crema solar > Torna al punt 3

D'aquesta manera hem pogut estructurar el problema en diversos passos ordenats.

Finalment, gràcies a la Màquina de Turing, Alan Turing va poder concloure que no existeix cap mètode per saber si un problema té solucions o no.

Per saber-ne més: