Accés més ràpid que el navegador!
31 les relacions: Alan Turing, Alemany, Algorisme, Alonzo Church, Arquitectura de von Neumann, Autòmat cel·lular, Autòmat finit, Càlcul lambda, Complexitat computacional, Conjunt de Mandelbrot, Constant de Chaitin, Entscheidungsproblem, Funció recursiva, Gramàtica formal, Joc de la vida, John Horton Conway, Llenguatge de programació, Llenguatge formal, Màquina de Turing, Màquina de Turing no determinista, Màquina de Turing probabilística, Màquina oracle, Nombre computable, Nombre real, Ordinador, Ordinador quàntic, Problema de decisió, Problema de la parada, Teoria de la computació, Tesi de Church-Turing, Turing complet.
Alan Turing
Alan Mathison Turing (Maida Vale, 23 de juny de 1912 - Wilmslow, 7 de juny de 1954) fou un científic, matemàtic, lògic, criptoanalista, biomatemàtic i maratonià britànic.
Nou!!: Teoria de la computabilitat і Alan Turing · Veure més »
Alemany
L'alemany (Deutsch) és una llengua germànica occidental parlada principalment a l'Europa Central.
Nou!!: Teoria de la computabilitat і Alemany · Veure més »
Algorisme
nombres primers Un algorisme (o, alternativament, algoritme) és un conjunt finit d'instruccions o passos que serveixen per a executar una tasca o resoldre un problema.
Nou!!: Teoria de la computabilitat і Algorisme · Veure més »
Alonzo Church
fou un matemàtic americà i lògic que va fer importants contribucions a la lògica matemàtica i als fonaments la informàtica teòrica.
Nou!!: Teoria de la computabilitat і Alonzo Church · Veure més »
Arquitectura de von Neumann
von Neumann L'arquitectura de von Neumann és la d'un ordinador amb un sistema d'emmagatzematge principal on es guarden tant les instruccions com les dades.
Nou!!: Teoria de la computabilitat і Arquitectura de von Neumann · Veure més »
Autòmat cel·lular
Animació del Joc de la vida de Conway, un autòmat cel·lular. Un autòmat cel·lular (A.C.) és un model matemàtic per a un sistema dinàmic que evoluciona en passos discrets.
Nou!!: Teoria de la computabilitat і Autòmat cel·lular · Veure més »
Autòmat finit
Esquema lògic d'un autòmat finit Un autòmat finit (AF) o màquina d'estats finits (FSM de l'anglès Finite State Machine) és un model matemàtic d'un sistema compost per estats, transicions i accions.
Nou!!: Teoria de la computabilitat і Autòmat finit · Veure més »
Càlcul lambda
El càlcul lambda (o càlcul-λ) és un sistema formal dissenyat per investigar la definició de funció, la noció d'aplicacions de funcions i la recursió.
Nou!!: Teoria de la computabilitat і Càlcul lambda · Veure més »
Complexitat computacional
La teoria de complexitat computacional és la part de la teoria de la computabilitat que estudia els recursos requerits durant el càlcul per resoldre un problema.
Nou!!: Teoria de la computabilitat і Complexitat computacional · Veure més »
Conjunt de Mandelbrot
184x184px La naturalesa fractal del conjunt de Mandelbrot es manifesta en ser ampliat indefinidament. En matemàtiques, es defineix el conjunt de Mandelbrot M com el lloc geomètric de connexitat de la família uniparamètrica de polinomis quadràtics següent: \_.
Nou!!: Teoria de la computabilitat і Conjunt de Mandelbrot · Veure més »
Constant de Chaitin
En complexitat computacional, la constant de Chaitin o nombre Omega de Chaitin o probabilitat de parada és, de forma informal, la probabilitat de que un programa escrit al atzar aturi correctament una màquina de Turing determinista.
Nou!!: Teoria de la computabilitat і Constant de Chaitin · Veure més »
Entscheidungsproblem
El Entscheidungsproblem (en català: problema de decisió) fou el repte en lògica simbòlica de trobar un algorisme que decidís si una fórmula de càlcul de primer ordre és un teorema.
Nou!!: Teoria de la computabilitat і Entscheidungsproblem · Veure més »
Funció recursiva
En lògica matemàtica i computació, les funcions recursives o també conegudes com a funcions recursives-μ són una classe de funcions dels nombres naturals en els nombres naturals que són "computables" en un sentit intuïtiu.
Nou!!: Teoria de la computabilitat і Funció recursiva · Veure més »
Gramàtica formal
teoremes. En alguns sistemes formals, però, el conjunt dels teoremes coincideix amb el de les fórmules ben formades. Una gramàtica formal és un objecte o model matemàtic que permet especificar un llenguatge o llengua, és a dir, és el conjunt de regles capaços de generar totes les possibilitats combinatòries de l'idioma, ja sigui aquest un llenguatge formal o un llenguatge natural.
Nou!!: Teoria de la computabilitat і Gramàtica formal · Veure més »
Joc de la vida
''Pistola de planadors'' de Bill Gosper (Glider Gun). El joc de la vida és un autòmat cel·lular dissenyat pel matemàtic britànic John Horton Conway el 1970.
Nou!!: Teoria de la computabilitat і Joc de la vida · Veure més »
John Horton Conway
John Horton Conway (Liverpool, 26 de desembre de 1937- Princeton, 11 d'abril de 2020) --> va ser un prolífic matemàtic anglès actiu en la teoria de grups finits, la teoria de nusos, la teoria de nombres, la teoria de jocs combinatoris i la teoria de la codificació.
Nou!!: Teoria de la computabilitat і John Horton Conway · Veure més »
Llenguatge de programació
Codi font d'un programa escrit en llenguatge BASIC. Un llenguatge de programació és un llenguatge informàtic utilitzat per controlar el comportament d'una màquina, normalment un ordinador.
Nou!!: Teoria de la computabilitat і Llenguatge de programació · Veure més »
Llenguatge formal
teoremes. En alguns sistemes formals, però, el conjunt dels teoremes coincideix amb el de les fórmules ben formades. A matemàtiques, lògica, i ciències de la computació, un llenguatge formal és un llenguatge on els símbols primitius i regles per a unir aquests símbols estan formalment especificats.
Nou!!: Teoria de la computabilitat і Llenguatge formal · Veure més »
Màquina de Turing
Fotografia d'Alan Turing (1930) La màquina de Turing és un model computacional introduït per Alan Turing en el treball "On computable numbers, with an application to the Entscheidungsproblem", publicat per la Societat Matemàtica de Londres, en el qual s'estudiava la qüestió plantejada per David Hilbert sobre si les matemàtiques són decidibles, és a dir, si hi ha un mètode definit que pugui aplicar-se a qualsevol sentència matemàtica i que resolgui si és certa o no.
Nou!!: Teoria de la computabilitat і Màquina de Turing · Veure més »
Màquina de Turing no determinista
En teoria de la computació, una Màquina de Turing no determinista (MTN) és una Màquina de Turing on el seu mecanisme de control treballa com un autòmat finit no determinista.
Nou!!: Teoria de la computabilitat і Màquina de Turing no determinista · Veure més »
Màquina de Turing probabilística
En teoria de la complexitat, s'utilitzen Màquines de Turing probabilística per definir diferents classes de complexitat.
Nou!!: Teoria de la computabilitat і Màquina de Turing probabilística · Veure més »
Màquina oracle
En teoria de la complexitat, una màquina oracle és màquina abstracta utilitzada per estudiar els problemes de decisió.
Nou!!: Teoria de la computabilitat і Màquina oracle · Veure més »
Nombre computable
En matemàtiques i especialment en complexitat computacional un nombre computable és un nombre real que pot ser computat amb una precisió arbitraria mitjançant un algorisme finit i que s'atura.
Nou!!: Teoria de la computabilitat і Nombre computable · Veure més »
Nombre real
En matemàtiques, els nombres reals (\R) informalment es poden concebre com els nombres associats a longituds o qualsevol mena de magnitud física que se suposa que és contínua.
Nou!!: Teoria de la computabilitat і Nombre real · Veure més »
Ordinador
Teclat Un ordinador (del francès ordinateur) o computadora (del llatí computare, calcular) és una màquina electrònica que rep i processa dades per a convertir-les en informació útil.
Nou!!: Teoria de la computabilitat і Ordinador · Veure més »
Ordinador quàntic
IBM Q System One (2019), el primer ordinador quàntic comercial basat en circuits. Un ordinador quàntic és un dispositiu de càlcul que fa ús dels fenòmens específics de la mecànica quàntica, tals com la superposició i l'entrellaçament, per executar operacions sobre dades.
Nou!!: Teoria de la computabilitat і Ordinador quàntic · Veure més »
Problema de decisió
En teoria de la computabilitat i en complexitat computacional, un problema de decisió és una qüestió en algun sistema formal amb una resposta sí o no.
Nou!!: Teoria de la computabilitat і Problema de decisió · Veure més »
Problema de la parada
En teoria de la computabilitat el problema de la parada és un problema de decisió que es pot formular de forma informal: Alan Turing va provar el 1936 que un algorisme general per resoldre el problema de la parada per totes les possibles parelles programa-entrades no pot existir.
Nou!!: Teoria de la computabilitat і Problema de la parada · Veure més »
Teoria de la computació
La teoria de la computació és una ciència, en particular una branca de la matemàtica i de la computació que tracta de quins problemes es poden resoldre en un model de càlcul, mitjançant un algorisme, de quina manera es poden resoldre de manera eficient o en quin grau (per exemple, les solucions aproximades enfront de les precises).
Nou!!: Teoria de la computabilitat і Teoria de la computació · Veure més »
Tesi de Church-Turing
La Tesi de Church-Turing, simplificant, es pot enunciar així: "Tot algorisme o procediment efectiu és Turing-computable".
Nou!!: Teoria de la computabilitat і Tesi de Church-Turing · Veure més »
Turing complet
En la teoria d'ordinadors reals i imaginaris, dels llenguatges de programació i d'altres sistemes lògics, un sistema Turing complet és aquell que té un poder computacional equivalent a la màquina universal de Turing.
Nou!!: Teoria de la computabilitat і Turing complet · Veure més »
Redirigeix aquí:
Computabilitat, Teoria de la recursió.
