Real computation

In computability theory, the theory of real computation deals with hypothetical computing machines using infinite-precision real numbers. They are given this name because they operate on the set of real numbers. Within this theory, it is possible to prove interesting statements such as "The complement of the Mandelbrot set is only partially decidable."

These hypothetical computing machines can be viewed as idealised analog computers which operate on real numbers, whereas digital computers are limited to computable numbers. They may be further subdivided into differential and algebraic models (digital computers, in this context, should be thought of as topological, at least insofar as their operation on computable reals is concerned^[1]). Depending on the model chosen, this may enable real computers to solve problems that are inextricable on digital computers (For example, Hava Siegelmann's neural nets can have noncomputable real weights, making them able to compute nonrecursive languages.) or vice versa. (Claude Shannon's idealized analog computer can only solve algebraic differential equations, while a digital computer can solve some transcendental equations as well. However this comparison is not entirely fair since in Claude Shannon's idealized analog computer computations are immediately done; i.e. computation is done in real time. Shannon's model can be adapted to cope with this problem.)^[2]

A canonical model of computation over the reals is Blum–Shub–Smale machine (BSS).

If real computation were physically realizable, one could use it to solve NP-complete problems, and even #P-complete problems, in polynomial time. Unlimited precision real numbers in the physical universe are prohibited by the holographic principle and the Bekenstein bound.^[3]

References

^ Klaus Weihrauch (1995). A Simple Introduction to Computable Analysis.
^ O. Bournez; M. L. Campagnolo; D. S. Graça & E. Hainry (Jun 2007). "Polynomial differential equations compute all real computable functions on computable compact intervals". Journal of Complexity. 23 (3): 317–335. doi:10.1016/j.jco.2006.12.005. hdl:10400.1/1011.
^ Scott Aaronson, NP-complete Problems and Physical Reality, ACM SIGACT News, Vol. 36, No. 1. (March 2005), pp. 30–52.

Read other articles:

Coffee with D

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. Coffee with DNama lainHindi कॉफ़ी विथ डी SutradaraVishal MishraProduserVinod RamaniSkenarioAabhar Dadhich Aabhar DadhichCeritaVishal MishraPemeran Sunil Grover Zakir Hussain Dipannita Sharma Anjana Sukhani Rajesh Sharma Penat...

Ruby on Rails

Este artículo o sección necesita ser wikificado, por favor, edítalo para que cumpla con las convenciones de estilo.Este aviso fue puesto el 30 de octubre de 2021. «RoR» redirige aquí. Para Rigs of Rods, véase Rigs of Rods. Ruby on Rails Página de bienvenida tras la instalaciónInformación generalTipo de programa framework de aplicaciones webDesarrollador Rails Core TeamLanzamiento inicial 13 de diciembre de 2005Licencia Licencia MITInformación técnicaProgramado en RubyVersionesÚl...

Vita (merek)

Untuk perusahaan dari merek tersebut, lihat Vitasoy.VitaJenisMinuman, makananProdusenVitasoyNegara asalHong KongDiperkenalkan1976Situs webwww.vitavitasoy.com Vita (Hanzi: 維他) adalah sebuah nama merek dari berbagai jenis minuman dan makanan yang diproduksi oleh perusahaan minuman yang berbasis di Hong Kong Vitasoy.[1] Mula-mula diperkenalkan pada 1976 sebagai serangkaian minuman rasa buah berbeda, merek tersebut kemudian diperluas menjadi meliputi minuman teh lemon siap saji pe...

Batocera rufomaculata

Batocera rufomaculata Klasifikasi ilmiah Kerajaan: Animalia Filum: Arthropoda Kelas: Insecta Ordo: Coleoptera Famili: Cerambycidae Subfamili: Lamiinae Tribus: Batocerini Genus: Batocera Spesies: Batocera rufomaculata Batocera rufomaculata Batocera rufomaculata adalah spesies kumbang tanduk panjang yang tergolong famili Cerambycidae. Spesies ini juga merupakan bagian dari genus Batocera, ordo Coleoptera, kelas Insecta, filum Arthropoda, dan kingdom Animalia. Larva kumbang ini biasanya mengebo...

العلاقات الأردنية المالطية

العلاقات الأردنية المالطية الأردن مالطا الأردن مالطا تعديل مصدري - تعديل العلاقات الأردنية المالطية هي العلاقات الثنائية التي تجمع بين الأردن ومالطا.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارنة الأردن ...

Pedro de Mendoza

Spanish conquistador (1499–1537) Pedro de MendozaMonument to Pedro de Mendoza, Parque Lezama, neighborhood of San Telmo, Buenos Aires, Argentina.Bornc. 1499Guadix, Granada, Spain[1]Died23 June 1537(1537-06-23) (aged 49–50)Atlantic OceanOccupationSpanish conquistador Pedro de Mendoza (Spanish pronunciation: [ˈpeðɾo ðe menˈdoθa]) (c. 1499 – June 23, 1537) was a Spanish conquistador, soldier and explorer, and the first adelantado of New Andalusia. Setting s...

Anak tentara

Artikel atau sebagian dari artikel ini mungkin diterjemahkan dari Military brat di en.wikipedia.org. Isinya masih belum akurat, karena bagian yang diterjemahkan masih perlu diperhalus dan disempurnakan. Jika Anda menguasai bahasa aslinya, harap pertimbangkan untuk menelusuri referensinya dan menyempurnakan terjemahan ini. Anda juga dapat ikut bergotong royong pada ProyekWiki Perbaikan Terjemahan. (Pesan ini dapat dihapus jika terjemahan dirasa sudah cukup tepat. Lihat pula: panduan penerjemah...

568th Air Defense Group

568th Air Defense Group5th Fighter-Interceptor Squadron, F-86D Sabre at McGuire AFB[a]Active1945–1946; 1952–1954Country United StatesBranch United States Air ForceTypeFighter interceptorRoleAir defenseMilitary unit The 568th Air Defense Group is a disbanded United States Air Force organization. Its last assignment was with Air Defense Command (ADC)'s 4709th Air Defense Wing at McGuire Air Force Base, New Jersey, where it was inactivated in 1954. The group was originally...

Человек прямоходящий

† Человек прямоходящий Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:Синапсиды�...

Daftar Wakil Wali Kota Padang Panjang

Wakil Wali Kota Padang PanjangLambang Kota Padang PanjangPetahanaJabatan Lowongsejak 9 Oktober 2023KediamanRumah Dinas Wakil Wali Kota Padang PanjangMasa jabatan5 tahun, sesudahnya dapat dipilih kembali sekaliDibentuk2003Pejabat pertamaAdirozalSitus webwww.padangpanjang.go.id Wakil Wali Kota Padang Panjang adalah politisi yang dipilih bersama Wali Kota Padang Panjang untuk membantu tugas Wali kota dalam mengatur dan mengelola Pemerintah Kota Padang Panjang, sebagai bagian dari sistem pen...

Шоу, Джордж Бернард

В Википедии есть статьи о других людях с такой фамилией, см. Шоу; Шоу, Джордж. Бернард Шоуангл. Bernard Shaw 1909 год Имя при рождении George Bernard Shaw Дата рождения 26 июля 1856(1856-07-26)[1][2][…] Место рождения Дублин, Соединённое Королевство Великобритании и Ирландии Дата смерти 2 н�...

2016 United States presidential election in Rhode Island

Election in Rhode Island Main article: 2016 United States presidential election 2016 United States presidential election in Rhode Island ← 2012 November 8, 2016 2020 → Turnout60.2%[1] 0.6 pp Nominee Hillary Clinton Donald Trump Party Democratic Republican Home state New York New York Running mate Tim Kaine Mike Pence Electoral vote 4 0 Popular vote 252,525 180,543 Percentage 54.41% 38.90% County results Municipality results Clinton ...

乌克兰总理

烏克蘭總理Прем'єр-міністр України烏克蘭國徽現任杰尼斯·什米加尔自2020年3月4日任命者烏克蘭總統任期總統任命首任維托爾德·福金设立1991年11月后继职位無网站www.kmu.gov.ua/control/en/（英文）乌克兰乌克兰政府与政治系列条目宪法政府总统弗拉基米尔·泽连斯基總統辦公室国家安全与国防事务委员会总统代表（英语：Representatives of the President of Ukraine）总...

List of Yu-Gi-Oh! GX characters

This is the list of characters in the Yu-Gi-Oh! GX animated series. The official English anime and the English manga by VIZ Media have changed character names. Main characters Jaden Yuki / Judai Yuki (遊城十代, Yūki Jūdai) Voiced by: KENN (Japanese); Matthew Charles (English)[1] The main protagonist of the series. He is described as an energetic, passionate and optimistic boy who comes to Duel Academy to learn to become the new King of Games. He is shown to be a very talen...

2016–17 NBL season

Australian basketball season 2016–17 NBL seasonLeagueNational Basketball LeagueSeason2016–17Dates6 October 2016 – 5 March 2017Number of teams8TV partner(s)Australia: Fox Sports SBS New Zealand: Sky Sport Online: NBL TV Regular seasonSeason championsAdelaide 36ersSeason MVP Jerome Randle (Adelaide)FinalsChampionsPerth Wildcats (8th title) Runners-upIllawarra HawksSemifinalistsAdelaide 36ersCairns TaipansFinals MVP Bryce Cotton (Perth)Statistical leadersPoints Bryce Cotton (Per...

Misalliance

Play by George Bernard Shaw This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Misalliance – news · newspapers · books · scholar · JSTOR (December 2023) (Learn how and when to remove this message) This article possibly contains original research. Please improve it by verifying the claims made and adding inline ...

ريو (اليونان)

لمعانٍ أخرى، طالع ريو (توضيح). ريو خريطة الموقع تقسيم إداري البلد اليونان [1] خصائص جغرافية إحداثيات 38°16′55″N 21°51′18″E / 38.2819°N 21.8549°E / 38.2819; 21.8549 [2] المساحة 97.93 كيلومتر مربع الارتفاع 40 متر السكان التعداد السكاني 12487 (legal population of Greece) (2021...

نقطة معلومات (نقاش تنافسي)

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016) هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين...

Mycenaean Greek

Earliest attested form of the Greek language, from the 16th to the 12th century BC This article is about the Greek language as spoken in the Late Bronze Age. For the later dialect used in Achaea and the Peloponnese, see Achaean Doric Greek. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Mycenaean Greek – news · newspapers...

Pemilihan umum Bupati Lembata 2017

Pemilihan Umum Bupati Lembata 20172011202415 Februari 2017[1]Kehadiran pemilih86,21%Kandidat Calon Sunur Wutun Viktor Partai PDI-P Gerindra PDI-P Pendamping Langoday Burin Nasir Suara rakyat 24.211 suara 16.540 suara 14.753 suara Persentase 38,31% 26,18% 23,35% Calon Lipataman Hani Partai PAN Perseorangan Pendamping Leu Linus Suara rakyat 4.913 suara 2.773 suara Persentase 7,77% 4,39% Peta persebaran suara Lokasi Kabupaten Lembata di Provinsi Nusa Tenggara Tim...

PROFILPELAJAR.COM