Apakah mahasiswa Alan Turing, Robin Gandy, menyatakan bahwa Charles Babbage tidak memiliki gagasan tentang mesin komputasi universal?

10

Robin Gandy adalah murid Alan Turing .

Gandy melakukan analisis Mesin Analitik Babbage (lihat 'Gandy - The Confluence of Ideas pada tahun 1936' dikutip dalam 'Herken, Rolf - Mesin Universal Turing - Sebuah Survei Setengah Abad . Springer Verlag') - dan mengatakan hal itu terjadi (lih. hlm. 52–53):

  1. Fungsi aritmatika +, -, ×, di mana - menunjukkan pengurangan "tepat" x - y = 0 jika y ≥ x.
  2. Urutan operasi apa pun adalah operasi.
  3. Iterasi suatu operasi (berulang n kali operasi P).
  4. Pengulangan bersyarat (pengulangan n kali suatu operasi P tergantung pada "keberhasilan" uji T).
  5. Transfer bersyarat (yaitu, "goto" bersyarat).

Lalu dia menyatakan

fungsi yang dapat dihitung dengan (1), (2), dan (4) adalah fungsi yang dapat dihitung oleh Turing.

(hlm. 53).

Lalu dia menyatakan:

... penekanannya pada pemrograman urutan operasi tetap yang dapat diperbaiki. Pentingnya dasar iterasi bersyarat dan transfer bersyarat untuk teori umum mesin hitung tidak diakui ...

Gandy p. 55

Saya menilai ruang lingkup klaim Gandy di sini. (Apakah itu benar atau salah). Dia tampaknya menyatakan bahwa meskipun Babbage tampaknya telah menemukan gagasan Turing Completeness (dapat mengekspresikan program apa pun menggunakan (1), (2) dan (4) - dia tidak memiliki gagasan tentang Fungsi yang Dapat Dihitung . (Mungkin Gandy mengatakan bahwa karena karya Babbage adalah sebelum karya Hilbert dan Godel , ia tidak memiliki alat matematika untuk mengikat definisi mesin komputasi universal.)

Pertanyaan saya adalah: Apakah mahasiswa Alan Turing Robin Gandy menyatakan bahwa Charles Babbage tidak memiliki gagasan tentang mesin komputasi universal?

hawkeye
sumber
2
Perhatikan ada juga sejarah sains dan matematika stackexchange hsm.stackexchange.com
usul
Saya agak bingung dengan halaman referensi. Jika semua nomor halaman adalah Gandy, mungkin akan lebih jelas untuk mengatakan "(Gandy, hal. 52-53)", (Gandy, hal. 53) ", dan (Gandy, hal. 55)". Untuk setiap kutipan yang dikutip dalam Rolf, atribusi dapat diperluas sebagai (Gandy, p. 5x; seperti dikutip dalam Rolf, p. Xx) ". " Cf. " adalah kependekan dari konferensi / konferensi Latin (" bandingkan "), yang berarti "lihat juga hal lain ini untuk perbandingan atau kontras", jadi tidak masuk akal untuk mengatakan bahwa untuk hal utama yang Anda kutip
Jacob C. mengatakan Reinstate Monica

Jawaban:

22

Tidak, sebaliknya. Kutipan Gandy ini tidak mengacu pada Babbage, tetapi pada beberapa proposal yang mengintervensi untuk komputasi gaya universal antara Babbage dan Turing. Gandy mengatakan proposal itu tidak memiliki pengakuan Babbage tentang pentingnya percabangan dan iterasi untuk perhitungan universal.


Dalam "The Confluence of Ideas in 1936" oleh Gandy, sebagaimana dicetak dalam buku "The Universal Turing Machine - A Half Century Survey", Bagian 2 adalah "Babbage and His Followers".

Di sini Gandy menekankan bahwa Babbage memahami dan menghormati "iterasi bersyarat" dan "pemindahan bersyarat", mis. Akhir p53 dan atas p54

Meskipun Babbage menyebutkan transfer bersyarat (67-68), ia, dengan rasa hormat alami untuk pemrograman terstruktur dengan baik, hanya menggunakan iterasi bersyarat [....] Ia menyatakan transfer bersyarat secara eksplisit (240), yang memungkinkan instruksi 'pergi ke' mungkin harus dieksekusi dengan membunyikan bel untuk memanggil petugas; ia memberi contoh penggunaannya (241).

(Di sini Gandy merujuk pada artikel oleh Menabrea 1842 tentang mesin Babbage, tetapi tampaknya menghubungkan gagasan itu dengan Babbage sendiri.)

Gandy lalu mengutip Babbage

Bahwa seluruh pengembangan dan operasi analisis sekarang mampu dieksekusi oleh permesinan.

dan menulis

Babbage, dalam karyanya tentang aljabar umum dan persamaan fungsional, telah menunjukkan kemampuannya untuk berpikir secara abstrak. Jika, kemudian, seseorang telah membawanya untuk berspekulasi (tidak sulit!) Pada apa yang bisa dilakukan dengan mesin abstrak, bebas dari batasan pada penyimpanannya, ia pasti akan menyetujui versi (berdasarkan Bagian 2.1. (1) - (5)) dari tesis Gereja.

Kemudian Gandy melanjutkan ke Bagian 2.3, "Perkembangan selanjutnya." Dia menulis

Penulis lain, yang peduli dengan mesin yang lebih praktis, merujuk pada karya Babbage. Contoh dari Ranwellell 1982 adalah: M. d'Ocagne [1922], L. Couffignal [1933], V. Bush 1936, HH Aiken 11964] (yang merupakan nota 1937 yang tidak diterbitkan). Tetapi penekanannya adalah pada pemrograman urutan operasi tetap aritmetika tetap. Pentingnya dasar iterasi bersyarat dan transfer bersyarat untuk teori umum mesin hitung tidak diakui, meskipun prinsip-prinsip dapat digunakan dalam konteks yang sangat khusus [....]

Akhirnya, Gandy menulis:

Kesimpulan. Babbage menegaskan apa yang sebenarnya merupakan versi dari tesis Gereja. Karyanya tidak pernah sepenuhnya dilupakan, tetapi kepentingan teoretisnya - kepentingannya, sehingga dapat dikatakan, sebagai perangkat lunak - tidak banyak dikenal [....]

usul
sumber