Wie kann man das zeigen / beweisen Theoretische Informatik?

Ich habe bis :

hA(n) ist Turing Berechenbar genau dann wenn , eine Turing Maschine existiert die auf Input n eine 1 schreibt falls n element A und ansonsten unendlich läuft. Was Äquivalant dazu ist, dass A semi entscheidbar ist.

also ist die Menge ja gleichmächtig wie die Menge der semi entscheidbaren Sprachen ? oder nicht?

sind die Semi entscheidbaren Sprachen denn abzählbar unendlich ? wenn ja wie beweise ich das wenn nein wo ist mein Fehler ?

Answer 1

[MagicalGrill]

Es gibt insgesamt nur abzählbar viele Turing-berechenbare Funktionen, weil es im Wesentlichen nur abzählbar viele Turing-Maschinen gibt (man kann die einfach durchnummerieren, such z.B. mal nach "Gödelisierung von Turingmaschinen").

Da deine Menge als Teilmenge der Turing-berechenbaren Funktionen somit ebenfalls höchstens abzählbar unendlich sein kann, brauchst du nur noch zeigen, dass tatsächlich unendlich viele Funktionen darin liegen.