وظيفة السودان

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

في عام 1926، افترض ديفيد هيلبرت أن كل دالة قابلة للحساب هي دالة بدائية تكرارية. وقد دحض هذا الافتراض غابرييل سودان وويلهلم أكرمان - وكلاهما من تلاميذه - باستخدام دوال مختلفة نُشرت تباعًا: سودان في عام 1927، ^{[ 1 ]} وأكرمان في عام 1928. ^{[ 2 ]}

تُعد دالة السودان أقدم مثال منشور لدالة تكرارية ليست تكرارية بدائية. ^{[ 3 ]}

${\displaystyle {\begin{array}{lll}F_{0}(x,y)&=x+y\\F_{n+1}(x,0)&=x&{\text{if}}n\geq 0\\F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1)&{\text{if }}n\geq 0\\\end{صفيف}}}$

يمكن كتابة المعادلة الأخيرة بشكل مكافئ على النحو التالي

${\displaystyle {\begin{array}{lll}F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{0}(F_{n+1}(x,y),y+1))\\\end{array}}}$[ ^{4 ]​}

يمكن استخدام هذه المعادلات كقواعد لنظام إعادة كتابة المصطلحات (TRS) .

الدالة المعممة${\displaystyle F(x,y,n){\stackrel {\mathrm {def} }{=}}F_{n}(x,y)}$يؤدي ذلك إلى إعادة كتابة القواعد

${\displaystyle {\begin{array}{lll}{\text{(r1)}}&F(x,y,0)&\rightarrow x+y\\{\text{(r2)}}&F(x,0,n+1)&\rightarrow x\\{\text{(r3)}}&F(x,y+1,n+1)&\rightarrow F(F(x,y,n+1),F(F(x,y,n+1),y+1,0),n)\\\end{array}}}$

في كل خطوة اختزال، تتم إعادة كتابة أحدث ظهور داخلي لـ F، عن طريق تطبيق إحدى القواعد (r1) - (r3).

يقدم كالود (1988) مثالاً على ذلك : حساب${\displaystyle F(2,2,1)\rightarrow _{*}12}$[ ^{5 ]​}

تسلسل الاختزال هو ^{[ 6 ]}

${\displaystyle {\underline {F(2,2,1)}}}$

${\displaystyle \rightarrow _{r3}F(F(2,1,1),F({\underline {F(2,1,1)}},2,0),0)}$

${\displaystyle \rightarrow _{r3}F(F(2,1,1),F(F(F(2,0,1),F({\underline {F(2,0,1)}},1,0),0),2,0),0)}$

${\displaystyle \rightarrow _{r2}F(F(2,1,1),F(F(F(2,0,1),{\underline {F(2,1,0)}},0),2,0),0)}$

${\displaystyle \rightarrow _{r1}F(F(2,1,1),F(F({\underline {F(2,0,1)}},3,0),2,0),0)}$

${\displaystyle \rightarrow _{r2}F(F(2,1,1),F({\underline {F(2,3,0)}},2,0),0)}$

${\displaystyle \rightarrow _{r1}F(F(2,1,1),{\underline {F(5,2,0)}},0)}$

${\displaystyle \rightarrow _{r1}F({\underline {F(2,1,1)}},7,0)}$

${\displaystyle \rightarrow _{r3}F(F(F(2,0,1),F({\underline {F(2,0,1)}},1,0),0),7,0)}$

${\displaystyle \rightarrow _{r2}F(F(F(2,0,1),{\underline {F(2,1,0)}},0),7,0)}$

${\displaystyle \rightarrow _{r1}F(F({\underline {F(2,0,1)}},3,0),7,0)}$

${\displaystyle \rightarrow _{r2}F({\underline {F(2,3,0)}},7,0)}$

${\displaystyle \rightarrow _{r1}{\underline {F(5,7,0)}}}$

${\displaystyle \rightarrow _{r1}12}$

• شفرة روزيتا (23 يوليو 2024). "وظيفة السودان" .

• OEIS: A260003 ، A260004