lý thuyết tính toán

Tham khảo tài liệu lý thuyết tính toán, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
lý thuyết tính toán ĐẠI HỌC ĐÀ NẴNG T R ƯỜ NG Đ Ạ I H Ọ C BÁCH KHOAKHOA CÔNG NGHỆ THÔNG TIN LÝ THUYẾT TÍNH TOÁN PGS.TS. PHAN HUY KHÁNH ĐÀ NẴNG 1999 2 Lý thuyết tính toán III.7. Một số máy Turing thông dụng ..................................................................40 III.6.1. Sao chép .....................................................................................................40 MỤC LỤC III.6.2. Kiểm tra bằng nhau ....................................................................................41 III.6.3. Liệt kê các câu, các cặp câu và dãy các câu ...............................................41 III.6.4. Các hàm chiếu ngược (antiprojection function) .........................................42 III.6.5. Các hàm giao hoán .....................................................................................42CHƯƠNG 1 NHẬP MÔN LÝ THUYẾT TÍNH TOÁN ........................................... 1 III.7. Các hàm T-tính được phức tạp hơn............................................................42 I. CÁC ĐốI TƯợNG ĐƯợC Xử LÝ TRONG TIN HọC ......................................................... 1 III.8. Nhận xét......................................................................................................43 II. CÁC MÁY (MACHINES)........................................................................................ 2 IV. CÁC BIếN THế KHÁC CủA MÔ HÌNH MÁY TURING ..............................................46 II.1. Khía cạnh chức năng (functional look)........................................................ 2 IV.1. Mô phỏng một máy Turing bởi một máy khác............................................46 II.2. Khía cạnh cấu trúc (structural look)............................................................ 3 IV.2. Các biến thể của máy Turing .....................................................................48 III. MÔ HÌNH TÍNH TOÁN .......................................................................................... 4 IV.2.1. Máy Turing có k băng ................................................................................48 IV. ĐịNH NGHĨA BÀI TOÁN........................................................................................ 5 Các máy off−line và các máy có băng ra ...................................................49 IV.2.2. IV.2.3. Các máy Turing không đơn định................................................................49CHƯƠNG 2 MÔ HÌNH CÁC MÁY RAM ............................................................... 9 IV.2.4. Thu gọn một bảng chữ còn ba ký tự ...........................................................50 IV.2.5. Rút gọn một bảng chữ còn hai ký tự ..........................................................52 I. CÁC MÁY RAM.......................................................................... ...