Máy tính Turing, Von Neuman, Goldel Tôi nghe nói có 3 người đã làm nên cơ sở toán học cho chiếc máy tính mà ngày nay chúng ta đang dùng. Có bạn nào biết cụ thể lí thuyết của các ông này không? Tôi mới đọc được bài viết này trên VNEXPRESS hay quá Computer lượng tử có thể 'xử lý' bài toán không giải được Nhà khoa học Australia gốc Việt Kiều Tiến Dũng đã có một khám phá có thể làm cho nền toán học và khoa học computer của thế kỷ trước vượt qua được giới hạn của chính nó: Những bài toán từng được coi là "không giải được" hoặc "không tính được" có thể sẽ giải được bằng cách sử dụng những tính chất bí ẩn của cơ học lượng tử. Công trình này hiện thu hút sự chú ý của nhiều nhà khoa học trên thế giới. Hoàn toàn độc lập với Kiều Tiến Dũng, hai nhà khoa học New Zealand là Christian Calude và Boris Pavlov cũng đi đến những kết luận tương tự. Tạp chí New Scientist, một tạp chí tiên phong trong việc giới thiệu những tư tưởng mới trong khoa học, bình luận: Đó là một cuộc tấn công táo bạo vào chính những giới hạn của toán học, nhờ đó có thể lấy lại những kho báu mà chúng ta tưởng rằng vĩnh viễn sẽ nằm ở phía bên kia tầm với. 1- Giới hạn tính toán bằng computer Alan Turing. Mặc dù computer ngày nay làm được biết bao nhiêu điều kỳ diệu, nhưng nó có những hạn chế nội tại không thể vượt qua. Người có công khám phá ra điều này là Alan Turing (1912-1954), nhà toán học xuất sắc người Anh, chuyên gia giải mã kỳ tài của Anh trong Chiến tranh thế giới thứ II, được coi là một trong những cha đẻ của khoa học computer ngày nay. Ngay từ năm 1936, Turing đã phác thảo ra thiết kế của một chiếc máy tính hoạt động theo chương trình, được gọi là máy Turing (Turing Machine). Về nguyên tắc, đó chính là cái mà bây giờ chúng ta gọi là computer. Sau chiến tranh ông dồn hết nỗ lực vào việc tìm nguyên lý hoạt động cho chiếc máy tưởng tượng của mình. Năm 1954, ông tự sát vì bị kết tội đồng tính luyến ái, để lại cho đời một tác phẩm bất hủ, được liệt vào danh sách 10 công trình khoa học tuyệt tác của thế kỷ 20: "On the Computability of Numbers" (Về khả năng có thể tính toán bằng số). Nội dung cơ bản của công trình này chỉ rõ khi nào một bài toán có thể giải được (bằng số) và khi nào thì không. Gần như đồng thời, Alonzo Church, một nhà logic toán học nổi tiếng tại Đại học Princeton cũng cho công bố một bài báo nhan đề "Một bài toán không giải được của lý thuyết số sơ cấp" (An Unsolvable Problem of Elementary Numbertheory), trong đó chỉ ra rằng có những bài toán không thể giải được bằng thuật toán. Ngay lập tức, Turing chứng minh rằng kết luận của Church tương đương với kết luận của chính ông. Kết luận đó đã đi vào lịch sử của khoa học tính toán như một nguyên lý nền tảng về khả năng giải được hoặc không giải được của một bài toán, được gọi là Luận đề Turing-Church (Turing-Church Thesis) với nội dung cơ bản như sau: Nếu một bài toán có thể giải được bằng cách sử dụng một tập hợp các quy tắc rõ ràng trong một số bước hữu hạn, thì bài toán đó có thể giải được bằng một chương trình trên computer, và ngược lại. Thiết kế sơ bộ của máy Turing. Nói một cách đơn giản: Một bài toán được coi là giải được nếu có thể tìm được một thuật toán hữu hạn để giải nó. Nếu không, bài toán là không giải được. Thực chất luận đề này là sự tổng quát hóa nguyên tắc lập trình cho computer hiện đại. Nó đã trở thành nền tảng, "sách gối đầu giường", một định nghĩa bất khả kháng của khoa học tính toán. Sau khi khẳng định nguyên lý hoạt động cho chiếc máy của mình, Turing đặt vấn đề: Phải chăng có những bài toán đòi hỏi một thời gian vô hạn để giải? Và ông đã tìm ra một bài toán cụ thể thuộc loại đó - bài toán Sự cố treo máy - SCTM (The Halting Problem) nổi tiếng. Nội dung cụ thể là: Liệu có thể tiên đoán một chương trình cho trước sẽ ngừng hoặc chạy vòng quanh mãi mãi hay không? Turing trả lời: Không, không thể tiên đoán được. Do đó không thể khắc phục được sự cố này. Trong khi sử dụng computer, ai cũng có thể gặp SCTM. Gặp sự cố này chúng ta chỉ có cách kiên trì chờ đợi hoặc bấm nút "restart" (khởi động lại). Các nhà khoa học computer sau này cũng tiếp tục xác nhận rằng không có ngôn ngữ chương trình nào (Pascal, BASIC, Prolog, C,...) có thể có được một công cụ cho phép khám phá ra mọi sai hỏng (bugs) dẫn tới ngưng hoạt động hoặc gây ra những vòng xử lý (processing loops) kéo dài vô tận. Sự cố treo máy là bài toán điển hình về hạn chế của computer. Sau này các nhà khoa học computer còn xác định được nhiều bài toán hạn chế khác như bài toán virus, bài toán tìm chương trình tối ưu cho một hoạt động định trước. Các nhà toán học cho rằng cơ sở logic của tính hạn chế này là Định lý bất toàn của Kurt Godel: Bất kỳ một hệ logic hình thức nào cũng không đủ mạnh để tự nó chứng minh nó phi mâu thuẫn, suy ra computer cũng không thể khắc phục được những sai hỏng trong những bài toán mà nó phải tự "xử lý" nó. Gregory Chaitin tại IBM còn cho rằng nguyên nhân của những hạn chế đó là ở chỗ tính ngẫu nhiên không phải chỉ tác động trong vật lý (như trong cơ học lượng tử), mà tác động ngay cả trong toán học. Chẳng hạn, số nguyên tố là hiện tượng mang tính ngẫu nhiên mà toán học không thể tìm ra những quy tắc xác định thống trị chúng. Tóm lại các hệ logic cũng chứa đựng tiềm ẩn tính bất định! Với tất cả những lý lẽ đó, khoa học computer dựa trên Luận đề Turing-Church đã tự đặt ra một giới hạn không thể vượt qua. Đó là một kết luận mang ý nghĩa như một "chân lý không thể thay đổi", một nguyên lý "bất di bất dịch", một cột mốc "vĩnh viễn ở phía bên kia tầm với", một bức tường "bất khả xâm phạm". Trong suốt hơn nửa thế kỷ qua, không ai dám vượt qua bức tường giới hạn đó. "Những việc cần làm ngay"
2-Computer lượng tử sẽ cho phép vượt qua giới hạn Kiều Tiến Dũng. Năm 1984, sau khi đỗ bằng cử nhân toán - lý xuất sắc tại Đại học Queensland, Australia, Kiều Tiến Dũng nhận được học bổng làm luận án tiến sĩ tại Đại học Edinburgh ở Anh. Hoàn thành luận án năm 1988, ông trở thành giáo sư Đại học Edinburgh và Đại học Oxford. Năm 1991, ông trở về làm giáo sư Đại học Melbourne, đồng thời cộng tác nghiên cứu với các đại học danh tiếng nhất của Mỹ như Đại học Princeton, Đại học Columbia, Đại học MIT. Hiện ông là lãnh đạo nhóm nghiên cứu của CSIRO - Cơ quan nghiên cứu quốc gia của Australia, kiêm giáo sư vật lý lý thuyết tại Đại học Swinburne thuộc thành phố Melbourne. Trong một công trình nghiên cứu ứng dụng các nguyên lý của cơ học lượng tử vào khoa học tính toán được gửi tới Viện nghiên cứu quốc gia Mỹ ở Los Alamos gần đây, giáo sư Kiều Tiến Dũng đã đưa ra một kết luận hết sức quan trọng: "Chúng tôi bác bỏ Luận đề Turing-Church bằng cách chỉ ra rằng tồn tại những bài toán không giải được theo nguyên lý Turing, nhưng có thể giải được bằng cách thực hiện những quy trình cơ học lượng tử xác định rõ ràng". Nói cách khác, giáo sư Dũng đã khám phá ra rằng những bài toán không giải được bằng computer hiện nay thực ra có thể giải được bằng computer lượng tử - computer dựa trên nguyên lý mã hóa lượng tử. Theo NewsFctor, công trình của giáo sư Kiều có thể bắn một phát đạn trúng hai đích: Bài toán số 10 của David Hilbert và SCTM của Alan Turing. Năm 1900, trong Hội nghị toán học thế giới họp tại Paris, Hilbert, một trong những nhà toán học lớn nhất thời đó, nêu lên 23 bài toán chưa giải được như một thách thức đối với toán học thế kỷ 20. Bài toán số 10 có nội dung như sau: "Hãy tìm một phương pháp để xác định xem liệu một phương trình Diophantine có giải được hay không?". Phương trình Diophantine là phương trình đại số dạng đa thức nhiều biến với hệ số nguyên, nghiệm nguyên. Thí dụ Định lý Pythagoras hoặc Định lý cuối cùng của Fermat là những thí dụ cụ thể của phương trình Diophantine. Có thể phát biểu lại bài toán số 10 như sau: Liệu có thể tìm được một thuật toán hoặc một chương trình computer để tìm nghiệm nguyên của một phương trình đại số dạng đa thức nhiều biến với hệ số nguyên hay không? Năm 1970, bài toán số 10 được các nhà khoa học computer chứng minh rằng nó tương đương với bài toán "Xác định xem liệu một chương trình computer định trước có thể giải được những phương trình đại số đa thức hay không, hay sẽ bị treo hoặc dừng?". Từ đó thấy rằng bài toán số 10 của Hilbert tương đương với SCTM của Turing - một bài toán không giải được. Giáo sư Kiều Tiến Dũng tuyên bố ông có thể giải được cả hai bài toán trên. Ông giải thích, với cơ học lượng tử, chúng ta có thể sử dụng một "thuật toán lượng tử" để tìm kiếm một số vô hạn lời giải khả dĩ thích hợp với phương trình trong một khoảng thời gian hữu hạn. Đây là đặc điểm quan trọng nhất của computer lượng tử - yếu tố hơn hẳn và khác biệt hẳn của computer lượng tử so với computer thông thường hiện nay. David Hilbert. Nếu có thể xem xét tất cả các lời giải có thể có thì đương nhiên sẽ biết phương trình có thể giải được bằng thuật toán của chúng ta hay không, và cũng sẽ biết computer lượng tử có bị treo hay không, tức là cùng một lúc có thể giải được cả bài toán số 10 của Hilbert lẫn SCTM của Turing. Giáo sư Dũng nhấn mạnh: "Thuật toán lượng tử của chúng tôi, thực ra, được xem như một cuộc tìm kiếm vô hạn các số nguyên trong một khoảng thời gian hữu hạn - kiểu tìm kiếm cần thiết để giải sự cố treo máy của Turing". Nhưng tại sao computer lượng tử lại có khả năng phi thường đến như thế? Câu trả lời phụ thuộc vào cơ sở vật lý của computer lượng tử - những nguyên lý kỳ lạ của thế giới lượng tử mà thế giới thông thường không có. "Những việc cần làm ngay"
3. Cơ sở vật lý trong khám phá của giáo sư Kiều Tiến Dũng Ngôn ngữ cơ bản của computer là hệ nhị phân - dãy chữ số gồm 1 và 0. Số 1 tương ứng với trạng thái mạch điện đóng và ngược lại, số 0 tương ứng với trạng thái mạch điện mở và ngược lại quan hệ tương ứng này là 1-1. Nói cách khác, mỗi trạng thái vật lý của mạch điện tương ứng với một thông tin duy nhất và ngược lại. Trong computer lượng tử, tình hình diễn ra hoàn toàn khác: Các hạt lượng tử, chẳng hạn electron và protons, cùng một lúc có thể tồn tại trong những trạng thái lượng tử khác nhau. Các nhà khoa học mô tả đó là sự tồn tại trong một "siêu vị thế trạng thái" (superposition of states). Tính chất này đến nay vẫn là một đặc trưng bí ẩn của thế giới lượng tử mà bản chất của nó chưa ai có thể giải thích rõ ràng chính xác. Một số người mô tả nó như một biểu hiện "rối lượng tử" (quantum entanglement), một số khác coi đó như một trong các biểu hiện bất định. Chẳng hạn, điều rất kỳ lạ là trong cùng một lúc các hạt lượng tử có thể đồng thời quay quanh trục (spining) theo chiều thuận kim đồng hồ lẫn chiều ngược kim đồng hồ, hoặc cùng một lúc có thể đồng thời đạt những mức năng lượng khác nhau. Nhưng dù chưa giải thích được bản chất của hiện tượng siêu trạng thái, các nhà nghiên cứu computer lượng tử vẫn đang tìm cách lợi dụng tính chất bí ẩn đó để xây dựng một thế hệ computer hoàn toàn mới - computer lượng tử - trong đó tại mỗi thời điểm computer có thể đồng thời có hàng nghìn trạng thái khác nhau, tức là tại mỗi thời điểm computer có thể đồng thời thực hiện hàng nghìn phép toán khác nhau. Điều này dẫn tới kết quả computer lượng tử có thể xử lý một lượng thông tin vô hạn trong một thời gian hữu hạn. Đó chính là cơ sở vật lý của khám phá của Kiều Tiến Dũng, Christian Calude và Boris Pavlov. Với khám phá này, không phải chỉ có bài toán số 10 của Hilbert hoặc SCTM của Turing sẽ được giải, mà sẽ có hẳn một lớp các bài toán không giải được sẽ được giải, với công cụ mới là computer lượng tử. Giả thuyết Golbach (Golbach' s Conjecture) có thể sẽ là một trong lớp đó. Giả thuyết này nói rằng mọi số chẵn đều là tổng của hai số nguyên tố. Giả sử bạn có thể viết được một chương trình cho computer lượng tử để, trong một thời gian hữu hạn, kiểm tra một số lượng vô hạn các thí dụ cụ thể (điều mà computer thông thường không thể làm vì đòi hỏi thời gian vô hạn). Nếu bạn tìm thấy một trường hợp sai, tức là Giả thuyết Golbach sai, bài toán chấm dứt. Nếu chương trình chạy trên máy hoàn thành mà không phát hiện thấy trường hợp sai, suy ra giả thuyết đúng. Một bài toán khác trong lớp đó có thể sẽ là Giả thuyết Riemann (Riemann's Hypothesis), một "chướng ngại lớn" của toán học đang được treo một giải thưởng trị giá 1 triệu USD cho ai giải được, có thể cũng sẽ được computer lượng tử trong tương lai giải quyết. Và nếu quả thật lớp những bài toán "ghê gớm" này đều được giải quyết hết thì không còn gì có thể so sánh nổi với tầm vóc vĩ đại của computer lượng tử nữa. Khi đó khó mà dự đoán khoa học sẽ còn tiến bộ vượt bậc đến đâu nữa và tạo ra những huyền thoại gì. Và tất nhiên khi đó chúng ta sẽ có dịp nhìn nhận lại rằng ai là người đã tiên đoán được khả năng siêu phàm của computer lượng tử như thế, và đã tiên đoán vào lúc nào. 4. Kết luận và nhận định bước đầu Sẽ là quá sớm để đưa ra một kết luận khẳng định chung cuộc vào lúc này về công trình nghiên cứu của Kiều Tiến Dũng và của các nhà khoa học New Zealand nói trên. Bởi vì hiện nay computer lượng tử chưa ra đời, chúng đang được thai nghén trong các dự án nghiên cứu. Bất cứ khám phá nào, dù trên lý thuyết đúng 100%, cũng chỉ có thể được coi là một chân lý sau khi đã được thực nghiệm kiểm chứng. Tuy nhiên, về mặt lý thuyết, công trình nghiên cứu của Kiều Tiến Dũng được nhiều nhà vật lý - toán học và khoa học computer đánh giá cao, và đang nằm trong sự chú ý của giới khoa học computer trên toàn thế giới. Tiến sĩ Richard Gomez, giáo sư Đại học George Mason ở Mỹ, một chuyên gia có uy tín lớn trong khoa học computer hiện nay nhận định: "Tôi đã đọc các công trình của giáo sư Kiều Tiến Dũng và nhận thấy chúng đó hoàn toàn phù hợp với những khám phá của các nhà nghiên cứu khác trong lĩnh vực tính toán lượng tử và vật lý lượng tử. Không còn nghi ngờ gì nữa, hiện nay đã có một sự chấp nhận rộng rãi rằng thông tin mang tính chất vật lý, và vật lý lượng tử cung cấp những quy luật của sự ứng xử vật lý đó". Ông nói tiếp: "Đặc trưng kỳ lạ của cơ học lượng tử cho phép chúng ta làm việc với toàn bộ thông tin theo những cung cách hoàn toàn mới. Đơn giản là giáo sư Kiều đã biết lợi dụng những quy luật của vật lý lượng tử để đạt tới những kết quả mà trong thế giới của vật lý cổ điển không thể đạt tới được". Nếu lý thuyết của các nhà khoa học này được thực nghiệm trong tương lai sắp tới xác nhận, thì đây có thể sẽ là những thành tựu sánh ngang với những công trình bất hủ nhất của khoa học tính toán trong thế kỷ 20. Sự đánh giá này sẽ được kiểm nghiệm nhanh hay chậm tùy thuộc vào tốc độ phát triển của công nghệ computer lượng tử. Bản thân giáo sư Kiều Tiến Dũng cho rằng khoảng vài ba chục năm nữa computer lượng tử sẽ biến thành hiện thực. (Theo Tia Sáng) "Những việc cần làm ngay"
Có một bài toán mà chứng minh không giải được trên máy TURING, viết ra đây cho anh em tham khảo. bài toán cũng đơn giản. Thứ nhất bảng biến đổi được gọi là tự chấp nhận nếu như khi áp dụng chính các phép biến đổi của bảng cho bảng ta nhận được một quá trình mà sớm hay muộn cũng sẽ dừng. Còn được gọi là không tự chấp nhận nếu như ngược lại. Ví dụ xét bảng sau: a -> b c -> de ab -> k ( Bảng này giống như một sơ đồ giải mã) Khi thực hiện các phép biến đổi của bảng cho chính bảng ta nhận được tuần tự các bảng tương ứng dưới đây : b - >b ( Vì a - > b, nên nhớ là các phép biến đổi có thứ tự c->de ưu tiên từ trên xuống) ab -> k Tiếp theo: b ->b c->de bb->k (a_>b) Tiếp theo: b->b de->de (c->de) bb->k Đến chỗ này thì kết thúc, không biến đổi được nữa nên bảng trên là bảng tự chấp nhận. Có những bảng không tự chấp nhận ví dụ như bảng: ->a Bảng này trong máy Turing cứ gặp kí tự trắng ở đầu thì nó lại biến thành a. Quá trình không chấm dứt . Câu hỏi đặt ra là liệu có một thuật toán xác định một bảng bất kì là tự hay không tự chấp nhận hay không ? Chứng minh như sau. Trước hết cần phải nói thêm rằng Turing định nghĩa bài toán có thuật toán giải được là bài toán có thể giải quyết trên máy Turing do ông sáng chế. Sau này giới toán học còn chấp nhận thêm máy MarKov( tên của một nhà toán học Nga) , máy này đơn giản và thông minh hơn máy Turing.Chúng ta có thể dễ dàng chứng minh được một bài toán giải bằng máy Turing thì giải được bằng máy Markov và ngược lại. Trở lại với bài toán đặt ra. Giả sử có thuật toán A mà khi ứng dụng nó vào Bảng P nào đó sẽ cho ta giá trị: C nếu như P tự chấp nhận và H nếu như ngược lại. Ta xây dựng thêm thuật toán B trên máy Turing như sau : Khoảng trắng C H Q1 C,Q1 Khoảng trắng,Q1 !(Dừng) Có nghĩa là nếu B gặp khoảng trắng thì biến khoảng trắng thành C sẽ nhảy về lại Q1 , gặp C sẽ biến C thành khoảng trắng rồi về lại Q1. Gặp H thì dừng. Có nghĩa là nếu gặp kí tự C thì làm việc không có điểm dừng còn kí tự H sẽ ngay tức khắc dừng lại. Lí thuyết của Turing chứng minh rằng nếu tồn tại 2 thuật toán a, thì tích của chúng K=A.B cũng tồn tại ( thực hiện A trước , sau đó đến B) Ta giả sử là tồn tại A, thế nên cũng tồn tại K. Bây giờ ta chứng minh rằng K không tồn tại, từ đó suy ra A không tồn tại. Thật vậy: Giả sử thuật toán K có bảng biến đổi tự chấp nhận có nghĩa là A ( Bảng của K) cho ra kí tự C) cho nên K( Bảng của K)=A.B( bảng của K) sẽ thực hiên không dừng vì khi gặp C, thuật toán B không cho phép máy dừng. Vì vậy K lại trở thành không tự chấp nhận. Suy ra vô lí. Bây giờ giả sử thuật toán k có bảng biến đổi không tự chấp nhận. Có nghĩa là A( bảng của K) cho ra kí tự H. Khi đó K( bảng kicúa K)= A.B( Bảng của K) dừng ngay tức khắc. Có nghĩa là K tự chấp nhận, suy ra vô lí. Do đó K không tồn tại. Suy ra A không tồn tại. Đó là cm đầy đủ theo qua niệm bài toán giải được khi có thuật toán chạy được trên máy Turing. Россия моя пе?вая лZбовO!!
Đây là ý kiến của bạn tôi về cái bài báo viết trên Vnexpress. Mọi người cho ý kiến nhá! Um, cai nay tao co biet. Bao VNExpress thi may biet roi, dich tao lao lam. Thu nhat, can phai noi ro, may tinh luong tu se giai quyet rat nhieu bai toan cua li thuyet tinh toan (Computability) chu ko phai la tat ca nhung van de lon cua toan hoc (Mathematics). Vi du, mot lan nua dinh li Godel se dung: "he thong toan hoc chua may tinh luong tu se ko c/m duoc tinh phi mau thuan cua no". Chuyen giai bai toan Goldback va Riemain la chuyen xa voi lam. Nam ngoai tao co hoc mon Computability theory roi, ngoai ra cung da nghe tien si Chi Chi Yao, chuyen gia ve may tinh luong tu, dat giai thuong Turing (giai thuong lon nhat cua Tin hoc, tuong duong voi Field va Nobel) cho nhung cong trinh ve may tinh luong tu noi ve no'. Thuc ra thi Church-Turing Thesis phat bieu nhu the nay: tat ca nhung bai toan giai duoc bang finite-state machine deu giai duoc bang Turing machine. Halting problem ko giai duoc bang Turing machine -> ko giai duoc bang finite state machine. Tuy nhien may tinh luong tu la may tinh infinite state -> no co the se vuot qua. Tao nhan manh la co the. Ko ai chac chan khi chua nhin thay no. Cho du vay thi co hoc luong tu van phai dat tren nen tang cua toan hoc. Va du co may tinh luong tu thi se xuat hien nhung van de khac ko giai quyet duoc bang no', va se can den mot may tinh khac. Tat nhien anh huong cua no la rat lon. Ngoai ra, tien doan ve viec giai quyet nhung bai toan ko giai duoc hien nay bang may tinh luong tu ko phai cua cha Kieu Tien Dung nay dau, VNExpress no nhu sung. Trong cuon sach "The emperor's new mind" cua Penrose, nguoi cung nghien cuu voi Stephan Hawking (thien tai vat li, chac may biet) ve lo den va co hoc luong tu, ong da dat ra cau hoi "lieu co the ton tai mot chuong trinh AI gia lap duoc nao nguoi hay ko" va tra loi "rat co the nao nguoi hoat dong dua tren nguyen li bat dinh cua luong tu, nghia la ko the gia lap duoc bang finite state machine", dieu do cung dong thoi khang dinh vi tri cua may tinh luong tu neu no ton tai. Hehe, noi chung la may tinh luong tu dang la hot trong tin hoc li thuyet. Tao biet ve no kha lau roi, du la ko ki. Neu may thich thi len google, search "quantum computer" se co rat nhieu article hay, doc VNExpress tao lao lam. Tao thay may bai no viet ve Duy be voi thang Thuan la tao biet roi. The ha, chao than ai va quyet thang. NCT Россия моя пе?вая лZбовO!! Được Thanh_Lam sửa chữa / chuyển vào 22:50 ngày 13/06/2003
Chào các bạn, VnExpress tán phét chả khác gì bác Hàm Châu. Ông Kiều Tiến Dũng này chứng minh rằng nếu ta có thể implement được một khái niệm là hamiltonian vô hạn chiều (một khái niệm của cơ lượng tử) thì có thể giải quyết được halting problem. Bản thân việc chứng minh này có thể là ý mới, và công trình của ông Dũng chắc hẳn có giá trị trong Quantum Computing và Computability, song không đến mức lỗi lạc siêu thần nhập hóa như Vnexpress miêu tả. Bạn nào muốn nghiên cứu các bài báo của ông này có thể xem danh sách sau : Submision cho LANL http://xxx.lanl.gov/abs/quant-ph/0205093 Computing the noncomputables. T.D. Kieu, Contemp. Phys. 44, 51-71 (2003). http://arxiv.org/abs/quant-ph/0203034 Representations of W in number theory: finitude versus parity. T. Ord and T.D. Kieu, In Proceedings of the Fourth International Conference on Discrete Mathematics and Theoretical Computer Science, Dijon, France, E-print math. NT/0302183 (in press, 2003) A reformulation of the Hilbert's tenth problem through quantum mechanics. T.D. Kieu, Proc. Roy. Soc. Lond. (submitted, 2003), http://arxiv.org/abs/quant-ph/0111063. Quantum algorithm for the Hilbert's tenth problem. T.D. Kieu, International J Theoretical Physics, http://arxiv.org/abs/quant-ph/0110136. Godel's incompleteness, Chaitin's W number and quantum physics. T.D. Kieu, J Optics B, http://arxiv.org/abs/quant-ph/0111062. On the existence of a new family of Diophantine equations for W. T.D. Kieu etc (submitted), http://arxiv.org/abs/math.NT/0301274 Bài của Calude và Pavlov, được nhắc đến trên New Scientist: http://www.cs.auckland.ac.nz/~cristian/smashandgrab.htm http://www.arxiv.org/abs/quant-ph/0112087 New Scientist magazine , vol 174 issue 2337, 06/04/2002, 24-28 Có một bài báo tranh luận với ông KTD, ở đây: http://www.math.tau.ac.il/~tsirel/Research/Recent/kieu.html Altus Được altus sửa chữa / chuyển vào 16:05 ngày 14/06/2003
