Logotyp
Unionpedia
Kommunikation
Ladda ned på Google Play
Ny! Ladda ner Unionpedia på din Android™-enhet!
Fri
Snabbare tillgång än webbläsare!
 

Avgörbarhetsproblemet

Index Avgörbarhetsproblemet

Inom matematik och datavetenskap är Avgörbarhetsproblemet eller Entscheidungsproblemet (av tyskans Entscheidung 'beslut') en fråga som ursprungligen formulerades av David Hilbert 1928: Enligt Gödels fullständighetssats för första ordningens logik är en utsaga universellt giltig om och endast om den kan härledas från dess axiom, så avgörbarhetsproblemet kan också ses som frågan om huruvida en utsaga är bevisbar utifrån axiomen eller inte.

29 relationer: Alan Turing, Alfred North Whitehead, Algoritm, Alonzo Church, Beräkningsteori, Bertrand Russell, Church-Turings hypotes, Churchs teorem, Datavetenskap, David Hilbert, Diofantisk ekvation, Första ordningens logik, Formellt språk, Gödels ofullständighetssatser, Gottfried Wilhelm von Leibniz, Hilbertproblemen, Kurt Gödel, Lambdakalkyl, Logisk sanning, Matematik, Programspråk, Räknemaskin, Stephen Toulmin, Stopproblemet, Turingmaskin, Typsystem, Tyska, Wilhelm Ackermann, 1600-talet.

Alan Turing

Sir Alan Mathison Turing (IPA), OBE, FRS, född 23 juni 1912 i Maida Vale, London, död genom förgiftning den 7 juni 1954 i Wilmslow, Cheshire, var en brittisk matematiker, logiker och kryptoanalytiker.

Ny!!: Avgörbarhetsproblemet och Alan Turing · Se mer »

Alfred North Whitehead

Alfred North (A.N.) Whitehead, född 15 februari 1861 i Ramsgate, Kent, död 30 december 1947 i Cambridge, Massachusetts, var en brittisk filosof och matematiker.

Ny!!: Avgörbarhetsproblemet och Alfred North Whitehead · Se mer »

Algoritm

Flödesscheman ger en grafisk representation av algoritmer. sovjetiskt frimärke. En algoritm är, inom matematiken och datavetenskapen, en ändlig uppsättning (mängd) otvetydiga instruktioner som efter exekvering löser ett problem.

Ny!!: Avgörbarhetsproblemet och Algoritm · Se mer »

Alonzo Church

Alonzo Church, född 14 juni 1903 i Washington, D.C., död 11 augusti 1995, var en amerikansk matematiker och logiker, som lämnade fundamentala bidrag till datavetenskapen.

Ny!!: Avgörbarhetsproblemet och Alonzo Church · Se mer »

Beräkningsteori

Beräkningsteori, som är en underdisciplin till matematik och datavetenskap, behandlar analys av problem, indata och algoritmer.

Ny!!: Avgörbarhetsproblemet och Beräkningsteori · Se mer »

Bertrand Russell

Bertrand Arthur William Russell, från 1931 3:e earl Russell, född 18 maj 1872 i Trellech, Monmouthshire, Wales, död 2 februari 1970 i Penrhyndeudraeth, Gwynedd, Wales, var en brittisk filosof, logiker, matematiker, historiker och pacifist.

Ny!!: Avgörbarhetsproblemet och Bertrand Russell · Se mer »

Church-Turings hypotes

Inom matematik och beräkningsteori innebär Church-Turings hypotes påståendet att en matematisk funktion är effektivt beräkningsbar om och endast om den kan beräknas med hjälp av en algoritm på en Turingmaskin, d.v.s. om beräkningarna kan utföras med någon annan godtycklig manuell eller mekanisk metod, så kan de också utföras av en sådan maskin.

Ny!!: Avgörbarhetsproblemet och Church-Turings hypotes · Se mer »

Churchs teorem

Churchs teorem är ett bevis, publicerat av den amerikanske matematikern Alonzo Church 1936, av att en allmän lösning av logikens avgörbarhetsproblem inte existerar.

Ny!!: Avgörbarhetsproblemet och Churchs teorem · Se mer »

Datavetenskap

Datavetenskap bygger på teorin bakom beräkningar, och innefattar även teknikerna som används för att tillämpa denna teori.

Ny!!: Avgörbarhetsproblemet och Datavetenskap · Se mer »

David Hilbert

David Hilbert, född 23 januari 1862 i Königsberg (nuvarande Kaliningrad), död 14 februari 1943 i Göttingen, var en tysk matematiker som var professor i Göttingen 1895-1930.

Ny!!: Avgörbarhetsproblemet och David Hilbert · Se mer »

Diofantisk ekvation

En diofantisk ekvation är en ekvation av en eller flera obekanta variabler där endast heltalslösningar för alla obekanta variabler sökes.

Ny!!: Avgörbarhetsproblemet och Diofantisk ekvation · Se mer »

Första ordningens logik

Första ordningens logik (FOL) är ett formellt deduktivt system som används i matematik, filosofi, lingvistik och datavetenskap.

Ny!!: Avgörbarhetsproblemet och Första ordningens logik · Se mer »

Formellt språk

Ett formellt språk är en mängd ord över ett alfabet Σ.

Ny!!: Avgörbarhetsproblemet och Formellt språk · Se mer »

Gödels ofullständighetssatser

Gödels ofullständighetsteorem är två fundamentala teorem inom den moderna logiken.

Ny!!: Avgörbarhetsproblemet och Gödels ofullständighetssatser · Se mer »

Gottfried Wilhelm von Leibniz

Gottfried Wilhelm von Leibniz, född 1 juli 1646 i Leipzig, död 14 november 1716 i Hannover, var en tysk matematiker, filosof och friherre.

Ny!!: Avgörbarhetsproblemet och Gottfried Wilhelm von Leibniz · Se mer »

Hilbertproblemen

Hilbertproblemen är en lista över 23 då olösta problem inom matematiken som lades fram år 1900 av David Hilbert vid en konferens i Paris.

Ny!!: Avgörbarhetsproblemet och Hilbertproblemen · Se mer »

Kurt Gödel

Kurt Gödel, född 28 april 1906 i Brünn (nu Brno i Tjeckien), död 14 januari 1978 i Princeton, var en österrikisk, senare amerikansk, logiker och matematiker.

Ny!!: Avgörbarhetsproblemet och Kurt Gödel · Se mer »

Lambdakalkyl

Lambdakalkyl (λ-kalkyl) är ett formellt system som skapades för att undersöka funktioner och rekursion.

Ny!!: Avgörbarhetsproblemet och Lambdakalkyl · Se mer »

Logisk sanning

Logisk sanning kallas en sats inom logiken, som är sann för varje tillordning av sanningsvärden till dess satssymboler.

Ny!!: Avgörbarhetsproblemet och Logisk sanning · Se mer »

Matematik

arkivdatum.

Ny!!: Avgörbarhetsproblemet och Matematik · Se mer »

Programspråk

Java. Programmet skriver ut meddelandet "Hello World!". Programspråk, eller programmeringsspråk, är ett formellt språk som en människa använder för att skapa datorprogram.

Ny!!: Avgörbarhetsproblemet och Programspråk · Se mer »

Räknemaskin

Räknemaskin av Facit AB (1954) Ursprunglig ritning för Schikards räkneur (1623). Källa: http://history-computer.com/MechanicalCalculators/Pioneers/Schickard.html F. Seck (Editor) 'Wilhelm Schickard 1592-1635, Astronom, Geograph, Orientalist, Erfinder der Rechenmaschine', Tübingen, 1978. En räknemaskin är en maskin som kan utföra olika sorters räkneoperationer, exempelvis addition, subtraktion, multiplikation och division.

Ny!!: Avgörbarhetsproblemet och Räknemaskin · Se mer »

Stephen Toulmin

Stephen Edelston Toulmin, född 25 mars 1922 i London, död 4 december 2009, var en brittisk filosof verksam i Storbritannien och USA, som främst är inriktad på etik, retorik, och vetenskapsteori.

Ny!!: Avgörbarhetsproblemet och Stephen Toulmin · Se mer »

Stopproblemet

Stopproblemet eller haltproblemet (en The Halting Problem) är ett grundläggande beslutsproblem inom beräkningsbarhetsteorin som informellt kan beskrivas så här: En annan beskrivning av problemet lyder: Alan Turing visade 1936 att en allmän algoritm för att lösa stopproblemet för samtliga (program, indata)-par inte kan existera.

Ny!!: Avgörbarhetsproblemet och Stopproblemet · Se mer »

Turingmaskin

En modell av Turingmaskinen En Turingmaskin är en teoretisk modell för att utföra beräkningar.

Ny!!: Avgörbarhetsproblemet och Turingmaskin · Se mer »

Typsystem

Ett typsystem definierar inom datavetenskapen hur ett programspråk klassificerar värden och uttryck som typer, hur det kan manipulera dessa och hur de kan interagera med varandra.

Ny!!: Avgörbarhetsproblemet och Typsystem · Se mer »

Tyska

Talad tyska Tyska (deutsche Sprache, Deutsch) är ett germanskt språk, talat av omkring 120–150 miljoner människor (varav cirka 95 miljoner har det som modersmål).

Ny!!: Avgörbarhetsproblemet och Tyska · Se mer »

Wilhelm Ackermann

Wilhelm Ackermann, född 29 mars 1896 i Herscheid,, död 24 december 1962 i Lüdenscheid, var en tysk matematiker och logiker.

Ny!!: Avgörbarhetsproblemet och Wilhelm Ackermann · Se mer »

1600-talet

1600-talet var ett århundrade inom den kristna-västerländska tideräkningen, som varade mellan 1 januari 1600 och 31 december 1699.

Ny!!: Avgörbarhetsproblemet och 1600-talet · Se mer »

Omdirigerar här:

Entscheidungsproblemet.

UtgåendeInkommande
Hallå! Vi är på Facebook nu! »