دالة قابلة للإنشاء

في نظرية التعقيد ، تُعرَّف الدالة القابلة للإنشاء في زمن محدد بأنها دالة f من الأعداد الطبيعية إلى الأعداد الطبيعية، بحيث يمكن إنشاء f ( n ) من n بواسطة آلة تورينج في زمن من الرتبة f ( n ). والهدف من هذا التعريف هو استبعاد الدوال التي لا تُقدِّم حدًا أعلى لزمن تشغيل آلة تورينج. ^{[ 1 ]}

لنفترض أن آلة تورينج تُعرَّف بالطريقة القياسية، بأبجدية تتضمن الرموز${\displaystyle 0,1}$يحتوي على شريط إدخال قياسي يحتوي على أصفار باستثناء سلسلة الإدخال. ليكن${\displaystyle 1^{n}}$يشير إلى سلسلة مكونة من${\displaystyle n}$أي أنها التمثيل الأحادي لـ${\displaystyle n}$. يترك${\displaystyle |n|}$ليكن التمثيل الثنائي .

وظيفة${\displaystyle f}$يُطلق عليها اسم قابلة للإنشاء في الوقت المحدد إذا وُجدت آلة تورينج${\displaystyle M}$بحيث يكون الحساب${\displaystyle M(1^{n})}$توقفات في${\displaystyle O(f(n))}$خطوات ذات قيمة${\displaystyle |f(n)|}$.

قد يستخدم هذا التعريف${\displaystyle M(1^{n})=1^{f(n)}}$بدلاً من ذلك، بما أن الاثنين يمكن تحويلهما إلى بعضهما البعض في${\displaystyle O(f(n))}$خطوات. ^{[ 1 ]}

وظيفة${\displaystyle f}$يُطلق عليه اسم قابل للإنشاء في الفضاء إذا وُجدت آلة تورينج${\displaystyle M}$بحيث${\displaystyle M(1^{n})}$يتوقف مع القيمة${\displaystyle |f(n)|}$(أو ما يعادل ذلك)${\displaystyle 1^{f(n)}}$), أثناء استخدام${\displaystyle O(f(n))}$^{[ 1 ]}​

وبعبارة أخرى،${\displaystyle f}$يُطلق عليه اسم قابل للإنشاء في الفضاء إذا وُجدت آلة تورينج${\displaystyle M}$، بحيث يكون ذلك لجميع القيم باستثناء عدد محدود منها${\displaystyle n}$، الحساب${\displaystyle M(1^{n})}$يتوقف في تكوين يكون فيه بالضبط${\displaystyle f(n)}$الخلايا ليست فارغة، ولم تُكتب أي خلية أخرى أثناء العملية. ^{[ 3 ] : التعريف 2.4.} يُطلق على هذا أحيانًا اسم "قابل للإنشاء بالكامل في المساحة". ومع ذلك، فإن التعريفين متكافئان. ^{[ 3 ] : النظرية 2.7}

جميع الوظائف الشائعة الاستخدام (مثل${\displaystyle n,n^{2},2^{n},n!}$يمكن إنشاء ) في الزمان والمكان، طالما أن${\displaystyle f(n)=\أوميغا (n)}$عملية البناء بسيطة. على سبيل المثال،${\displaystyle n^{2}}$يتم بناؤها بواسطة حلقة تكرار متداخلة واحدة، بينما${\displaystyle n^{3}}$يتم بناؤها بواسطة حلقتين متداخلتين من نوع for، إلخ.

لو${\displaystyle f(n)=o(n)}$إذا كان بالإمكان إنشاء متغير زمني، فإنه سيكون ثابتًا في النهاية، لأنه بخلاف ذلك لن يكون هناك وقت كافٍ لقراءة المدخلات بالكامل.

${\displaystyle \ln n}$يمكن بناؤه في الفضاء على الرغم من${\displaystyle \ln n=o(n)}$.

لكل دالة قابلة للحساب${\displaystyle f}$، هناك دالة قابلة للحساب${\displaystyle g}$هذا وقت قابل للبناء و${\displaystyle \forall n,g(n)>f(n)}$[ ^{3 ] : اللمة 2.3}

تُستخدم الدوال القابلة للإنشاء في زمن محدد في نتائج نظرية التعقيد، مثل نظرية التسلسل الهرمي الزمني . تكمن أهميتها في أن نظرية التسلسل الهرمي الزمني تعتمد على آلات تورينج التي يجب أن تحدد في زمن O ( f ( n )) ما إذا كانت خوارزمية ما قد استغرقت أكثر من f ( n ) خطوة. وهذا، بطبيعة الحال، مستحيل دون القدرة على حساب f ( n ) في ذلك الزمن. عادةً ما تكون هذه النتائج صحيحة لجميع الدوال الطبيعية f، ولكنها ليست بالضرورة صحيحة للدوال f المصطنعة . لصياغتها بدقة، من الضروري وجود تعريف دقيق للدالة الطبيعية f التي تنطبق عليها النظرية. غالبًا ما تُستخدم الدوال القابلة للإنشاء في زمن محدد لتوفير هذا التعريف.

تُستخدم الدوال القابلة للإنشاء في الفضاء بشكل مماثل، على سبيل المثال في نظرية التسلسل الهرمي للفضاء .

تتضمن هذه المقالة مواد من موقع "constructible" على موقع "PlanetMath" ، وهو مرخص بموجب رخصة المشاع الإبداعي "نسب المصنف/المشاركة بالمثل" .