Smn-теорема
З Вікіпедії, безкоштовно encyclopedia
В теорії обчислень smn-теорема (англ. smn theorem; також відома як лема про трансляцію, теорема параметрів, чи теорема параметризації) — основне досягнення в сфері мов програмування (і, більш загально, Геделівських нумерацій обчислюваних функцій). Вперше була доведена Стівеном Коулом Кліні у 1943.
На практиці теорема означає, що для заданої мови програмування та додатних цілих m та n існує певний алгоритм, який оперує кодом програм з m+n вільними змінними. Цей алгоритм ефективно прив'язує m даних значень до перших m вільних змінних в програмі і залишає інші вільними.