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

Bài giảng Lý thuyết tính toán: Bài 13 - Phạm Xuân Cường cung cấp cho học viên các kiến thức về bài toán dừng; máy Turing vạn năng; phương pháp chéo hóa; ngôn ngữ đoán nhận được bởi Turing; ngôn ngữ vạn năng; ngôn ngữ không là Turing-recognizable; . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | LÝ THUYẾT TÍNH TOÁN BÀI 13 Bài toán dừng Phạm Xuân Cường Khoa Công nghệ thông tin cuongpx@ Nội dung bài giảng 1. Bài toán dừng 2. Máy Turing vạn năng 3. Phương pháp chéo hóa 4. Ngôn ngữ đoán nhận được bởi Turing 1 Bài toán dừng Bài toán dừng Một số bài toán có thể giải được bằng thuật toán một số thì không thể Nghiên cứu giới hạn của máy tính ATM M là 1 máy Turing chấp thuận xâu vào w Định lý 1 ATM là không quyết định được 2 Bài toán dừng Trước tiên ta nhận xét là ATM có thể đoán nhận được Máy Turing U sau đoán nhận ATM U quot Trên đầu vào trong đó M là một TM và w là một xâu 1. Mô phỏng M trên xâu đầu vào w 2. Nếu M gặp một trạng thái chấp thuận U chấp thuận ngược lại bác bỏ Nếu M lặp trên w thì U lặp trên ATM được gọi là bài toán dừng 3 Máy Turing vạn năng Máy Turing vạn năng Ngôn ngữ vạn năng Universal Language U trên bộ chữ Σ 0 1 là U w L M 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 A w 0 1 U 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 đó 4 Phương pháp chéo hóa Phương pháp chéo hóa Để chứng minh khả năng không quyết định của bài toán dừng Sử dụng kỹ thuật kiểm tra chéo Georg Cantor 1873 Georg Cantor tập trung vào các bài toán về đo kích thước tập vô hạn Nếu có hai tập vô hạn làm thế nào để biết hai tập có kích thước bằng nhau hay không Georg Cantor đề xuất một giải pháp Hai tập hữu hạn có cùng kích thước nếu có thể ghép cặp các phần tử thuôc tập này với các phần tử thuộc tập kia Có thể so sánh mà không cần sắp xếp và đếm 5 Phương pháp chéo hóa Từ ý tưởng trên ta có thể mở rộng với tập vô hạn Định nghĩa 1 Giả sử có 2 tập A B và một hàm f ánh xạ A B Quan hệ 1-1 f a 6 f b nếu a 6 b Toàn ánh b B a A sao cho f a b Tương đương cả 2 quan hệ 1-1 và toàn ánh 6 Vô hạn đếm được và không đếm được Georg Cantor Hai tập có cùng kích