VL-08 Turing-Mächtigkeit

Question 1

Wie ist eine kontextfreie Grammatik (CFG) definiert?

Answer 1

Eine CFG G ist ein Quadrupel (N, Σ, P, S), mit
- N = Menge der Non-Terminal Symbole
- Σ = Terminal Alphabet
- P = Menge der Regeln
- S = Startsymbol aus N

Question 2

Welche Aussage lässt sich über die Entscheidbarkeit von CFGs machen?

Answer 2

Es ist unentscheidbar ob der Schnitt von zwei CFGs leer ist, weil dies das PKP lösen würde.

Question 3

Wann ist ein Rechenmodell Turning-mächtig?

Answer 3

Ein Rechenmodell ist turning-mächtig wenn jede Funktion die von einer TM berechnet werden kann auch von diesem Rechner berechnet werden kann

Question 4

Welche bekannte Rechenmodelle sind turing-mächtig?

Answer 4

• RAM/ Mini-Ram
• Alle gängigen Programmiersprachen (Java, Python, C etc)
• Lambda Calculus
• Game of life