هل يمكن إثبات == decidable؟

Question

في نظرية الحساب ، هل المصطلحات قابلة للتبادل وقابلة للتشويش؟ أنها لا تعني الشيء نفسه؟

على سبيل المثال ، غالبًا ما ترى السؤال عما إذا كان هناك شيء يمكن الإشارة إليه على أنه مشكلة في القرار (Das entscheidungsproblem).

Answer 1

هذه مختلفة. في الواقع ، فإنها تشير إلى مناطق مختلفة تماما.

يعني Decidable أنه يمكن حل مشكلة القرار لجميع المدخلات المحتملة بواسطة آلة تورينج ، والتي تضع "قبول" أو "رفض".

يعني أنه يمكن إثبات وجود بيان رياضي من خلال دليل رياضي.

في الواقع ، لا يمكنك مقارنة "Decidable" و "Diviber" ، حيث تشير هذه السمات إلى أشياء مختلفة تمامًا.