Mengapa fungsi yang dapat dihitung juga disebut fungsi rekursif?

23

Dalam teori komputabilitas, fungsi yang dapat dihitung juga disebut fungsi rekursif. Setidaknya pada pandangan pertama, mereka tidak memiliki kesamaan apa pun dengan apa yang Anda sebut "rekursif" dalam pemrograman sehari-hari (yaitu, fungsi yang menyebut dirinya sendiri).

Apa arti sebenarnya dari rekursif dalam konteks kemampuan komputasi? Mengapa fungsi-fungsi itu disebut "rekursif"?

Dengan kata lain: Apa hubungan antara dua makna "rekursif"?

computability terminology history Golo Roden
sumber

2

μ-fungsi rekursif

Thomas Klimpel

3

Mereka curang, karena mereka termasuk operator μ . Ini adalah operator minimisasi, tetapi tentu saja minimisasi tidak ada hubungannya dengan rekursi. Jadi sepertinya seseorang (Kleene) berpikir bahwa "rekursif" akan terdengar bagus, jadi dia menemukan alasan untuk menggunakan nama itu. Jauh kemudian, Robert Soare menjelaskan bahwa "computable" akan terdengar jauh lebih baik, dan bahwa "recursive" baru saja menjadi trik pemasaran pada masa-masa awal, dan semua orang setuju.

Thomas Klimpel

3

Bagaimana dengan fungsi rekursif primitif? Disalin dari wikipedia mereka didefinisikan sebagai

h (0, x_{1}, \dots, x_{k}) = f (x_{1}, \dots, x_{k})

$h(0,x_{1},\ldots ,x_{k})=f(x_{1},\ldots ,x_{k})$ dan

h (S (y), x_{1}, \dots, x_{k}) = g (y, h (y, x_{1}, \dots, x_{k}), x_{1}, \dots, x_{k})

$h(S(y),x_{1},\ldots ,x_{k})=g(y,h(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})$ . Itu adalah fungsi yang memanggil dirinya sendiri.

Hendrik Jan

3

@GoloRoden Perhatikan bahwa tag-description 'computability' (Anda menggunakannya untuk pertanyaan ini) mengatakan: "teori komputabilitas alias teori rekursi". Gödel disebut fungsi rekursif , tetapi istilah tersebut berkembang menjadi komputasi . Mungkin untuk menghindari kebingungan seperti milikmu. Orang yang mempelajari teori komputabilitas (intensif) cenderung menggunakan istilah teori rekursi lebih untuk 'menghormati' akarnya.

Auberon

1

karena mereka didefinisikan secara rekursif, yaitu " fungsi yang lebih kompleks didefinisikan dalam hal fungsi yang didefinisikan sebelumnya, lebih sederhana "

Nikos M.

13

Tetapkan beberapa fungsi dasar:

fungsi nol

$z e r o : N \to N : x \mapsto 0$ $zero: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto 0$
fungsi penerus

$s u c c : N \to N : x \mapsto x + 1$ $succ: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto x + 1$
fungsi proyeksi

p_{i}^{n} : N^{n} \to N : (x_{1}, x_{2}, \dots, x_{n}) \mapsto x_{i}

$p_i^n: \mathbb{N}^n \rightarrow \mathbb{N} : (x_1, x_2, \dots, x_n) \mapsto x_i$

Mulai sekarang saya akan menggunakan untuk menunjukkan $\bar{x_n}$ $(x_1, x_2, \dots, x_n)$

Tentukan komposisi:

Fungsi yang diberikan

masing-masing dengan tanda tangan $g_1, g_2, \dots, g_m$ $\mathbb{N}^k \rightarrow \mathbb{N}$
$f : \mathbb{N}^m \rightarrow \mathbb{N}$

Bangun fungsi berikut:

\begin{aligned} h : N^{k} \to N : \bar{x_{k}} \mapsto h (\bar{x_{k}}) = f ( & g_{1} (\bar{x_{k}}), g_{2} (\bar{x_{k}}), \dots, g_{m} (\bar{x_{k}})) \end{aligned}

$\begin{align} h: \mathbb{N}^k \rightarrow \mathbb{N}: \bar{x_k} \mapsto h(\bar{x_k}) = f ( & g_1(\bar{x_k}), g_2(\bar{x_k}), \dots, g_m(\bar{x_k}) ) \end{align}$

Tetapkan rekursi primitif:

Fungsi yang diberikan

$f: \mathbb{N}^k \rightarrow \mathbb{N}$
$g: \mathbb{N}^{k+2} \rightarrow \mathbb{N}$

Bangun fungsi berikut (secara terpisah):

h : N^{k + 1} \to N : (\bar{x_{k}}, y + 1) \mapsto {\begin{cases} f (\bar{x_{k}}), & y + 1 = 0 \\ g (\bar{x_{k}}, y, h (\bar{x_{k}}, y)), & y + 1 > 0 \end{cases}

$h : \mathbb{N}^{k+1} \rightarrow \mathbb{N} : \\ (\bar{x_k}, y + 1) \mapsto \begin{cases} f(\bar{x_k}), & y + 1 = 0 \\ g (\bar{x_k}, y, h(\bar{x_k}, y)), & y + 1 > 0 \end{cases}$

Semua fungsi yang dapat dibuat menggunakan komposisi dan rekursi primitif pada fungsi dasar , disebut primitif rekursif . Disebut demikian menurut definisi. Sementara tautan dengan fungsi yang menyebut dirinya ada, tidak perlu mencoba dan menautkannya satu sama lain. Anda mungkin menganggap rekursi sebagai homonim.

Definisi dan konstruksi di atas dibangun oleh Gödel (beberapa orang lain juga terlibat) dalam upaya untuk menangkap semua fungsi yang dapat dihitung yaitu ada Mesin Turing untuk fungsi tersebut. Perhatikan bahwa konsep Mesin Turing belum dijelaskan, atau setidaknya sangat kabur.

(Un) untungnya, seseorang bernama Ackermann datang dan mendefinisikan fungsi berikut:

$Ack : \mathbb{N}^2 \rightarrow \mathbb{N}$
$Ack(0, y) = y+1$
$Ack(x+1, 0) = Ack(x, 1)$
$Ack(x+1, y+1) = Ack(x, Ack(x+1,y))$

$Ack$

Minimalisasi tanpa batas

$g : \mathbb{N}^k \rightarrow \mathbb{N}$
$\left[f(\bar{x_k}, y) = 0 \text{ AND } \\f(\bar{x_k}, z) \text{ is defined } \forall z < y \text{ AND } \\f(\bar{x_k}, z)\neq 0\right]$

$g(\bar{x_k}) = y$

$g(\bar{x_k})$

$g((x_1, x_2, \dots, x_k))$ $f$

Semua fungsi yang dapat dibangun dengan semua konstruksi yang didefinisikan di atas disebut rekursif . Sekali lagi, nama rekursif hanya berdasarkan definisi, dan itu tidak selalu memiliki korelasi dengan fungsi yang menyebut diri mereka. Sungguh, anggap itu homonim.

Fungsi rekursif dapat berupa fungsi rekursif parsial $Ack$

$Ack$

Jika Anda tertarik, Anda bisa mencoba membuat kelas Gödel lebih besar. Anda dapat mencoba menentukan 'kebalikan' dari minimisasi tanpa batas. Artinya, maksimalisasi tanpa batas yaitu fungsi yang menemukan akar terbesar. Namun, Anda mungkin menemukan bahwa penghitungan fungsi itu sulit (tidak mungkin). Anda dapat membaca Masalah Sibuk Berang-berang , yang mencoba menerapkan maksimalisasi tanpa batas.

Auberon
sumber

4

Saya tahu menyadari definisi yang diberikan tidak benar-benar menjawab pertanyaan, tetapi jawaban saya menjelaskan evolusi rekursi / teori komputabilitas, semacam. Mungkin layak dibaca.

Auberon

Saya suka, terima kasih atas upaya Anda :-)

Golo Roden

h ((x_{1}, x_{2}, . . ., x_{k}), 0) = f ((x_{1}, x_{2}, . . ., x_{k}))

$h((x_1, x_2, ..., x_k), 0) = f((x_1, x_2, ..., x_k))$

h ((x_{1}, x_{2}, . . ., x_{k}, 0))

$h((x_1, x_2, ..., x_k, 0))$ . Juga, tidak ada klausa sebelum klausa poin poin berikutnya.

Eric Towers

2

μ

$\mu$

1

Ada beberapa pernyataan yang salah dalam jawaban Anda. Anda seharusnya tidak mengarang riwayat untuk sebuah jawaban.

Kaveh

17

Para pendiri teori komputasi adalah ahli matematika. Mereka menemukan apa yang sekarang disebut teori komputabilitas sebelum ada komputer. Apa cara matematikawan mendefinisikan fungsi yang dapat dihitung? Dengan definisi rekursif!

Jadi ada fungsi rekursif sebelum ada model komputasi lain seperti mesin Turing atau kalkulus lambda atau mesin register. Jadi orang menyebut fungsi ini sebagai fungsi rekursif. Fakta bahwa mereka ternyata persis seperti yang dapat dihitung oleh mesin Turing dan model lainnya adalah peristiwa selanjutnya (kebanyakan dibuktikan oleh Kleene).

$\mu$ fungsi -recursive dan Herbrand-Gödel fungsi rekursif umum yang melakukan capture semua fungsi dihitung (dengan asumsi tesis Gereja). Church mengklaim bahwa model kalkulus lambda menangkap semua fungsi yang dapat dihitung. Banyak orang, dan khususnya Gödel, tidak yakin bahwa ini menangkap semua fungsi yang dapat dihitung. Sampai analisis Turing tentang perhitungan dan pengenalan model mesinnya.

Nama bidang yang digunakan untuk teori rekursi. Namun telah ada dorongan yang berhasil dalam beberapa dekade terakhir untuk mengubah nama menjadi sesuatu yang lebih menarik dari teori rekursi menjadi sesuatu yang lebih banyak keahlian komputer (vs matematika). Akibatnya lapangan sekarang disebut teori komputabilitas. Namun jika Anda melihat buku, makalah, konferensi, dll. Di awal dekade mereka disebut teori rekursi dan bukan teori komputabilitas. Bahkan judul buku Soare sendiri tahun 1987 (yang merupakan orang utama di balik dorongan untuk mengubah nama menjadi teori komputabilitas) adalah "Recursively Enumerable Sets and Degrees".

Jika Anda ingin tahu lebih banyak tentang sejarah yang menyenangkan dan tempat yang baik untuk membaca tentang itu adalah bab pertama dari Teori Rekursi Klasik oleh Odifreddi.

Kaveh
sumber

7

Robert Soare menulis esai tentang masalah ini. Menurutnya, istilah fungsi rekursif (umum) diciptakan oleh Gödel, yang mendefinisikannya menggunakan semacam rekursi timbal balik. Nama macet, meskipun kemudian definisi setara lainnya ditemukan.

Untuk informasi lebih lanjut, saya merekomendasikan esai Soare.

Yuval Filmus
sumber

0

bukannya memberikan komentar panjang memutuskan untuk menambahkan jawaban:

Karena mereka didefinisikan secara rekursif , yaitu " fungsi yang lebih kompleks didefinisikan dalam hal fungsi yang didefinisikan sebelumnya, lebih sederhana "

Jenis prosedur iteratif atau tambahan ini menciptakan fungsi yang terdefinisi dengan baik (dalam pengertian matematika)

Ini adalah makna dari sifat recursiveness dalam bahasa matematika. Lihat di bawah bagaimana ini berhubungan dengan rekursi dalam bahasa pemrograman.

Bandingkan prosedur ini dengan teknik dan metode seperti induksi (matematika) yang juga merupakan contoh ketepatan dalam matematika.

Pemrograman memiliki nada matematika serta teknik.

Prosedur (biasanya konstruktif) ini juga disebut sebagai " bootstrap " dalam bahasa Sistem Operasi.

Namun sebuah runtime rekursi fungsi yang sama (yaitu caling sendiri selama runtime-nya ), karena harus (hmm, harus) terjadi pada nilai-nilai yang sudah dihitung (atau argumen), atau dengan kata lain, dalam bagian dari hasil set sudah dihitung , juga rekursif dalam arti di atas, yaitu " fungsi yang didefinisikan sebelumnya ditentukan (dan nilainya) "

Lain tidak terdefinisi dengan baik, dan mengarah ke hal-hal seperti Stack Overflow :))))

Untuk memberikan contoh lebih lanjut dari Sistem Operasi, rekursi runtime (memanggil dirinya sendiri) dapat diambil sebagai analog dari sistem operasi yang me-reboot setelah pembaruan tertentu (misalnya pembaruan inti). Banyak OS melakukan prosedur berikut:

boot awal untuk memuat rutin tingkat rendah (mis. I / O)
lakukan pembaruan yang diperlukan (menggunakan rutinitas tingkat rendah)
boot ulang (secara efektif, memanggil kembali dirinya sendiri), tetapi kali ini memuat rutinitas yang lebih kompleks (atau bahkan seluruh sistem)

Jawaban indah Auberon menunjukkan prosedur semacam ini secara lebih rinci.

Nikos M.
sumber

Mengapa fungsi yang dapat dihitung juga disebut fungsi rekursif?

Jawaban: