- BÀI 14: Quy dẫn. - Các 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ạ. - Quy dẫn là một kỹ thuật chứng minh sự không quyết định được của một ngôn ngữ. - Một quy dẫn là cách chuyển 1 bài toán (khó) thành bài toán khác (dễ hơn, có thể giải được). - Có thể sử dụng lời giải của bài toán dễ để áp dụng cho bài toán khó. - Quy dẫn thường hay xuất hiện trong các bài toán về toán học. - Bài toán tìm đường đi trong một thành phố mới đến (khó. - Bài toán tìm bản đồ của thành phố đó (từ bản đồ → đường đi. - Bài toán tính diện tích hình chữ nhật → Bài toán đo chiều dài,. - Quy dẫn: đưa một bài toán khó về một bài toán dễ hơn. - Nếu bài toán khó là không thể giải được → Bài toán dễ phải chắc chắn là không giải được. - Bài toán A: Sống mãi mãi - Bài toán B: Trẻ mãi. - Nếu ta tìm được lời giải cho bài toán B → Có thể giải được bài toán A. - Nhưng bài toán A là không thể xảy ra → Bài toán B cũng không thể xảy ra. - Tương tự trong LTTT, bài toán A là không quyết định được. - bài toán B cũng không quyết định được. - Ta biết rằng A TM là không quyết định được. - Xét bài toán P, P có quyết định được hay không?. - Định lý 1. - P là không quyết định được. - Chứng minh. - Giả sử P là quyết định được. - Quy dẫn A TM (Bài toán khó) về P (Bài toán dễ hơn). - Sử dụng thuật toán quyết định P để giải A TM. - Nhưng ta biết rằng không tồn tại bộ quyết định cho A TM. - Mâu thuẫn → P là không quyết định được. - Bài toán dừng: Kiểm tra xem một máy Turing có dừng trên một đầu vào w đã cho hay không. - M là một máy Turing và M dừng với đầu vào w}. - Vậy HALT TM là quyết định được hay không. - Bài toán dừng. - Định lý 2. - HALT TM là không quyết định được. - Giả sử HALT TM là quyết định được. - Quy dẫn A TM về HALT TM → A TM quyết định được. - Bài toán dừng (2). - Chứng minh (Chi tiết). - Giả sử TM R quyết định HALT TM → Xây dựng TM S quyết định A TM như sau:. - S với đầu vào là <M, w>. - Chạy TM R trên đầu vào <M, w>. - Rõ ràng, R quyết định HALT TM → S cũng phải quyết định A TM. - A TM là không quyết định được → HALT TM cũng không quyết định được. - Bài toán kiểm tra rỗng. - Định lý 3. - M là một máy Turing và L(M)=Ø} là không quyết định được. - Giả sử máy Turing R quyết định E TM → Sử dụng R để xây dựng máy Turing S quyết định A TM. - S sẽ hoạt động như thế nào trên đầu vào <M, w>. - Nếu R chấp thuận xâu đầu vào <M>. - Ø → Bác bỏ w. - Nếu R bác bỏ xâu đầu vào <M>. - M 1 trên xâu đầu vào x:. - Nếu x = w thì chạy M trên đầu vào w và M 1 chấp thuận nếu M chấp thuận, ngược lại bác bỏ. - Máy Turing S quyết định A TM : S= Trên đầu vào <M, w>:. - Chạy R trên xâu đầu vào M 1. - Một số bài toán khác. - Định lý 4. - M là một máy Turing và L(M) là ngôn ngữ chính quy} là không quyết định được. - Định lý 5. - là không quyết định được. - Thường dùng để chứng minh bài toán kiểm tra sự tồn tại của một vấn đề. - Ôtômat có biên tuyến tính (Linear Bounded Automaton - LBA) là một kiểu máy Turing có băng nhớ bằng đúng chuỗi đầu vào. - Đầu đọc không thể di chuyển ra ngoài đầu bên trái và phải của đoạn băng nhớ chứa chuỗi đầu vào. - Các bộ quyết định cho A DFA , A CFG , E DFA , E CFG đều là LBA. - Mọi ngôn ngữ phi ngữ cảnh CFL đều có thể quyết định được bởi một LBA. - Bài toán quyết định của LBA. - Định lý 6. - M là một LBA chấp thuận w} là quyết định được. - L = Trên đầu vào <M, w>:. - bác bỏ.. - Bài toán kiểm tra rỗng của LBA Định lý 7. - Ø} là không quyết định được. - Ý Tưởng: Quy dẫn về A TM , nếu E LBA quyết định được thì A TM. - cũng quyết định được. - Nhận đầu vào là lịch sử tính toán của w trên M:. - Xây dựng máy Turing S quyết định A TM như sau:. - S = Trên đầu vào <M, w>. - Chạy R trên đầu vào <B>. - Định lý 8. - ALL CFG là không quyết định được. - Bài toán PCP: Mô tả dưới dạng một trò chơi Domino. - Bài toán PCP là bài toán quyết định xem một tập các domino có đối xứng không. - Bài toán này không giải được bằng thuật toán. - Mô tả bài toán dưới dạng ngôn ngữ - Một thể hiện của PCP là một tập. - Ý tưởng: Quy dẫn về A TM thông qua các lịch sử tính toán chấp thuận → Chứng minh rằng ∀ TM M và đầu vào w ta có thể xây dựng một thể hiện P có một đối xứng là 1 lịch sử tính toán chấp thuận của M trên w. - Gọi R là máy Turing quyết định PCP và xây dựng S quyết định A TM. - Định lý 9. - Nếu A ≤ m B và B quyết định được thì A cũng quyết định được Chứng minh. - Gọi M là bộ quyết định cho B, f là một quy dẫn từ A sang B. - Bộ quyết định N cho A được mô tả như sau:. - N = Trên đầu vào w:. - Chạy M trên đầu vào f(w) và đầu ra chính là đầu ra của M. - Nếu A ≤ m B và A không quyết định được thì B cũng không quyết định được. - F = Trên đầu vào <M, w>. - M 1 trên đầu vào bất kỳ: Bác bỏ. - M 2 trên đầu vào bất kỳ - Chạy M trên w. - Để chứng minh EQ TM không nhận biết được bởi TM ta quy dẫn A TM về EQ TM . - G = Trên đầu vào <M, w>. - M 1 trên đầu vào bất kỳ: Chấp thuận
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt