Resultats de la cerca

Dit més informalment, un conjunt X és recursiu quan existeix un algorisme que permet de decidir la resposta a la pregunta ' x ∈ X'

D’una banda, es preguntà si tot grup engendrat per un nombre finit d’elements i en el qual tot element és d’ordre finit és necessàriament finit aquesta conjectura fou resposta negativament per Novikov el 1959 D’altra banda, demostrà que si p i q són enters primers diferents, aleshores tot grup d’ordre p 2 q és grup resoluble

La ciutat prussiana de Königsberg actualment Kaliningrad està dividida pel riu Pregol’a, que voreja l’illa de Kneiphof Hi havia set ponts disposats com s’indica a la figura Els habitants de la ciutat es plantejaven si era possible fer un recorregut tancat que passés una sola vegada per cadascun dels set ponts En llenguatge de teoria de grafs, la pregunta és si el graf és eulerià La resposta és negativa La solució del problema va ser trobada per Leonard Euler, el 1736, introduint per primer cop la noció de graf i resolent a la vegada un problema de caràcter més general

D’una banda si hom disposa d’un alfabet finit OOO = {a 1 ,,a n } i, per concatenació, construeix els mots M = ζ 1 ζ r , on cada símbol ζ i és una de les lletres a j ∈ OOO d’aquest alfabet i r ∈ ℕ si, d’altra banda, hom disposa d’un cert diccionari que estableix l’equivalència de certes parelles de mots i, finalment, hom accepta el fet que, en substituir en un mot M = M 1 mM 2 un cert sumbmot m per un altre mot m´ equivalent, obté un mot equivalent M´ = M 1 m' M 2 Cal plantejar la pregunta següent donats dos mots arbitraris M i N , hi ha algun algorisme que permeti de decidir si són…