Θεωρία Υπολογισμού [open] (321-6701)

Άσκηση αυτοαξιολόγησης - Ενότητα 6η (Η θέση των Church-Turing. Μη-υπολογισιμότητα, το πρόβλημα του τερματισμού)

Question 1 (Multiple Choice (Single Answer) — 10 grades)

Κάθε αλγόριθμος μπορεί να υλοποιηθεί από:

a) ένα πεπερασμένο αυτόματο

b) μια μηχανή Turing

c) ένα πεπερασμένο αυτόματο στοίβας

Question 2 (Multiple Choice (Single Answer) — 10 grades)

Ένα σύνολο είναι αριθμήσιμο αν:

a) είναι διατεταγμένο

b) είναι άπειρο

c) έχει ίδιο πληθαρίθμο με τους φυσικούς αριθμούς Ν, δλδ τα στοιχεία του μπορούν να αντιστοιχηθούν "1-1" και επί με το Ν

Question 3 (Multiple Choice (Single Answer) — 10 grades)

Το σύνολο όλων των μηχανών Turing είναι:

a) αριθμήσιμο

b) μη αριθμήσιμο

c) ίδιο πληθαρίθμου με τους φυσικούς αριθμούς

Question 4 (Multiple Choice (Single Answer) — 10 grades)

Το σύνολο όλων των αναγνωρίσιμων γλωσσών είναι:

a) αριθμήσιμο

b) μη αριθμήσιμο

c) ίδιο πληθαρίθμου με τους φυσικούς αριθμούς

Question 5 (Multiple Choice (Single Answer) — 10 grades)

Το σύνολο όλων των γλωσσών είναι:

a) αριθμήσιμο

b) μη αριθμήσιμο

c) ίδιο πληθαρίθμου με τους φυσικούς αριθμούς

Question 6 (Multiple Choice (Single Answer) — 10 grades)

Κάθε αποφασίσιμη γλώσσα μπορεί να αποφασιστεί από:

a) ένα πεπερασμένο αυτόματο

b) μια μηχανή Turing

c) ένα πεπερασμένο αυτόματο στοίβας

Question 7 (Multiple Choice (Single Answer) — 20 grades)

Η πρώτη απόδειξη μη επιλυσιμότητας έγινε με την τεχνική:

a) της αναγωγής

b) του Λήμματος Άντλησης

c) της Διαγωνοποίησης

Question 8 (Multiple Choice (Single Answer) — 20 grades)

Αν έχουμε μια μη επιλύσιμη γλώσσα Α, μπορούμε ν.δ.ο. μια άλλη γλώσσα Β είναι μη επιλύσιμη με την τεχνική της :

a) της αναγωγής

b) του Λήμματος Άντλησης

c) της Διαγωνοποίησης

Θεωρία Υπολογισμού [open] (321-6701)

Άσκηση αυτοαξιολόγησης - Ενότητα 6η (Η θέση των Church-Turing. Μη-υπολογισιμότητα, το πρόβλημα του τερματισμού)

Question 1 (Multiple Choice (Single Answer) — 10 grades)

Κάθε αλγόριθμος μπορεί να υλοποιηθεί από:

Question 2 (Multiple Choice (Single Answer) — 10 grades)

Ένα σύνολο είναι αριθμήσιμο αν:

Question 3 (Multiple Choice (Single Answer) — 10 grades)

Το σύνολο όλων των μηχανών Turing είναι:

Question 4 (Multiple Choice (Single Answer) — 10 grades)

Το σύνολο όλων των αναγνωρίσιμων γλωσσών είναι:

Question 5 (Multiple Choice (Single Answer) — 10 grades)

Το σύνολο όλων των γλωσσών είναι:

Question 6 (Multiple Choice (Single Answer) — 10 grades)

Κάθε αποφασίσιμη γλώσσα μπορεί να αποφασιστεί από:

Question 7 (Multiple Choice (Single Answer) — 20 grades)

Η πρώτη απόδειξη μη επιλυσιμότητας έγινε με την τεχνική:

Question 8 (Multiple Choice (Single Answer) — 20 grades)

Αν έχουμε μια μη επιλύσιμη γλώσσα Α, μπορούμε ν.δ.ο. μια άλλη γλώσσα Β είναι μη επιλύσιμη με την τεχνική της :

Course Options