Da link
a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.
Da link
a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine.
Quindi entrambe le lingue enumerabili in modo ricorsivo e le lingue complete di Turing sono definite in termini di Turing Machines.
-
Quali sono le differenze fondamentali tra enumerabili ricorsivamente lingue e lingue complete di Turing?
Ad esempio, è corretto che
- un linguaggio ricorsivamente enumerabile una serie di input per una macchina di Turing per il riconoscimento, mentre
- una lingua completa di Turing è la lingua fornita da una macchina di Turing o il suo equivalente?
Quindi i due concetti appartengono a due aspetti non correlati delle macchine di Turing?
-
Quali sono le loro relazioni?
Per una lingua,
- l'essere ricorsivamente enumerabile implica il completamento di Turing?
- Il completamento di Turing implica l'enumerazione ricorsiva?
Grazie.