TAILIEUCHUNG - 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

• Toán học
• Bài giảng Lý thuyết tính toán
• Lý thuyết tính toán
• Bài toán dừng
• Máy Turing vạn năng
• Phương pháp chéo hóa
• Ngôn ngữ vạn năng
• giáo trình lý thuyết tính toán
• tài liệu về lý thuyết tính toán
• học lý thuyết tính toán
• tự học lý thuyết tính toán
• Tổng quan lý thuyết tính toán
• Khái niệm ngôn ngữ
• Khái niệm văn phạm
• Các phép toán trên ngôn ngữ
• Cơ sở toán học
• Cơ sở thuật toán
• Lý thuyết khoa học máy tính
• Ôtômat hữu hạn
• Văn phạm phi ngữ cảnh
• Quy dẫn
• Bài toán không quyết định được
• Quy dẫn thông qua lịch sử tính toán
• Bài toán PCP
• Quy dẫn ánh xạ
• Ôtômat đẩy xuống
• Mô hình tính toán
• Ngôn ngữ không phi ngữ cảnh
• Ngôn ngữ phi ngữ cảnh
• Định nghĩa giải thuật
• Bài toán của Hilbert
• Luận đề Church Turing
• Ngôn ngữ quyết định được
• Bài toán quyết định được
• Ngôn ngữ chính quy
• Bài giảng Lý thuyết hạch toán kế toán
• Lý thuyết hạch toán kế toán
• Hệ thống phương pháp hạch toán kế toán
• Phương pháp chứng từ
• Phương pháp tính giá
• Phương pháp tổng hợp cân đối
• Quy hoạch tuyến tính
• Lý thuyết quy hoạch tuyến tính
• Bài toán quy hoạch tuyến tính
• Quy hoạch tuyến tính tổng quát
• Quy hoạch tuyến tính chính tắc
• Bài toán vận tải
• Tính chất của ngôn ngữ chính quy
• Ngôn ngữ không chính quy
• Nhận biết ngôn ngữ không chính quy
• Thiết kế ôtômat hữu hạn
• Toán tử chính quy
• Ôtômat hữu hạn không đơn định
• Toán tử chính quy với NFA
• Nondeterministic Finite State Automaton (NFA)
• Biểu thức chính quy
• Ngôn ngữ của biểu thức chính quy
• Toán học cơ sở
• Máy trừu tượng
• Biểu diễn ngôn ngữ
• Cấu trúc rời rạc
• Văn phạm và ô tô mát
• Kiến thức cơ bản về ngôn ngữ
• Phương pháp phân tích từ vựng
• Phân tích cú pháp
• Automat hữu hạn
• Accepter hữu hạn đơn định
• Accepter hữu hạn không đơn định
• Rút gọn số trạng thái
• Văn phạm chính quy
• Quan hệ ngôn ngữ và biểu thức chính quy
• Ngôn ngữ lập trình
• Biến đổi văn phạm
• Dạng chuẩn quan trọng
• Giải thuật thành viên
• Tập hợp
• Đồ thị
• Boolean logic
• Quan hệ tương đương
• Độ dài dẫn xuất
• Bổ đề Bơm (Pumping Lemma)
• Văn phạm nhập nhằng
• Dạng chuẩn tắc Chomsky
• Quy tắc thay thế
• Máy Turing
• Ngôn ngữ của Turing Machine
• Cấu trúc dữ liệu Turing Machine
• Đoán nhận ngôn ngữ
• Các biến thể của máy Turing
• Máy Turing tùy chọn tại chỗ
• Máy Turing bán vô hạn
• Máy Turing đa băng
• Máy Turing không đơn định