Bài giảng Lý thuyết tính toán: Bài 13 - Phạm Xuân Cường

- BÀI 13: Bài toán dừng.
- Bài toán dừng.
- Máy Turing vạn năng.
- Ngôn ngữ đoán nhận được bởi Turing.
- M là 1 máy Turing chấp thuận xâu vào w}.
- A TM là không quyết định được.
- Trước tiên, ta nhận xét là A TM có thể đoán nhận được.
- Máy Turing U sau đoán nhận A TM.
- A TM được gọi là bài toán dừng.
- Ngôn ngữ vạn năng (Universal Language) U trên bộ chữ Σ = {0,1} là.
- U chứa tất cả các ngôn ngữ Turing đoán nhận được trên bộ chữ Σ = {0,1}.
- Giả sử A là một ngôn ngữ Turing đoán nhận được trên bộ chữ Σ = {0,1}, và M là máy Turing đoán nhận A.
- U là một ngôn ngữ Turing đoán nhận được.
- Máy Turing đoán nhận U được gọi là máy Turing vạn năng.
- Có khả năng mô phỏng bất kỳ máy Turing nào từ bản mô tả của máy đó.
- Để chứng minh khả năng không quyết định của bài toán dừng.
- Georg Cantor tập trung vào các bài toán về đo kích thước tập vô hạn.
- Từ ý tưởng trên ta có thể mở rộng với tập vô hạn Định nghĩa 1.
- Vô hạn đếm được và không đếm được.
- Tập A là đếm được nếu A là hữu hạn hoặc A có kích thước tương đương với N.
- Vô hạn đếm được.
- Tập số thực → Vô hạn không đếm được.
- Ví dụ vô hạn đếm được.
- Ví dụ vô hạn không đếm được.
- Tập số thực R → Vô hạn không đếm được Chứng minh.
- Tập tất cả các chuỗi nhị phân vô hạn là vô hạn không đếm được.
- Ngôn ngữ không là Turing-recognizable.
- Tập tất cả các máy Turing là vô hạn đếm được Hệ quả.
- Tập tất cả ngôn ngữ Turing đoán nhận được là vô hạn đếm được Định lý.
- Tập tất cả các ngôn ngữ là vô hạn không đếm được Hệ quả.
- Tồn tại một số ngôn ngữ không là Turing-recognizable.
- Bài toán dừng là không quyết định được.
- M là máy Turing đoán nhận w}.
- A TM là không quyết định được Chứng minh.
- Giả sử A TM là quyết định được.
- Xây dựng máy Turing D mà H đóng vai trò là thủ tục con.
- Chứng minh (tiếp).
- Thuật toán của máy Turing D như sau:.
- Ngôn ngữ đoán nhận được bởi.
- Thuật ngữ: co-Turing-recognizable là bù của một ngôn ngữ Turing-recognizable.
- Một ngôn ngữ là quyết định được khi và chỉ khi nó vừa là Turing-recognizable và co-Turing-recognizable.
- Chứng minh.
- Nếu A là Turing-recognizable thì A cũng là Turing-recognizable Hệ quả.
- A TM không là Turing-recognizable

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt