Những hiểu lầm “xác sống” trong khoa học máy tính lý thuyết
(scottaaronson.blog)- Tính tính được và NP-hard trong khoa học máy tính lý thuyết là các khái niệm áp dụng cho hàm, ngôn ngữ và dãy vô hạn, chứ không phải cho từng số nguyên riêng lẻ hay một câu hỏi đúng/sai đơn lẻ
- Trong ví dụ của Sipser, “hàm f luôn trả về 1 nếu Chúa tồn tại, còn nếu không thì luôn trả về 0” trong cả hai trường hợp đều là hàm hằng, nên tính được
- P vs NP không phải là một bài toán nhận đầu vào, mà là một câu hỏi có/không duy nhất, nên bản thân nó không thể được gọi là NP-hard hay không tính được
- Toàn bộ hàm Busy Beaver là không tính được, nhưng một giá trị cụ thể như BB(6) không thể được xử lý theo cùng cách, vì với bất kỳ số nguyên k nào cũng tồn tại chương trình
print k - Cốt lõi của sự nhầm lẫn lặp đi lặp lại là việc áp dụng các khái niệm dành cho đối tượng vô hạn vào các bài toán riêng lẻ; thói quen trộn lẫn tính không tính được của bài toán dừng với tính bất toàn Gödel cũng thuộc cùng một kiểu nhầm lẫn
Phạm vi của tính tính được mà ví dụ của Sipser dạy ta
- Trong Introduction to the Theory of Computation của Michael Sipser có một bài tập làm rõ định nghĩa về tính tính được
- Đặt f:{0,1}*→{0,1} là hàm luôn trả về 1 nếu Chúa tồn tại, và luôn trả về 0 nếu Chúa không tồn tại
- Câu hỏi là f có tính được hay không, và câu trả lời không liên quan đến niềm tin tôn giáo
- f là tính được
- Hàm hằng luôn trả về 1 là tính được
- Hàm hằng luôn trả về 0 cũng là tính được
- Nếu f là một trong hai hàm đó, thì f cũng tính được
- Một câu hỏi song song có cùng cấu trúc cũng cho trực giác tương tự
- Trong câu hỏi “n có phải là số nguyên tố không khi n=3 nếu Chúa tồn tại, còn n=5 nếu không?”, dù n chưa được xác định hoàn toàn, chỉ cần biết n là phần tử của {3,5} là đủ để nói rằng đó là số nguyên tố
- f cũng vậy: chỉ khác ở việc nó là hàm hằng nào trong hai hàm, nhưng đã đủ xác định để phán đoán rằng nó tính được
Tính tính được là vấn đề tồn tại, không phải độ khó khi viết chương trình
- Tính tính được là khái niệm áp dụng cho hàm hoặc dãy vô hạn
- Ta không gán tính tính được cho một câu hỏi có/không riêng lẻ hay một số nguyên riêng lẻ theo cùng cách
- Câu hỏi cốt lõi là liệu có tồn tại một chương trình máy tính ánh xạ đầu vào thành đầu ra hay không
- Việc chọn, tìm ra hay viết chương trình đó khó đến mức nào không nằm trong định nghĩa của tính tính được
- Ngay cả nếu để viết chương trình phải giải quyết việc Chúa có tồn tại hay không, bản thân phán định về tính tính được vẫn không thay đổi
Vì sao không thể gọi P vs NP là NP-hard
- Câu hỏi “liệu bản thân câu hỏi P versus NP có NP-hard nên không thể giải được hay không” đã được lặp lại nhiều lần trong 25 năm qua
- NP-hard áp dụng cho hàm hoặc ngôn ngữ nhận đầu vào, như 3SAT, Independent Set, Clique
- Đầu vào là Boolean formula, graph, v.v.
- Đầu ra là câu trả lời cho đầu vào đó
- Một bài toán được gọi là NP-hard khi nếu có thể giải nó trong thời gian đa thức, thì thông qua phép quy giảm, mọi ngôn ngữ hoặc hàm trong NP cũng có thể được giải trong thời gian đa thức
- P vs NP không phải là hàm hay ngôn ngữ, mà là một câu hỏi có/không duy nhất
- Không loại trừ khả năng câu trả lời của nó độc lập với các tiên đề của lý thuyết tập hợp Zermelo-Fraenkel
- Nhưng không thể nói bản thân câu hỏi này là không tính được hay NP-hard
- Về mặt hình thức, một chương trình nhanh trả lời chính xác câu hỏi P vs NP có tồn tại
- Nếu P=NP, đó là chương trình in ra “P=NP”
- Nếu P≠NP, đó là chương trình in ra “P≠NP”
Cùng một nhầm lẫn lặp lại trong Busy Beaver
- Trong phần bình luận của bài viết xác định được giá trị Busy Beaver 5, các câu hỏi tương tự cũng lặp lại
- “n nhỏ nhất mà giá trị BB(n) trở nên không tính được là bao nhiêu?”
- “BB(6) có thể đã không tính được không?”
- Hàm Busy Beaver là không tính được
- Nhưng khái niệm tính tính được không được áp dụng theo cách đó cho một số nguyên riêng lẻ như BB(6)
- Dù BB(6) được xác định là số nguyên k nào đi nữa, vẫn tồn tại chương trình
print k - Chương trình này in ra số nguyên đó
- Dù BB(6) được xác định là số nguyên k nào đi nữa, vẫn tồn tại chương trình
- Thay vào đó, câu hỏi có thể đặt ra là với n nào thì giá trị BB(n) không thể chứng minh được trong một hệ tiên đề như lý thuyết tập hợp ZF
- Aaronson và Adam Yedidia đã nghiên cứu câu hỏi này vào năm 2016
- Kỷ lục hiện tại là n=745, cải thiện so với giá trị n=8000 của Aaronson và Adam
- Mọi số nguyên cụ thể đều có thể được xem là “tính được”, còn thứ không tính được là toàn bộ hàm BB
Vì sao “hiểu lầm xác sống” cứ tiếp tục sống dậy
- Cốt lõi của sự nhầm lẫn lặp đi lặp lại là việc áp dụng sai các khái niệm được thiết kế cho dãy vô hạn và hàm vào các số nguyên riêng lẻ và các bài toán mở
- Các trường hợp trộn lẫn tính không tính được của bài toán dừng với tính bất toàn Gödel cũng thuộc cùng một kiểu nhầm lẫn
- Hai khái niệm này có liên hệ mật thiết
- Gödel cho phép nói về các mệnh đề riêng lẻ
- Tính tính được Turing không phải là một khái niệm tương đối với một hệ tiên đề cụ thể, mà là khái niệm tuyệt đối
- Phần giải thích này đóng vai trò như một điểm tham chiếu để liên kết tới mỗi khi cùng một hiểu lầm mang tính giáo dục này xuất hiện trở lại
- Câu hỏi cuối cùng hướng tới việc làm thế nào để dập tắt kiểu hiểu lầm giống như “xác sống” này
1 bình luận
Ý kiến trên Hacker News
Khái niệm tính toán được có thể khá trái trực giác ở chỗ nó tất yếu bao hàm vô hạn
Ví dụ, nếu hỏi có thuật toán nào tính được độ phức tạp Kolmogorov K(s) cho một chuỗi tùy ý s hay không, thì câu trả lời nổi tiếng là “không”. Không tồn tại máy Turing nào nhận chuỗi có độ dài bất kỳ làm đầu vào rồi tính K(s), và chứng minh có thể kết thúc ngắn gọn bằng bài toán dừng
Nhưng nếu hỏi có thuật toán nào tính K(s) cho mọi chuỗi tùy ý s có độ dài nhỏ hơn n hay không, thì câu trả lời là “có”. Với bất kỳ n nào, một thuật toán như vậy đều tồn tại
Cách làm, dù khá hụt hẫng, là tạo một máy Turing có một bảng tra cứu khổng lồ chứa giá trị K(s) cho toàn bộ 2^n chuỗi khả dĩ. Việc thực sự lấy được bảng đó bằng cách nào lại là chuyện khác, nhưng một cài đặt cụ thể thì có mô tả hữu hạn, và K(s) cũng hữu hạn với mọi s, nên thuật toán đó tồn tại
Vì vậy, các câu hỏi hữu hạn về các đối tượng hữu hạn có thể không mấy thú vị dưới góc nhìn tính toán được. Ta luôn có thể viết một chương trình in ra toàn bộ câu trả lời; chỉ khi câu hỏi mở rộng sang một tập vô hạn các đối tượng thì mới trở nên thú vị rằng liệu một thứ hữu hạn có thể trả lời vô hạn câu hỏi hay không
Thực ra, vô hạn ở đây đang thay thế cho “hành vi xấp xỉ, tiệm cận và trạng thái ổn định khi N đủ lớn, vượt qua mọi mẹo một lần”
Trong thực tế, các mẹo như vậy cũng quan trọng, và các hằng số cùng các hạng bậc thấp bị bỏ qua trong so sánh Big-O vẫn ảnh hưởng lớn đến hiệu năng thật. Luôn có một sự căng thẳng giữa “bài toán đủ lớn để hệ số hằng trở nên vô nghĩa” và “bài toán đủ nhỏ để nằm trong phạm vi mà từ ‘hằng số’ ngầm ám chỉ”. Ví dụ, số nguyên 32-bit giả làm số nguyên là như vậy
Từ góc nhìn vô hạn, mọi số hữu hạn thực ra đều rất nhỏ. Ngồi trên chiếc ghế ở tận cùng vũ trụ mà nhìn, 1 dặm cũng chẳng khác gì 1 milimét
Kịch bản này về cơ bản giống như “khách sạn vô hạn của Hilbert trên máy tính”. Ta có thể dời mọi chương trình hiện có đi một ô để thêm chương trình mới, còn kích thước bảng cần cho việc tính toán thì giữ nguyên
Khái quát hơn, đa số mọi người có trực giác khá yếu về cách vô hạn, aleph và toán học siêu hạn vận hành. Nó ít liên hệ đời thường, lại gắn sâu với các tính chất phát sinh của toán học, lý thuyết phạm trù và lý thuyết tập hợp. Không chỉ vô hạn lớn hơn mọi số hữu hạn, mà còn có những vô hạn lớn hơn những vô hạn khác — điều này không hề hiện ra ngay với trực giác chỉ dừng ở khái niệm “vô hạn” kiểu tiểu học
Câu hỏi thú vị hơn là liệu có tồn tại một n < ∞ nào cho phép tính được thuật toán hay không; hiển nhiên câu trả lời là không, và giải Turing bị mất luôn
Ý tưởng là liệt kê mọi máy Turing khả dĩ theo thứ tự từ ngắn đến dài rồi tìm máy in ra s. Nếu đã thử hết mọi máy ngắn hơn mà không máy nào in ra s, thì ta đã tìm được máy ngắn nhất in ra s, nên độ dài của nó chính là K(s). Có thể vẫn có máy khác cùng độ dài hoặc dài hơn cũng in ra s, nhưng K(s) là giá trị theo độ dài nhỏ nhất nên không thay đổi
Theo kinh nghiệm của tôi, ở đây toán học kiến tạo hợp với trực giác của con người hơn khoa học máy tính cổ điển
Ví dụ, hiện vẫn chưa có chứng minh mang tính kiến tạo nào cho sự tồn tại của một chương trình in ra lời giải của bài toán P=NP
Trong bài báo của tôi, tôi cũng bàn về vấn đề này liên quan đến các tập Julia tính được. Mark Braverman đã chứng minh rằng mọi tập Julia bậc hai đều tính được, nhưng ông cũng giải thích rằng chứng minh đó không tính được một cách đồng nhất. Thay vào đó, ông xây dựng 5 cỗ máy nhận tham số của tập Julia mong muốn rồi cố vẽ nhiều tập khác nhau ở độ phân giải cần thiết, và với mỗi tập Julia thì sẽ có một trong số đó vẽ đúng
Trong toán học kiến tạo, khái niệm kiến tạo về tập compact tương ứng khá sát với nghĩa của tập tính được cần cho các tập Julia tính được. Nhưng việc mọi tập Julia bậc hai đều compact thì không thể chứng minh theo lối kiến tạo; thay vào đó phải chia mặt phẳng phức của các tham số khả dĩ thành nhiều miền, rồi trong từng miền chứng minh rằng các tập Julia tương ứng là compact
Trong toán học cổ điển, hợp của các miền này là toàn bộ mặt phẳng phức, nhưng trong toán học kiến tạo thì kết quả đó không đúng. Tương tự, trong toán học cổ điển thì hợp của các số thực dương và các số thực không dương là toàn bộ trục số thực, nhưng trong toán học kiến tạo thì điều đó cũng không đúng
Cách tiếp cận kiến tạo cho biết chính xác cần thêm thông tin gì để hiện thực hóa phép tính trong thực tế. Cụ thể, phải xác định tham số đã cho thuộc miền nào của mặt phẳng phức, để từ đó biết cần chạy cỗ máy nào trong 5 cỗ máy để nhận được hình ảnh mong muốn. Câu trả lời theo hướng này tạo cảm giác thỏa đáng hơn nhiều
Con người theo bản năng biết rằng cần phải biết mình đang ở nhánh nào của câu lệnh rẽ nhánh, chứ không phải vì được huấn luyện theo logic cổ điển nên quên mất điều đó
Tôi cũng muốn biết liệu anh có nghĩ rằng với câu hỏi “trong 5 cái thì cái nào đúng” vẫn còn thiếu một chứng minh nào đó chưa tìm ra, hay anh cho rằng điều đó là bất khả quyết như trong ZFC
Tôi nghĩ đây là một trong những yếu tố khiến tính bất khả quyết của bài toán dừng trở nên khó hiểu
Người ta muốn nói rằng “có những cỗ máy quá phức tạp nên không thể phân biệt được chúng sẽ dừng hay không”, nhưng giữa hai chương trình tầm thường
return truevàreturn false, luôn có một chương trình sẽ cho đáp án đúng với bất kỳ cỗ máy và đầu vào nàoCó thể bạn muốn phản bác rằng “những chương trình đó không biết gì về máy Turing nên phải loại chúng ra”, nhưng tính quyết định không nói về chuyện đó. Cũng có thể nghĩ rằng “điều bất khả quyết là tìm ra chương trình nào trong hai chương trình đó là đúng”, nhưng chuyện đó cũng có một đáp án đã được xác định là đúng hoặc sai. Vấn đề chỉ có thể trở nên bất khả quyết khi mở rộng sang một tập vô hạn các cặp máy/đầu vào
Ví dụ, mọi không gian vectơ hữu hạn chiều bất kỳ đều đẳng cấu theo nhiều cách với không gian đối ngẫu và đối ngẫu kép của nó, nhưng với cái sau thì có thể chọn một phép đẳng cấu “tự nhiên” nhất quán trên mọi không gian như vậy, còn với cái trước thì không thể
Điều này dễ gây ra bối rối kiểu như “Tại sao lại không đẳng cấu một cách tự nhiên? Chúng có cùng số chiều cơ mà! Việc phụ thuộc vào cơ sở thì có sao? Những chứng minh khác cũng chọn một cơ sở, tại sao ở đó lại chấp nhận được?”
Tôi nghĩ vấn đề của cách diễn đạt là nó đòi hỏi logic tình thái
“Nếu Chúa tồn tại thì đặt f:{0,1}*→{0,1} là hàm hằng 1, còn nếu Chúa không tồn tại thì đặt nó là hàm hằng 0. f có tính toán được không? Gợi ý: câu trả lời không phụ thuộc vào niềm tin tôn giáo.”
Câu hỏi chính xác là liệu f có tính toán được hay không, tức là có tồn tại một máy Turing M sao cho với mọi x thì f(x)=M(x) hay không
Câu trả lời là có. Vì trong bất kỳ thế giới nào cũng có máy Turing tầm thường M=1_M hoặc M=0_M. Ngược lại, cách diễn đạt ban đầu “f có tính toán được không” là một câu hỏi sai về mặt tình thái, gần giống một câu hỏi không chính xác về mặt ngữ pháp như nghịch lý Sleeping Beauty hay Red Envelope
Một góc nhìn khác là sự phụ thuộc vào Chúa hay vào một sự kiện thực tế nào đó chỉ được điền vào sau này, giống một chỉ thị tiền xử lý hoặc pragma được xác định trước khi dùng nhưng lại phụ thuộc vào một sự kiện thực tế nào đó có thể đúng. Nếu hỏi đúng cách thì đây chỉ là bài toán bung ra các định nghĩa chặt chẽ của hàm và tính toán được, và cả hai đều được Sipser định nghĩa tường minh
Ý là cái mà nhãn tên
fchỉ tới sẽ là hàm hằng 1 nếu Chúa tồn tại, và là hàm hằng 0 nếu Chúa không tồn tại; chỉ là trước khi biết Chúa có tồn tại hay không thì ta không biết nó là cái nào. Tính tính toán được của hai hàm hằng này là điều hiển nhiên, nên đây thực ra không phải vấn đề về tính toán được mà gần hơn với vấn đề về nhãn tênĐiều này không có gì đáng ngạc nhiên nếu nghĩ rằng chính việc lý thuyết xác suất hoạt động khi áp dụng vào thực tế đã là một điều rất bí ẩn và từ lâu là đối tượng của nhiều nghiên cứu khoa học và triết học
Cách giải quyết kiểu “would f be” được đề xuất dường như cũng không giải quyết được bao nhiêu. Mục đích của câu hỏi về “Chúa” là để người đọc tách khỏi một bài toán P-NP cụ thể và hiểu rằng với các hàm hằng thì khái niệm tính toán được trở nên vô dụng. Nếu đề xuất này thực sự hữu ích thì nó cũng phải áp dụng được cho câu hỏi P-NP ban đầu, nhưng tôi vẫn chưa thấy cách tiếp cận tình thái đi vào một câu hỏi toán học được xác định rõ như thế nào
“Nếu Chúa tồn tại thì đặt f:{0,1}→{0,1} là hàm hằng 1, còn nếu Chúa không tồn tại thì đặt f:{0,1}→{0,1} là hàm hằng 0”
Việc một vị từ như vậy có phù hợp với khái niệm về Chúa của bạn hay không lại là một vấn đề phi toán học khác
Điều này giống như khi mọi người ngạc nhiên lúc học rằng trong logic cổ điển, một mệnh đề sai kéo theo mọi thứ. Toán học có các quy tắc hình thức nghiêm ngặt, và điều quan trọng là phải gác lại các định kiến về nghĩa đời thường của những từ như “suy ra” hay “nếu”
G:t∈ℝ⁺->{0,1} được đặt là 1 nếu tại thời điểm t Chúa tồn tại, còn không thì là 0
Tất nhiên, sẽ còn thú vị hơn nếu phân tích G trong một hệ quy chiếu phi quán tính
Sipser đang tận dụng việc đa số mọi người không phân biệt rõ giữa tính toán và điều tra thực nghiệm
“Chúa có tồn tại không” có thể là một câu hỏi không thể trả lời, nhưng đó không phải trọng tâm. Việc tìm câu trả lời cho điều đó ngay từ đầu đã không thuộc phạm vi của tính toán. Tính toán chỉ là một thủ tục ánh xạ đầu vào sang đầu ra, và trong trường hợp này sự tồn tại của Chúa là một trong các đầu vào
Điều gây rối là ta không thể thực sự biết giá trị đầu vào, nhưng chương trình vẫn tồn tại và là một chương trình tầm thường. Có thể thay bằng một câu hỏi thực nghiệm nhị phân khác
Ví dụ, giả sử f:{0,1}* -> {0,1} nghĩa là “nếu ở Paris có ít nhất một nhà vệ sinh di động thì trả về 1, còn không thì 0”. Hàm này là tính toán được và thậm chí có thể thực thi thực sự với đầu vào đúng là sự thật. Hàm về Chúa cũng tính toán được, chỉ là ta chỉ có thể chạy nó với một đầu vào được phỏng đoán. Dù không thể đảm bảo đầu ra tương ứng có ý nghĩa với vũ trụ mà ta đang sống hay không, nó vẫn là một hàm tính toán được
Thậm chí có thể nghĩ đơn giản hơn chỉ với f:{0,1}* -> {0,1}. “Chúa tồn tại” và “Chúa không tồn tại” mỗi cái đều là những chuỗi bit khả dĩ. Nếu hỏi liệu có thể tồn tại một chương trình nhận một trong hai đầu vào đó rồi xuất 0, và với đầu vào kia thì xuất 1 hay không, thì dĩ nhiên là có. Việc đầu vào có đúng về mặt thực nghiệm hay không là không liên quan
ftrong câu hỏi không phải là một hàm mà là một nhãn tên. Nếu Chúa tồn tại thì cái màfchỉ tới làf1, luôn xuất 1; còn nếu Chúa không tồn tại thì nó làf0, luôn xuất 0. Vì thế, đây thực ra không phải là vấn đề về tính toán được mà là vấn đề về nhãn tênĐiều này xảy ra thường xuyên vì các nhà toán học và nhà khoa học máy tính dùng cách diễn đạt rút gọn để tiện trao đổi, lược bỏ chi tiết
Không khác gì việc nói “nhân
dxvào hai vế”. Câu hỏi “bài toán người du lịch có NP-khó không?” nói về một họ bài toán chứ không phải một cá thể cụ thể. Nếu cố định một đồ thị cụ thể thì không còn N, nên dĩ nhiên nó không thể là NP-khóNếu đã biết điều này thì nó quá hiển nhiên đến mức không đáng nói, nhưng với người không biết ý nghĩa của thuật ngữ thì gần như không thể nắm bắt được
Bản thân tôi trước đây cũng từng có một kiểu hiểu lầm tương tự ở lĩnh vực khác. Tôi từng xem DNA như mã nguồn, và tin rằng những thứ gửi thông điệp trực tiếp qua chất nền hoặc bằng cách sửa đổi DNA đang thực thi đoạn mã đó. Nhìn tổng thể thì đây không hẳn là một mô hình hoàn toàn vô dụng, nhưng cần biết khi nào không nên bị ám bởi mô hình đó
Với một nhà sinh học có nền tảng toán học, việc xem DNA đúng nguyên dạng như mô hình thực thi của máy Turing là sai rành rành, nhưng với tôi thì không như vậy. Cuối cùng đây là vấn đề xuất phát từ sự xa lạ với kiến thức nền tảng
Những từ như tính quyết định được, tính tính được, sự tồn tại, thậm chí cả trái cây, đều mang nghĩa khác nhau trong bối cảnh học thuật và bối cảnh đời thường. Khi mang trực giác của nghĩa đời thường vào bối cảnh học thuật thì sẽ sinh ra những “câu hỏi ngớ ngẩn” như vậy
Một số rất lớn nào đó trên Wikipedia “tồn tại” và “tính được” theo nghĩa học thuật, nhưng số chữ số của nó thì không thể chứa nổi trong vũ trụ của chúng ta
Nếu không đọc cẩn thận thì câu chữ rất dễ gây nhầm lẫn
Trong câu “nếu Chúa tồn tại thì đặt f:{0,1}*→{0,1} là hàm hằng 1, còn nếu Chúa không tồn tại thì là hàm hằng 0. f có tính được không?”, phương án thay thế không phải là một phần của hàm
Hàm f không phân nhánh theo giá trị của “Chúa tồn tại”; sự phân nhánh nằm trong siêu ngôn ngữ. Chúng ta không biết f=0 hay f=1, nhưng dù là hàm nào thì cả hai hàm khả dĩ đều tính được, nên f cũng tính được
Hơn nữa, kể cả nếu f thật sự chứa nhánh đó, và miền xác định của hàm là 0 (Chúa không tồn tại) và 1 (Chúa tồn tại), thì nó vẫn là một hàm tính được theo nghĩa có thể tính ra kết quả cho từng giá trị trong miền xác định
Cốt lõi của sự nhầm lẫn là đẩy một biến tự do mà ta xem là chưa biết giá trị vào trong f như thể đó là điều kiện phân nhánh
Tôi sẵn sàng phản đối ví dụ “giả sử nếu Chúa tồn tại thì n=3, còn nếu Chúa không tồn tại thì n=5. n có phải là số nguyên tố không?”
Ở đây người ta đang dùng luật bài trung để khẳng định n là 3 hoặc 5, nhưng không có cơ sở nào để biện minh rằng luật bài trung áp dụng được cho mệnh đề “Chúa tồn tại”
Nếu đã định xét xem luật bài trung có được biện minh hay không, thì cũng phải biện minh vì sao chỉ có luật bài trung là bị đem ra nghi vấn. Tại sao không bỏ luôn cả nguyên lý bùng nổ và làm việc trong paraconsistent logic? Kolmogorov cũng xem tiên đề này là có vấn đề nghiêm trọng, và ban đầu cho rằng nó không tương thích với logic kiến tạo
Ngoài ra, tùy theo cách hình thức hóa chính xác mệnh đề này, có thể thậm chí không cần đến luật bài trung
Chúa không nhất thiết bị ràng buộc bởi các định luật vật lý hay tính tất yếu logic cơ bản. Kiểu khái niệm về Chúa đó xuất phát từ một số dòng suy luận thần học nhất định chứ không phải trường hợp tổng quát
Nếu muốn, Chúa có thể khiến 6 trở thành số lẻ. Chúa có thể thay đổi toàn bộ toán học, tính nhất quán logic và toàn thể vũ trụ, hoặc tạo ra một thế giới nơi chỉ có 77 là số chẵn còn mọi số khác đều là số lẻ, và khiến mọi nhà toán học đều xem cách sắp xếp đó là hoàn toàn nhất quán và luôn luôn đúng
Vì vậy có thể nói đáp án phần nào phụ thuộc vào niềm tin tôn giáo
Khoa học máy tính lý thuyết và lý thuyết độ phức tạp dường như giữ vị trí đối với sinh viên đại học ngành CS hoặc những người làm việc ở các ngành lân cận tương tự như vật lý hạt đối với công chúng
Giống như người bình thường từng nghe đến từ rối lượng tử, chúng ta cũng từng nghe đến NP-khó, rồi thay vì tự mình đi qua các bước triển khai toán học thì lại thế chỗ bằng những phép ví von đại chúng tệ hại và các tưởng tượng viển vông
Có thể tác giả, vì được đào tạo lâu năm, đã chọn cho mình một định nghĩa rất nghiêm ngặt về tính tính được, viết cả bài xoay quanh một định nghĩa cụ thể của từ đó, rồi quay sang buộc tội những người trong thế giới dùng cùng từ ấy theo nghĩa khác là đang hỏi câu ngớ ngẩn
Khi trò chuyện với giới học thuật ở chỗ làm hoặc khi nói chuyện với người bình thường, chuyện này xảy ra thật sự rất thường xuyên. Việc thống nhất thuật ngữ chung là rất khó, và cách kẻ một ranh giới theo bộ thuật ngữ của riêng mình rồi bắt người khác phải theo là rất mệt mỏi