هل مصطلح "الاستمرارية" له معنى مختلف في الرياضيات وفي علوم الكمبيوتر؟

Question

أطرح هذا السؤال بسبب وجود بعض العبارات في السؤال "ما هي" الاستمرارية "كمصطلح في التحليل الحسابي؟" جعلني مشبوهة.

أنا مهندس، ولست عالم كمبيوتر، لذلك لا أفكر في آلة تورينج ولكن البوابات المنطقية عندما أفكر في العمليات الجبرية التي يتم إجراؤها باستخدام الأجهزة.

قرأت الجواب على السؤال "لماذا تكون الدوال الحسابية مستمرة؟" وفهمتها بالطريقة التالية:

نظرًا لأن إدخال الجهاز ذو طول لا نهائي (رقم عشري يحتوي على عدد لا نهائي من الأرقام بعد العلامة العشرية)، فإن الجهاز (على سبيل المثال:لا يمكن لآلة تورينج أو الكمبيوتر) قراءة الرقم بالكامل قبل كتابة الرقم $ن$-الرقم الناتج.

بدلاً من ذلك، يمكن للجهاز القراءة فقط $م(ن)$ أرقام الإدخال عندما يكتب $ن$-الرقم الناتج.

إذا كان الأول $ن$ أرقام مخرجات بعض الوظائف تعتمد فقط على الأولى $م(ن)$ أرقام الإدخال، الدالة مستمرة.

ومع ذلك، إذا فهمت هذه الحجة بشكل صحيح، فإن كلمة "مستمر" في نظرية الحساب ليست مطابقة لكلمة "مستمر" في الرياضيات:

لن يتطلب التقريب نحو الصفر سوى قراءة المدخلات حتى النقطة العشرية (وبالتالي $m(n)= ext{const.}$);ومع ذلك، فإن الدالة الرياضية التي يتم حسابها ليست "مستمرة" وفقًا للتعريف الرياضي لهذا المصطلح.

يمكننا أيضًا إجراء عملية رقمية ($م(ن)=ن$) وتبادل أرقام معينة بعد العلامة العشرية؛على سبيل المثال استبدال كافة 4بواسطة 9ق وجميع 9بواسطة 4س.بقدر ما أفهم، فإن الوظيفة التي يتم حسابها ليست مستمرة في أي فترة زمنية $\mathbb{R}$ (ومع ذلك، فإنه سيكون مستمرًا على اليمين $[0,\infty)$ واليسار المستمر على $(-\infty,0]$).

وإذا لم أرتكب خطأً مفاهيميًا ونستخدم a نظام الأرقام المتوازن (مثل أ الكمبيوتر الروسي في الستينيات) بدلا من النظام العشري، خوارزمية مماثلة (تبادل 0رمل 1س بدلا من 4رمل 9s) قد يمثل حتى وظيفة رياضية وهي ولا حتى الاتجاه المستمر في أي فترة من $\mathbb{R}$.

أسئلة:

هل تعتمد قابلية الحساب على نظام الأرقام المستخدم (كما يوحي المثال مع نظام الأرقام المتوازن) أم أن المصطلح "قابل للحساب" حتى مع افتراض استخدام نظام رقمي معين؟

هل الملاحظة صحيحة أن مصطلح "مستمر" ليس له نفس المعنى في الرياضيات وعلوم الكمبيوتر؟

Answer 1

إذا أردنا استخدام التوسعة العشرية لتمثيل الأعداد الحقيقية، فسينجح منطقك.لكن هذا يعطينا فكرة سيئة للغاية عن الحوسبة:

الاقتراح:الضرب في 3 لا يمكن حسابه بالنسبة للتمثيل العشري.

دليل:افترض أن الإدخال يبدأ بـ 0.3333333...في مرحلة ما، تحتاج حساباتنا إلى البدء في إخراج شيء ما.أفضل الخيارات هي 0.و 1..في الحالة الأولى، لقد أخطأنا إذا كان مدخلنا يحتوي على الرقم التالي 4 الذي لم ننظر إليه؛وفي الحالة الثانية، الرقم 2 يجعلنا مخطئين.وبالتالي، لا يمكننا إخراج بادئة مضمونة للحل.

إن استخدام قاعدة مختلفة من شأنه أن يؤدي إلى مفهوم مختلف للحسابية، ولكن أيا منها ليس مناسبا.بعض الطرق التي تؤدي جميعها إلى نفس الفكرة الجيدة للحسابية هي:

1. رمز حقيقي $x$ كسلسلة من العقلانيات $(q_n)_{n \in \mathbb{N}}$ مثل ذلك $ | x - q_n | <2^{-n} $.
2. رمز حقيقي عبر تمثيل أرقام موقعة، باستخدام $\{-1,0,1\}$.
3. رمز حقيقي $x$ كسلسلة من الفواصل العقلانية $(I_n)_{n \in \mathbb{N}}$ مع $\bigcap_{n \in \mathbb{N}} I_n = \{x\}$

عندما نتحدث عن قابلية حساب دالة على الواقع دون تحديد نوع التمثيل الذي نستخدمه، فإننا نعني واحدًا من هؤلاء (أو تمثيلًا مكافئًا آخر).هذا تمامًا كما لا نشير دائمًا إلى استخدام الطوبولوجيا الإقليدية على الواقع، إذا فعلنا ذلك، فهذه هي الحالة القياسية فقط.يمكننا الآن أن نذكر:

نظرية:إن الوظائف الواقعية القابلة للحساب (كتابة التمثيل القياسي) بالنسبة لبعض أوراكل هي بالضبط الوظائف المستمرة (كتابة الطوبولوجيا الإقليدية).

بالعودة إلى التقريب، يوضح هذا أن التقريب الدقيق تمامًا لا يمكن أن ينجح.ومع ذلك، يمكننا التحايل على هذا من خلال عدم تقييد أنفسنا بالوظائف.على سبيل المثال، المهمة التالية قابلة للحساب:

نظرا لعدد حقيقي $x \في [0,1]$, ، الإخراج سواء $0$ أو $1$.لو $س < 0.501 دولار, ، ثم $0$ هو حل مقبول وإذا $س> 0.499 دولار, ، ثم $1$ هو حل مقبول.

إذا كان الإدخال للمهمة أعلاه من $[0.499,0.501]$, ، فإن الإجابة التي نحصل عليها لا تعتمد فقط على الواقع الذي ننظر إليه، بل على الكود المحدد لذلك الحقيقي الذي تقرأه الخوارزمية.وهذا يمكن أن يجعل التفكير بشأن الخوارزميات أكثر تعقيدًا بعض الشيء، ولكن لا يمكننا حقًا تجنب ذلك.