Bài giảng Khoa học máy tính - Chương 2: Giải thuật

Chương 2: GIẢI THUẬT Nội Dung 1. Định nghĩa giải thuật . 2. Ví dụ về giải thuật. 3. Đặc tả giải thuật. 4. Phân tích giải thuật. 5. Giải thuật là công nghệ. 6. Mô hình hình thức tính toán. 2 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Định Nghĩa Giải Thuật • Định nghĩa giải thuật: Giải thuật là cách thức để giải quyết một tập các vấn đề. • Thuật ngữ “giải thuật” cũng áp dụng cho bất kỳ cách thức nào để giải quyết một vấn đề cụ thể. Cho ví dụ, các bước để thay phanh xe cũng được gọi là giải thuật. • Ví dụ: Tìm ước số chung lớn nhất. • Trong toán học, một giải thuật nổi tiếng và hữu dụng là giải thuật Euclid để tìm ước số chung lớn nhất (GCD) của hai số nguyên. Ông đã đưa ra giải thuật này vào khoảng 300 năm trước công nguyên. • Không có giải thuật Euclid, chúng ta tìm 3 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ví Dụ Về Giải Thuật GCD(372, 84) như thế nào? Phải phân tích hai số nguyên thành các thừa số nguyên tố và tìm thừa số chung lớn nhất. • Nếu các số nguyên này lớn, việc phân tích thành các thừa số trở nên khó khăn và tốn nhiều thời gian. Euclid đã tìm ra giải thuật một cách có hệ thống và nhanh chóng giảm kích thước của vấn đề, bằng cách thay giá trị ban đầu của hai số nguyên với giá trị nhỏ hơn cho đến khi một trong hai số bằng 0. Lúc này, GCD của hai số chính là giá trị của số còn lại. • Sau đây là giải thuật Euclid để tìm GCD của 4 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ví Dụ Về Giải Thuật hai số nguyên A và B: Repeat: Nếu B = 0, GCD(A, B) = A Ngược lại: Thay R bằng A modulo B Thay A bằng B Thay B bằng R • Cho ví dụ, để tìm GCD của 372 và 84: - Tìm GCD(84, 36) vì 372 % 84 = 36 - Tìm GCD(36, 12) vì 84 % 36 = 12 - Tìm GCD(12, 0) vì 36 % 12 = 0 - Vậy GCD(372, 84) = 12 5 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ví Dụ Về Giải Thuật • Như vậy, giải thuật là một chuỗi các phép toán thao tác trên tập giá trị nhập và sinh ra kết quả trong khoảng thời gian hữu hạn. Trong ví dụ trên, tập giá trị nhập là 2 số nguyên. Kết quả là ước số chung lớn nhất của hai số đó. • Có nhiều cách để giải quyết một lớp các vấn đề. Câu hỏi đặt ra là giải thuật nào tốt nhất? Thông thường, các nhà khoa học máy tính sử dụng các kỹ thuật để phân tích, đánh giá và so sánh hiệu quả giữa các giải thuật. 6 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Đặc Tả Giải Thuật • Đặc tả giải thuật (representing algorithm): Trong ngành khoa học máy tính, giải thuật thường được đặc tả bằng mã giả (pseudocode). Mã giả đủ để cho một ngôn ngữ lập trình có thể thể hiện các tác vụ mà máy tính phải thực hiện trong giải thuật. • Mã giả cũng độc lập với bất kỳ ngôn ngữ lập trình nào. Nó thể hiện chi tiết cú pháp và làm cho người lập trình dễ dàng đặc tả các thao tác cốt lõi của một giải thuật. • Không có một mẫu chuẩn nào cho mã giả. Các nhà khoa học máy tính sử dụng mã giả của riêng mình để đặc tả một giải thuật. Ví dụ sau là một kiểu mã giả đặc tả giải thuật GCD: 7 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Đặc Tả Giải Thuật GCD(a, b) While b != 0 { r ← a mod b a ← b b ← r } return a - Tên hàm và đối số - Trong khi b khác 0 - Bắt đầu thân vòng lặp - Gán r = a modulo b - Gán a = giá trị ban đầu của b - Gán b = r - Kết thúc thân vòng lặp - Khi b = 0, kết quả trả về là a • Để minh hoạ thế nào là hiệu quả khác nhau giữa các giải thuật, chúng ta sẽ thảo luận về sự đa dạng của các giải thuật mà các nhà khoa học máy tính đã đưa ra để giải quyết các vấn đề phổ biến trong tính toán. Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng 8 Đặc Tả Giải Thuật • Tìm kiếm tuần tự (sequential search): Giả sử chúng ta có danh sách của các sinh viên trong một lớp học, yêu cầu là hãy tìm tên của sinh viên Debbie Drawe. Giải thuật tìm kiếm tuần tự chỉ đơn giản là so sánh mỗi tên trong danh sách với tên cần tìm. Quá trình tìm kiếm kết thúc khi tên được tìm thấy hoặc khi giải thuật đã tìm hết tất cả các tên trong danh sách. • Sau đây là mã giả của giải thuật tìm kiếm tuần tự: 9 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Đặc Tả Giải Thuật Sequential_Search(listNames, name) length ← length of listNames matchFound ← false index ← 1 while matchFound = false AND index <= length { if listNames[index] = name then matchFound ← true index ← index + 1 } return matchFound end 10 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật • Phân tích giải thuật (analyzing algorithm): Nếu chúng ta biết chiều dài của mỗi câu lệnh và có bao nhiêu tên trong danh sách, chúng ta có thể tính được thời gian để thực thi giải thuật. • Tuy nhiên, thường thì chúng ta không biết giải thuật giải quyết vấn đề trong bao lâu và thời gian cần giải quyết vấn đề sẽ thay đổi theo độ lớn của vấn đề. • Giải thuật tìm kiếm tuần tự sẽ cần thời gian lâu hơn nếu số lần so sánh nhiều hơn. Những lệnh khác của giải thuật chỉ thực thi 1 lần, nhưng những lệnh trong vòng lặp sẽ 11 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Phân Tích Giải Thuật thực thi nhiều lần miễn là điều kiện lặp còn đúng. • Nếu tên cần tìm cần tìm nằm giữa danh sách thì giải thuật sẽ chỉ tìm một nửa danh sách. Nhưng nếu tên cần tìm ở cuối hoặc không có trong danh sách thì giải thuật sẽ phải tìm tất cả các tên trong danh sách. • Thời gian thực thi của giải thuật tìm kiếm tuần tự sẽ tăng tỷ lệ theo kích thước của danh sách. • Chúng ta nói rằng “bậc tăng” của giải thuật tìm kiếm tuần tự là n, ký hiệu là T(n). Chúng ta cũng nói rằng một giải thuật mà bậc tăng của nó giới hạn trong một yếu tố không đổi 12 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Phân Tích Giải Thuật nào đó có theta của n, ký hiệu Θ(n). Lưu ý: T(n) là hàm theta của g(n): T(n) = Θ(g(n)) nếu ∃ các hằng số dương c1, c2, n0 sao cho với mọi n >= n0: c1g(n) <= T(n) <= c2g(n) 1. Giải thuật tìm kiếm tuần tự ở trên có Θ(n). Bởi vì, trong trường hợp trung bình và xấu nhất, giải thuật thực hiện chậm tỷ lệ với chiều dài n của danh sách. 2. Sắp xếp bằng phương pháp chèn trực tiếp (insertion sort) - thời gian thực thi T(n) = Θ(n2): 13 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật Insertion_Sort(numList) length ← length of numList numIndex ← 2 while(numIndex <= length) { newNum ← numList[numIndex] sortedIndex ← numIndex - 1 while newNum 0 { numList[sortedIndex + 1] ← numList[sortedIndex] sortedIndex ← sortedIndex - 1 } numList[sortedIndex + 1] = newNum numIndex ← numIndex + 1 } end 14 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Phân Tích Giải Thuật • Để phân tích thời gian thực thi của giải thuật sắp xếp bằng phương pháp chèn trực tiếp, đầu tiên chúng ta lưu ý là thời gian thực thi tỷ lệ với số phần tử cần sắp xếp n. Ngoài ra, mỗi phần tử đang xét phải được so sánh một hay nhiều lần với các phần tử đã được sắp. Trong trường hợp tốt nhất, danh sách cần sắp xếp đã có thứ tự rồi, khi này mỗi phần tử chỉ so sánh một lần, vì thế trường hợp tốt nhất của giải thuật là Θ(n). • Trong trường hợp xấu nhất, danh sách cần sắp xếp có thứ tự ngược, khi này mỗi phần tử đang xét sẽ so sánh với tất cả phần tử đã 15 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật được sắp. Phần tử thứ 2 so sánh với phần tử đầu, phần tử thứ 3 so sánh với phần tử thứ 2 và phần tử đầu, Ví dụ danh sách có 4 phần tử có thứ tự ngược, số lần so sánh sẽ là 6. Nói chung, số lần so sánh trong trường hợp xấu nhất của giải thuật này là 𝑛𝑛 𝑛𝑛 + 12 − 𝑛𝑛 = 𝑛𝑛2 − 𝑛𝑛2 • Khi n lớn thì n2 lớn hơn rất nhiều so với n, vì vậy thời gian thực thi của giải thuật trong trường hợp này là T(n) = Θ(n2). • Trong trường hợp trung bình, mỗi phần tử đang xét sẽ so sánh với một nửa phần tử đã 16 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật được sắp. Vì vậy, thời gian thực thi của giải thuật trong trường hợp này cũng là T(n) = Θ(n2). 3. Sắp xếp bằng phương pháp trộn (merge sort) - thời gian thực thi T(n) = Θ(n log2n): merge(listA, listB) index ← 1 while listA is not empty AND listB is not empty if listA[1] < listB[1] sortedList[index] ← listA[1] discard listA[1] 17 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật else sortedList[index] ← listB[1] discard listB[1] index ← index + 1 while listA is not empty sortedList[index] ← listA[1] discard listA[1] index ← index + 1 while listB is not empty sortedList[index] ← listB[1] discard listB[1] index ← index + 1 return sortedList 18 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật • Trong hàm merge(), các phần tử được di chuyển từ một trong hai danh sách ban đầu là listA và listB vào danh sách kết quả sortedList. Trong đó, tổng số phần tử di chuyển bằng với tổng số phần tử của hai danh sách ban đầu. Vì vậy, thời gian thực thi của hàm merge() là Θ(nA + nB), với nA + nB là tổng số phần tử của hai danh sách. • Giải thuật sắp xếp bằng phương pháp trộn sẽ sử dụng hàm merge() ở trên để trộn hai danh sách có thứ tự thành danh sách mới cũng có thứ tự: 19 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật merge_sort(numList) length ← length of numList if length > 1 listA ← first half of numList listB ← second half of numList resultA ← merge_sort(listA) resultB ← merge_sort(listB) sortedList ← merge(resultA, resultB) return sortedList else return numList end 20 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật • Bài tập tại lớp: Hãy lấy ví dụ thực thi giải thuật sắp xếp trộn bằng lời gọi hàm merge_sort() với danh sách sau: numList = {1, 6, 4, 2}. • Tổng thời gian thực thi T(n) của giải thuật sắp xếp trộn gồm thời gian gọi đệ qui của hai nửa danh sách và thời gian kết hợp (trộn) các kết quả: T(n) = 2T(n/2) + merge • Như chúng ta đã biết, thời gian thực thi hàm merge() là nA + nB = n, nên: T(n) = 2T(n/2) + n 21 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật • Từ công thức trên, chúng ta xây dựng hệ thức truy hồi sau: • Giải hệ thức truy hồi trên, viết lại: T(n) = n + 2T(n/2) = n + 2[n/2 + 2T(n/4)] = n + n + 4T(n/4) = n + n + 4[n/4 + 2T(n/8)] = n + n + n + 8T(n/8) = 3n + 23T(n/23) = 22 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật Ở bước thứ i, ta có: T(n) = in + 2iT(n/2i) Quá trình tiếp tục cho đến khi gặp T(1). Tức là n/2i = 1 → n = 2i → i = log2n. Khi này: T(n) = nlog2n + 𝟐𝟐𝒍𝒍𝒍𝒍𝒍𝒍𝟐𝟐𝒏𝒏T(1) = nlog2n + nT(1) = nlog2n + nΘ(1) = nlog2n + Θ(n) = Θ(nlog2n + n) = Θ(max(nlog2n + n)) = Θ(nlog2n) 23 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật 4. Tìm kiếm nhị phân (binary search) - thời gian thực thi T(n) = Θ(log2n): • Trước đây, chúng ta đã xét giải thuật tìm kiếm tuần tự, độ phức tạp của nó là Θ(n). Nếu danh sách tìm kiếm đã có thứ tự, sử dụng giải thuật tìm kiếm nhị phân sẽ hiệu quả hơn. • Thời gian tìm kiếm của giải thuật tìm kiếm nhị phân là log2n. Nếu danh sách có 1.000.000 phần tử thì số lần tìm kiếm không quá 20 lần, trong khi giải thuật tìm kiếm tuần tự có số lần tìm kiếm trung bình là 500.000 lần. 24 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật • Sau đây là mã giả của giải thuật tìm kiếm nhị phân: BinarySearch(list, searchItem) begin ← 1 end ← length of list matchFound ← false while matchFound = false AND begin <= end midpoint ← (begin + end) / 2 if list[midpoint] = searchItem matchFound = true else if searchItem < list[midpoint] 25 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật end ← midpoint - 1 else begin ← midpoint + 1 return matchFound • Trong mỗi vòng lặp, giải thuật tìm kiếm nhị phân giảm một nửa kích thước danh sách. Vì vậy, nếu tìm thấy hay không tìm thấy phần tử trong danh sách thì số lần lặp tối đa là log2n. Do đó, thời gian thực thi của giải thuật này là T(n) = Θ(log2n). 26 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Giải Thuật Là Công Nghệ • Nhiều người cho rằng tốc độ phần cứng máy tính như là sự đo lường về kỹ thuật. Nhưng các giải thuật đã xét trước đây và hiệu quả thực thi của nó, cho thấy rằng một giải thuật tốt trên máy tính chậm hơn là một giải thuật chậm trên máy tính nhanh. • Giả sử chúng ta cần sắp thứ tự 1.000.000 (106) phần tử. Hoặc là chúng ta chọn máy tính đang sử dụng với giải thuật sắp xếp trộn hoặc là mua máy tính mới nhanh hơn 10 lần nhưng sử dụng giải thuật sắp xếp chèn. • Giải thuật chèn trên máy tính mới sẽ cần 27 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Giải Thuật Là Công Nghệ (106)2 chu kỳ, trong khi giải thuật trộn cần 106(log2106) = 106(20) = 20.000.000 chu kỳ. Nếu cần 20 giây để thực thi giải thuật trộn trên máy tính cũ thì sẽ cần đến 27 giờ để thực thi giải thuật chèn trên máy tính mới. 28 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán • Lý thuyết máy tính được cải tiến bởi mô hình hình thức tính toán bằng toán học. • Mô hình có tính thuyết phục nhất được đưa ra vào năm 1936 bởi nhà toán học người Anh - Alan Turing. • Khái niệm toán học của mô hình tính toán Turing được gọi là máy Turing (Turing machine) hay TM. • Một máy Turing thường được mô tả như là một máy đọc dải băng (tape): - Dải băng được chia thành các ô chứa các ký hiệu (symbol) và các khoảng trống (blank) và có thể dài vô hạn. 29 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán - Máy sẽ đọc một ký hiệu ở mỗi thời điểm, ký hiệu được đặt phía dưới “đầu đọc/ghi” của máy. - Máy cũng có thể xoá ký hiệu, ghi ký hiệu mới và có thể di chuyển đầu đọc/ghi một ô sang trái hay sang phải trên dải băng (hoặc dải băng di chuyển). - Tại mỗi thời điểm, máy luôn ở một trong một số trạng thái hữu hạn, khi đọc một ký hiệu có thể làm cho trạng thái của máy thay đổi. - Một trạng thái đặc biệt là trạng thái dừng (halting state), đây là trạng thái kết thúc. 30 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán - Khi máy bắt đầu, trạng thái của nó là 1, lúc này máy sẽ ở bên cực trái của dải băng và dải băng sẽ được mở rộng vô hạn về bên phải. • Một máy Turing cụ thể sẽ có một tập các lệnh. Mỗi lệnh gồm một bộ 5 giá trị: 1. Trạng thái hiện tại. 2. Ký hiệu hiện tại đang đọc. 3. Ký hiệu để thay thế ký hiệu hiện tại. 4. Trạng thái kế tiếp. 5. Hướng để di chuyển đầu đọc (Right (phải), Left (trái), Stationary (đứng yên)) 31 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán • Ví dụ 1: Giả sử máy Turing gồm 3 lệnh (Δ nghĩa là trống): 1.(1, 0, 1, 1, Right) 2.(1, 1, 0, 1, Right) 3.(1, Δ, Δ, halt, Stationary) • Lệnh thứ nhất: nếu ký hiệu đang đọc là 0, thay nó bằng 1 và chuyển sang phải dải băng. • Lệnh thứ hai: nếu ký hiệu đang đọc là 1, thay nó bằng 0 và chuyển sang phải dải băng. • Lệnh thứ ba: nếu ký hiệu đang đọc là trống, dừng máy không di chuyển. 32 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán • Giả sử dải băng dùng cho máy Turing ở trên chứa các ký hiệu sau: 1 1 0 1 0 1 0 0 Δ Δ Δ... • Bắt đầu ở trạng thái 1, máy ở cực trái của dải băng, máy đọc ký hiệu 1. Lệnh 2 được sử dụng, làm cho 1 được thay bằng 0, máy vẫn ở trạng thái 1 và di chuyển 1 ô sang phải dải băng. • Kế đến, máy đọc ký hiệu 1 kế tiếp. Lệnh 2 được sử dụng lần nữa, vì thế ký hiệu 1 thứ hai được thay bằng 0, máy vẫn ở trạng thái 1 và di chuyển sang phải. • Khi máy đọc ký hiệu 0, lệnh 1 được sử dụng, 33 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán lệnh này làm cho 0 được thay bằng 1, máy vẫn ở trạng thái 1 và di chuyển sang phải.. • Cuối cùng, máy đọc ký hiệu trống, lệnh 3 được sử dụng và máy sẽ dừng. • Bài tập tại lớp: a) Cho biết công dụng của máy Turing ở trên. b) Kết quả được ghi trên dải băng. • Ví dụ 2: Một ví dụ phức tạp hơn một chút là lấy bù 2 (two's complement) của số nhị phân. Phép toán này thường được máy tính sử dụng để thực hiện trừ nhị phân. • Trước đây, trên những máy cộng cơ học, 34 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán người ta thực hiện phép trừ tương tự nhưng trên cơ số 10, sử dụng phương pháp lấy bù 10 (10’s complement – bù 9 + 1). • Ví dụ để tính 17 – 14, người ta tìm bù 9 của 14 là 85, sau đó cộng thêm 1 là 86. Lấy 86 + 17 = 103, bỏ giá trị nhớ 1 bên trái nhất còn lại là 3. • Để thực hiện trừ nhị phân, lấy bù 2 số trừ và cộng với số bị trừ. Cho ví dụ để tính 5 – 2, lấy bù hai số 2 và cộng với số 5. Giả sử dùng 3 bit để biểu diễn giá trị nhị phân của 5 và 2: 35 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán Nhị phân Ý nghĩa 010 2 110 bù 2 (= bù 1 + 1) của 2 +101 cộng với 5 1011 3 (bỏ bit nhớ 1 bên trái nhất) • Sau đây là các lệnh của máy Turing để lấy bù 2 một số nhị phân: 1 (1, 0, 1, 1, Right) 2 (1, 1, 0, 1, Right) 3 (1, Δ, Δ, 2, Left) 4 (2, 0, 1, 3, Right) 5 (2, 1, 0, 2, Left) 36 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán 6 (3, 1, 1, 3, Right) 7 (3, 0, 0, 3, Right) 8 (3, Δ, Δ, halt, Stationary) • Lệnh 1 và 2 thực hiện lấy bù 1 các bit trên dải bằng. • Lệnh 3 thực thi khi máy Turing đã lấy bù 1 tất cả các bit và gặp ký tự trống bên cuối phải của dải băng. Khi lệnh này thực thi, máy sẽ đến trạng thái 2 và di chuyển sang trái. • Trong trạng thái 2, nếu máy gặp bit 0, lệnh 4 sẽ làm cho 0 được thay bằng 1, máy sẽ đến trạng thái 3 và di chuyển sang phải. 37 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán • Khi máy ở trạng thái 3, lệnh 6 và lệnh 7 làm cho máy di chuyển sang phải mà không thay đổi nội dung dải băng. Khi máy gặp ký tự trống bên phải lần nữa, lệnh 8 sẽ làm cho máy dừng. • Trong trạng thái 2, nếu máy gặp bit 1, lệnh 5 sẽ làm cho 1 được thay bằng 0, máy vẫn ở trạng thái 2 và di chuyển tiếp sang trái cho đến khi gặp bit 0, khi này lệnh 4 được thực thi như đã mô tả ở trên. • Ví dụ số nhị phân là 010, máy Turing sẽ tạo các nội dung như sau trên dải băng khi nó thực thi: 38 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán 0 1 0 Δ Δ nội dung ban đầu 1 0 1 Δ Δ lấy bù 1 hoàn tất 1 0 0 Δ Δ sau khi thực thi lệnh 5 1 1 0 Δ Δ sau khi thực thi lệnh 4 1 1 0 Δ Δ dừng sau khi thực thi lệnh 8 • Máy Turing thực hiện trên nhiều giá trị nhập nhưng không phải tất cả. Giả sử nội dung của dải băng ban đầu đều là 0: 0 0 0 Δ Δ nội dung ban đầu • Sau khi thực hiện lấy bù 1, tất cả các bit 0 thành 1: 1 1 1 Δ Δ 39 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán • Khi này lệnh 5 được thực thi để tìm các bit 1 và thay bằng 0. Trong trường hợp này, không bao giờ máy gặp bit 0 để làm cho lệnh 4 thực thi và đưa máy vào trạng thái 3 để máy di chuyển vào cuối dải bằng và kết thúc thích hợp. 40 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng