Warum stimmt die Vollständigkeit von Turing?

  • Ich verwende einen digitalen Computer, um diese Nachricht zu schreiben. Eine solche Maschine hat eine Eigenschaft, die, wenn Sie darüber nachdenken, tatsächlich bemerkenswert ist: eine Maschine , die bei entsprechender Programmierung alle möglichen Berechnungen .

    Natürlich gehen Rechenmaschinen der einen oder anderen Art bis in die Antike zurück. Menschen haben Maschinen gebaut, die Additionen und Subtraktionen (z. B. Abakus), Multiplikation und Division (z. B. die Rechenschieber) sowie weitere domänenspezifische Maschinen wie Rechner für die Positionen der Planeten durchführen.

    Das Auffällige an einem Computer ist, dass er jede Berechnung ausführen kann. Jede Berechnung überhaupt. Und das alles, ohne die Maschine neu verkabeln zu müssen. Heute nimmt jeder diese Idee als selbstverständlich an, aber wenn Sie aufhören, darüber nachzudenken, ist es erstaunlich, dass ein solches Gerät möglich ist.

    Ich habe zwei eigentliche Fragen < / em>:

    1. Wann hat die Menschheit herausgefunden, dass eine solche Maschine möglich ist? Gab es jemals ernsthafte Zweifel , ob dies möglich ist? Wann war das erledigt? (Wurde es vor oder nach der ersten tatsächlichen Implementierung festgelegt?)

    2. Wie haben Mathematiker bewiesen, dass sie eine Turing-Komplettmaschine sind kann wirklich alles berechnen?

    Das zweite ist fummelig. Jeder Formalismus scheint einige Dinge zu haben, die nicht berechnet werden können. Derzeit ist "berechenbare Funktion" als "alles, was eine Turing-Maschine berechnen kann", definiert. Aber woher wissen wir, dass es keine leistungsfähigere Maschine gibt, die mehr Material berechnen kann? Woher wissen wir, dass Turing-Maschinen die richtige Abstraktion sind?

    23 June 2012
    Raphael
1 answer
  • Es gibt einen Grund, warum sie eine Turing-Maschine genannt wird, und zwar weil Alan Turing sie erfunden hat. Er machte 1936 ein Papier darüber und stellte diese Konzepte fest. Wenn Sie mehr über Turing-Maschinen erfahren möchten, überprüfen Sie das Papier. Es wurde ernsthaft bezweifelt, dass er, bevor er eines entwickelte und baute, das die Enigma knackte, daran glaubte, dass dieses Konzept tatsächlich funktionieren könnte. Die Briten waren jedoch ziemlich verzweifelt und er war ein Genie, deshalb vertrauten sie ihm und es hat sich massiv ausgezahlt.

    Wenn Sie jedoch noch darüber nachdenken, ist das nicht wirklich erstaunlich überhaupt. Lange vor Turing war bekannt, dass sich die gesamte Mathematik auf einige Axiome reduzieren lässt. Alles, was Sie tun müssen, ist, dem Befehlssatz die Fähigkeit zu geben, diese Axiome auszuführen, und los geht's.

    23 June 2012
    Puppy