Wie gibt man die Sprache von der grammatik an , ich komme irgendwie nicht weiter und kann mir jemand sagen wie das geht ?

In der Realität will man doch eh immer nur Kryptocoins von A nach B senden. Was bringt es also, dass z.B. Ethereum turingvollständig ist?

Ich würde gern wissen, wie man diese Aussage "Wenn X semi-entscheidbar ist und Y entscheidbar ist, dann ist X \ Y semi-entscheidbar" zeigen kann.

Kann jmd bitte einmal beweisen, der gut auf Entscheidbarkeit ist?

Hallo! Ich bräuchte Hilfe bei dieser Aufgabe:

"Sei L = {<M> | M akzeptiert, wenn die Eingabelänge durch 5 teilbar ist}. Zeigen Sie durch Reduktion, dass L unentscheidbar ist."

Ich weiß, dass man jetzt einen Widerspruchsbeweis aufstellen sollte, indem man eine bekanntlich unentscheidbare Sprache U auf L reduziert. Dazu nimmt man an, dass L entscheidbar wäre und dafür somit ein Entscheider existiert. Daraus baut man dann eine Entscheider-TM T für diese unentscheidbare Sprache U, was einen Widerspruch erzeugt.

Welche unentscheidbare Sprache sollte man hier bestenfalls benutzen (vielleicht das Wortproblem ATM) und wie würde dann die TM T im Ansatz funktionieren?

Danke!

Menschen können sich die Natur durch Modelle und Mathematik, nachvollziehbar erklären und berechnen. Aber könnte es nicht eine Lebensform versuchen auf anderen Wegen die Natur und das Universum zu erklären und exakte Ergebnisse liefern über Gegenwart, Vergangenheit und Zukunft?

Ist das was wir messen und berechnen immer messbar und von jeder Lebensform erkennbar?

Hallo!

Die Verteilung der natürlichen Primzahlen scheint auf den ersten Blick zufällig. Allerdings gibt es ja eine Primzahlzählfunktion π(x), weswegen die Annordnung der Primzahlen nicht dem Zufall überlassen sein kann. Jedoch gibt es bis jetzt noch keinen endgültigen Zusammenhang der Abstände aller Primzahlen. Denkt ihr die Primzahlen folgen einem Muster? Oder denkt ihr, sie sind absolut unberechenbar verteilt? Ich denke, dass sie einem gewissen System folgen, da ich nicht an Zufall glaube. Ich denke, alles in der Mathematik, Physik und jeder Ablauf in der Natur ist genau festgelegt und anhand von genügend Informationen vorhersagbar.

Vielen Dank! :)

Hallo,

wir haben momentan im Informatik Unterricht einen Exkurs zur Berechenbarkeit angefangen. Dazu sollen wir nun selbstständig die Aufgaben 1 und 2 auf der Seite bearbeiten. Bei der Aufgabe 2 habe ich keine Probleme, da diese sehr gut lösbar ist. Jedoch komme ich bei Aufgabe 1 nicht weiter, das alleine schon weil ich die Methode nicht verstehe. Habe mir dazu einige Texte usw durchgelesen aber ich komm mit der Methode eif nicht weiter, sodass die Aufgabe dann natürlich nicht lösbar ist. Könnte mir da jemand weiterhelfen?

Hallo, ich verstehe die Konzept auf Reduktion, und auch Turing machine. aber ich weiss nich wie man mit so Aufgaben umgehen muss.