Lý thuyết tính toán

Lý thuyết tính toán, còn được gọi là lý thuyết đệ quy, là một nhánh của logic toán học, của khoa học máy tính và của lý thuyết tính toán (theory of computation) bắt nguồn từ những năm 1930 với nghiên cứu về các hàm tính toán và độ Turing. Lĩnh vực này đã được mở rộng để bao gồm các nghiên cứu về tính toán tổng quát và tính xác định. Trong các lĩnh vực này, lý thuyết đệ quy trùng lặp với lý thuyết chứng minh và lý thuyết tập hợp mô tả hiệu quả.

Các câu hỏi cơ bản được lý thuyết đệ quy nêu ra bao gồm:

  • Đối với một hàm trên các số tự nhiên có thể tính toán được, có ý nghĩa gì?
  • Làm thế nào các hàm mà không tính toán được phân loại thành một hệ thống phân cấp dựa trên mức độ không tính toán được của chúng?

Mặc dù có sự chồng chéo đáng kể về kiến thức và phương pháp, các nhà lý thuyết đệ quy toán học nghiên cứu lý thuyết về khả năng tính toán tương đối, các khái niệm giảm thiểu và cấu trúc mức độ; những người trong lĩnh vực khoa học máy tính tập trung vào lý thuyết về thứ bậc phụ, phương pháp chính thức và ngôn ngữ chính thức.

Tập hợp tính toán được và không tính toán được

Lý thuyết đệ quy bắt nguồn từ những năm 1930, với công trình của Kurt Gödel, Alonzo Church, Rózsa Péter, Alan Turing, Stephen Kleene và Emil Post.[1][2]

Các kết quả cơ bản mà các nhà nghiên cứu thu được đã thiết lập tính toán Turing như là sự chính thức hóa chính xác của ý tưởng không chính thức về tính toán hiệu quả. Những kết quả này đã khiến Stephen Kleene (1952) đặt ra hai tên "Luận án của Church" (Kleene 1952: 300) và "Luận án của Turing" (Kleene 1952: 376). Ngày nay, những điều này thường được coi là một giả thuyết duy nhất, luận án Church-Turing, nói rằng bất kỳ hàm nào có thể tính toán được bằng thuật toán là một hàm tính toán được. Mặc dù ban đầu còn hoài nghi, đến năm 1946, Gôdel đã lập luận ủng hộ luận điểm này:

Ghi chú

  1. ^ Many of these foundational papers are collected in The Undecidable (1965) edited by Martin Davis.
  2. ^ Soare, Robert Irving (ngày 22 tháng 12 năm 2011). “Computability Theory and Applications: The Art of Classical Computability” (PDF). Department of Mathematics. University of Chicago. Bản gốc (PDF) lưu trữ ngày 30 tháng 6 năm 2022. Truy cập ngày 23 tháng 8 năm 2017.

Read other articles:

Bahasa Latin Kuno

Untuk teks Alkitabiah Bahasa Latin Kuno, lihat Vetus Latina. PemberitahuanTemplat ini mendeteksi bahwa artikel bahasa ini masih belum dinilai kualitasnya oleh ProyekWiki Bahasa dan ProyekWiki terkait dengan subjek. Terjadi [[false positive]]? Silakan laporkan kesalahan ini. 06.14, Sabtu, 30 Maret, 2024 (UTC) • hapus singgahan Sebanyak 1.305 artikel belum dinilai Artikel ini belum dinilai oleh ProyekWiki Bahasa Cari artikel bahasa  Cari berdasarkan kode ISO 639 (Uji coba)  Kol...

 

EISCAT

Radar systems used to study the interaction between the Sun and the Earth This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: EISCAT – news · newspapers · books · scholar · JSTOR (July 2022) (Learn how and when to remove this template message) EISCAT Sodankylä receiver antenna (diameter 32m) after conversion to 224 MHz (crossed dipole replaced Cassegr...

 

SMA Negeri 6 Semarang

Artikel ini membutuhkan rujukan tambahan agar kualitasnya dapat dipastikan. Mohon bantu kami mengembangkan artikel ini dengan cara menambahkan rujukan ke sumber tepercaya. Pernyataan tak bersumber bisa saja dipertentangkan dan dihapus.Cari sumber: SMA Negeri 6 Semarang – berita · surat kabar · buku · cendekiawan · JSTOR SMA Negeri 6 SemarangInformasiDidirikan6 Agustus 1979JenisSekolah NegeriNomor Statistik Sekolah301036307006Kepala SekolahDrs. Mul...

Kabupaten Temanggung

Untuk desa bernama sama di Kabupaten Magelang, lihat Temanggung, Kaliangkrik, Magelang. Temanggung beralih ke halaman ini. Untuk kegunaan lain, lihat Temanggung (disambiguasi). Kabupaten TemanggungKabupatenTranskripsi bahasa daerah • Hanacarakaꦠꦼꦩꦔ꧀ꦒꦸꦁ • Pegonتماڠڬوڠ • Alfabet JawaTemanggungDari kiri; ke kanan: Kuda lumping Temanggung, Pertani panen tembakau, View Sumbing Dari Embung kledung, Tradisi Nyadran Tenong, Candi Pringap...

 

522 Martir Spanyol

Upacara diadakan oleh Kardinal Angelo Amato di Tarragona, Spanyol Bagian dari sebuah serial tentangPenganiayaan GerejaKatolik di era modern Ikhtisar Sejarah Penganiayaan terhadap Umat Kristiani Penganiayaan Gereja Katolik 1939–1958 Pemberantasan Gereja Katolik di bawah Stalinisme Penganiayaan Katolik Timur Penganiayaan terhadap umat Katolik di era modern Kekaisaran Romawi Penganiayaan terhadap umat Kristiani di Kekaisaran Romawi Penindasan Diokletianus Kekaisaran Neo-Persia Penaklukan Yerus...

 

Resolusi 854 Dewan Keamanan Perserikatan Bangsa-Bangsa

Resolusi 854Dewan Keamanan PBBAbkhaziaTanggal6 Agustus 1993Sidang no.3,261KodeS/RES/854 (Dokumen)TopikAbkhazia, GeorgiaRingkasan hasil15 mendukungTidak ada menentangTidak ada abstainHasilDiadopsiKomposisi Dewan KeamananAnggota tetap Tiongkok Prancis Rusia Britania Raya Amerika SerikatAnggota tidak tetap Brasil Tanjung Verde Djibouti Spanyol Hungaria Jepang Maroko Selandia Baru Pakistan Venezuela Resolusi 854 ...

Souleymane Diawara

Souleymane Diawara Diawara with MarseilleInformasi pribadiNama lengkap Souleymane DiawaraTanggal lahir 24 Desember 1978 (umur 45)Tempat lahir Dakar, SenegalTinggi 1,87 m (6 ft 1+1⁄2 in)Posisi bermain BekInformasi klubKlub saat ini MarseilleNomor 21Karier senior*Tahun Tim Tampil (Gol)1998–2003 Le Havre 104 (2)2003–2006 Sochaux 84 (4)2006–2007 Charlton Athletic 23 (0)2007–2009 Bordeaux 63 (2)2009– Marseille 87 (5)Tim nasional‡2002– Senegal 45 (0) * Penam...

 

Ervin Johnson

American basketball player (born 1967) For the former Los Angeles Lakers player named Earvin Johnson, see Magic Johnson. Ervin JohnsonJohnson in 2010Personal informationBorn (1967-12-21) December 21, 1967 (age 56)New Orleans, Louisiana, U.S.NationalityAmericanListed height6 ft 11 in (2.11 m)Listed weight245 lb (111 kg)Career informationHigh schoolBlock (Jonesville, Louisiana)CollegeNew Orleans (1989–1993)NBA draft1993: 1st round, 23rd overall pickSelected by th...

 

Daftar stasiun televisi di Papua Tengah

Penyuntingan Artikel oleh pengguna baru atau anonim untuk saat ini tidak diizinkan.Lihat kebijakan pelindungan dan log pelindungan untuk informasi selengkapnya. Jika Anda tidak dapat menyunting Artikel ini dan Anda ingin melakukannya, Anda dapat memohon permintaan penyuntingan, diskusikan perubahan yang ingin dilakukan di halaman pembicaraan, memohon untuk melepaskan pelindungan, masuk, atau buatlah sebuah akun. Berikut ini adalah daftar stasiun televisi di Papua Tengah. Catatan: Kecuali pada...

Військово-музичне управління Збройних сил України

Військово-музичне управління Збройних сил України Тип військове формуванняЗасновано 1992Країна  Україна Емблема управління Військово-музичне управління Збройних сил України — структурний підрозділ Генерального штабу Збройних сил України призначений для планува...

 

13.ª edición de los Premios Óscar

13.ª edición de los Premios Óscar Premio a La excelencia en logros cinematográficosOtorgado por Academia de las Artes y las Ciencias Cinematográficas (AMPAS)Fecha 27 de febrero de 1941Ubicación Biltmore Hotel, Los Ángeles, CaliforniaEstados UnidosAnfitrión Bob HopeDestacadoMás premios El ladrón de Bagdad (3)Más nominaciones Rebecca (11) Cronología 12.ª edición 13.ª edición de los Premios Óscar 14.ª edición Sitio web oficial[editar datos en Wikidata] La 13.ª edici...

 

List of college athletic programs in South Dakota

This is a list of college athletics programs in the U.S. state of South Dakota. Notes: This list is in a tabular format, with columns arranged in the following order, from left to right: Athletic team description (short school name and nickname), with a link to the school's athletic program article if it exists. When only one nickname is listed, it is used for teams of both sexes. (Note that in recent years, many schools have chosen to use the same nickname for men's and women's teams even w...

Донецкая возвышенность

Донецкая возвышенностьукр. Донецька височина Расположение 48°15′47″ с. ш. 38°52′48″ в. д.HGЯO Страна Украина Донецкая возвышенность Донецкая возвышенность (укр. Донецька височина) находится в юго-восточной Украине, в Донецкой, Луганской и частично Харьковско�...

 

DEFCON

Alert posture used by the United States Armed Forces For other uses, see Defcon (disambiguation). DEFCON levels The defense readiness condition (DEFCON) is an alert state used by the United States Armed Forces.[1][2] For security reasons, the US military does not announce a DEFCON level to the public.[1] The DEFCON system was developed by the Joint Chiefs of Staff (JCS) and unified and specified combatant commands.[3] It prescribes five graduated levels of read...

 

Fairview Township, Luzerne County, Pennsylvania

For other Pennsylvania townships with similar names, see Fairview Township, Pennsylvania (disambiguation). Township in Pennsylvania, United StatesFairview Township, Luzerne County, PennsylvaniaTownshipGlen Summit Chapel in August 2011Location of Fairview Township in Luzerne County, PennsylvaniaLocation of Luzere County in PennsylvaniaCountryUnited StatesStatePennsylvaniaCountyLuzerneArea[1] • Total9.44 sq mi (24.46 km2) • Land9.43 sq m...

AFC Champions League 2015

AFC Champions League 2015 Competizione AFC Champions League Sport Calcio Edizione 34ª Organizzatore AFC Date dal 4 febbraio 2015al 21 novembre 2015 Partecipanti 49 Nazioni 21 Sito web AFC Champions League Risultati Vincitore  Guangzhou E.(2º titolo) Secondo  Al-Ahli Statistiche Miglior marcatore Ricardo Goulart (8) Incontri disputati 142 Gol segnati 391 (2,75 per incontro) Cronologia della competizione 2014 2016 Manuale La AFC Champions League 2015 è stata la 3...

 

AIM-4 Falcon

Hughes AIM-4 Falcon adalah sebuah peluru kendali / rudal udara-ke-udara dipandu yang pertama operasional dari Angkatan Udara Amerika Serikat. Pembangunan dimulai pada tahun 1946, senjata pertama kali diuji pada tahun 1949. Rudal itu memasuki layanan dengan USAF pada tahun 1956. Referensi The history of the Falcon missile, and its various configurations, is examined in Gart, Jason H. Electronics and Aerospace Industry in Cold War Arizona, 1945-1968: Motorola, Hughes Aircraft, Goodyear Aircraf...

 

Austin Stories

American TV series or program Austin StoriesCreated byJames Jones[1]Starring Laura House Howard Kremer Brad Chip Pope[2] Country of originUnited StatesOriginal languageEnglishNo. of seasons1No. of episodes12ProductionExecutive producersJames JonesHoward KremerCamera setupSingle-cameraRunning time30 minutesOriginal releaseNetworkMTVReleaseSeptember 10, 1997 (1997-09-10) –January 7, 1998 (1998-01-07) Austin Stories is an American sitcom that aired on MTV from S...

A Sea of Her Own

A Sea of Her OwnPoster promosiGenreDrama sejarah KeluargaDitulis olehKim Mi-Jung Lee Jung-DaeSutradaraHan Chul-KyungPemeranOh Seung-ahKim Joo-YongHan Yoo-yiChoi Sung-JaeNegara asalKorea SelatanBahasa asliKoreaJmlh. episode120ProduksiDurasiSenin sampai Jumat pada pukul 09:00 (WSK)Rilis asliJaringanKorean Broadcasting SystemFormat gambar480i (SDTV) 1080i (HDTV)Rilis27 Februari 2017 (2017-02-27) – () TV Novel: A Sea of Her Own (Hangul: TV소설 그 여자의 바다;...

 

Rouffy

Cet article est une ébauche concernant une commune de la Marne. Vous pouvez partager vos connaissances en l’améliorant (comment ?). Le bandeau {{ébauche}} peut être enlevé et l’article évalué comme étant au stade « Bon début » quand il comporte assez de renseignements encyclopédiques concernant la commune. Si vous avez un doute, l’atelier de lecture du projet Communes de France est à votre disposition pour vous aider. Consultez également la page d’aide à...