Không phải cái gì máy tính cũng làm đuợc

Đây là chứng minh:

2 responses to “Không phải cái gì máy tính cũng làm đuợc

  1. GS! Tại sao lại không dùng một máy HY để kiểm tra chương trình của X? Như vậy không phải mọi thứ đều hợp lý hay sao?

    • Trong ví dụ kia, khối N bản chất chính là một cổng not, trong đó kết quả đầu ra là ngược lại với đầu vào. Vậy, nếu HY là HX bỏ khối N thì chẳng có gì sai. Đó là một trường hợp khác và vì thế kia chỉ là ví dụ, chưa phải là chứng minh. Nhưng mục tiêu cuối cùng là tạo ra một cỗ máy duy nhất để kiểm tra chương trình và kiểm tra chính nó. Gọi khối kiểm tra chương trình là HX thì khối kiểm tra cho HX là HY, kiểm tra cho HY là HZ,… Tuy nhiên, trong giả sử cho phép bộ nhớ chương trình và thời gian thực thi là vô hạn.
      Em cũng biết một chút về lập trình và cũng đã gặp một số trường hợp rơi vào kiểu “The halting problem”. Trường hợp chương trình chạy mãi không dừng thì gặp nhiều và chắc ai cũng từng gặp. Có trường hợp hiếm hơn là RAM lúc nào cũng 99% khi thực hiện chương trình nào đó. Cũng có khi là bắt buộc phải thiết kế một chương trình chạy mãi mãi như trong lập trình nhúng. Nhìn chung, khi rơi vào những trạng thái đó thì chắc chắn đã kẹt trong một khối lệnh nào đó. Vấn đề halting thực sự không phải là hiếm gặp và cũng không phải không thể xây dựng chương trình kiểm tra. Ví dụ như ta có thể xây dựng 1 chương trình thay ta debug chương trình, nếu nhận thấy các biến nhận giá trị thay đổi theo chu kỳ thì hoàn toàn có thể nói rằng chương trình gặp vấn đề halting.
      Suy nghĩ một cách đơn giản, máy tính chỉ là các cổng logic cơ bản, và do vậy, về bản chất máy tính sẽ bị hoạt động theo các phép toán nhị phân. Điều đó theo suy nghĩ cá nhân của em là mọi vấn đề của máy tính có thể quy về vấn đề của toán học.
      Trong toán học thì có định lý bất toàn, em cũng không rõ định lý này. Nhưng theo mọi người nói thì The halting problem liên quan chặt chẽ với định lý kia và em cũng nghĩ thế, vấn đề chính là có những thuật toán không thể kiểm tra chứ không phải có hay không tồn tại cỗ máy để kiểm tra tính dừng của một chương trình. Đó là suy nghĩ cá nhân của em.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s