التشاكل الحسابي

في نظرية الحوسبة، مجموعتان${\displaystyle A,B}$تكون مجموعات الأعداد الطبيعية متماثلة حسابيًا أو متماثلة تكراريًا إذا وُجدت دالة قابلة للحساب كليًا وتقابلية .${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }$بحيث تكون صورة${\displaystyle f}$يقتصر على${\displaystyle A\subseteq \mathbb {N} }$يساوي${\displaystyle B\subseteq \mathbb {N} }$، أي${\displaystyle f(A)=B}$.

بالإضافة إلى ذلك، ترقيمان${\displaystyle \nu }$و${\displaystyle \mu }$تُسمى (من نفس مجموعة الكائنات) متماثلة حسابيًا إذا وُجد تقابل حسابي${\displaystyle f}$لهذا السبب.${\displaystyle \nu =\mu \circ f}$تؤدي الترقيمات المتماثلة حسابيًا إلى نفس مفهوم قابلية الحساب على مجموعة.

بحسب نظرية ميهيل للتماثل ، فإن علاقة التماثل الحسابي تتطابق مع علاقة الاختزال المتبادل أحادي النظير . ^{[ 1 ]}

• روغرز، هارتلي الابن (1987)، نظرية الدوال التكرارية والحسابية الفعالة (الطبعة الثانية  )، كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا، رقم ISBN 0-262-68052-1، MR 0886890 .