Real computation

Circuit diagram of an analog computing element to integrate a given function. Real computation theory investigates properties of such devices under the idealizing assumption of infinite precision.

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]

See also

References

  1. ^ Klaus Weihrauch (1995). A Simple Introduction to Computable Analysis.
  2. ^ 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.
  3. ^ Scott Aaronson, NP-complete Problems and Physical Reality, ACM SIGACT News, Vol. 36, No. 1. (March 2005), pp. 30–52.

Further reading

Stub icon

This computer science article is a stub. You can help Wikipedia by expanding it.

Read other articles:

Suìrén

Suìrén Suiren, dari: The Dragon, Image, and Demon oleh Hampden C. DuBose, London 1886 Hanzi tradisional: 燧人(燧人氏) Hanzi sederhana: 福禄寿 Alih aksara Mandarin - Hanyu Pinyin: Suìrén (Suìrén Shì) - Wade-Giles: Sui-jen (Sui-jen Shih) Suiren (Pinyin: Suìrén-Shì; Hanzi: 燧人氏; terjemahan: pembuat api) atau Suiren Shi (Suku Suiren) merupakan penemu api yang paling pertama dalam mitologi Tiongkok. Namanya memiliki arti pria pengebor api karena ia membuat api dengan cara m...

 

Agincourt Square, Monmouth

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 April 2016. Agincourt Square, Monmouth Pemandangan alun-alun menghadap barat dayaNama sebelumnya Market PlaceLokasi Monmouth, Monmouthshire, WalesKode pos NP25Koordinat 51°48′44″N 2°42′56″W / 51.812124°N 2.715489°W / 51.812124; -2...

 

Darigold

American dairy cooperative Northwest Dairy AssociationDarigold corporate offices in SeattleTrade nameDarigoldCompany typeAgricultural marketing cooperativeIndustryAgricultureFounded1918HeadquartersSeattle, Washington, USArea servedWashington, Oregon, Idaho, California, Utah, Nevada, and HawaiiWebsitedarigold.com Northwest Dairy Association (formerly the Northwest Dairymen's Association; trading as Darigold, Inc.) is an American dairy agricultural marketing cooperative. Headquartered in Seattl...

Daur ulang di Jepang

Tempat sampah daur ulang di Jepang Daur ulang di Jepang (リサイクルcode: ja is deprecated , Risaikuru), adalah aspek dalam pengelolaan sampah di Jepang, didasarkan pada Undang-Undang Daur Ulang Wadah dan Kemasan Jepang. Plastik, kertas, botol PET, aluminium dan kaca dikumpulkan dan didaur ulang. Profil negara Jepang dalam Waste Atlas menunjukkan bahwa tingkat daur ulang pada tahun 2012[butuh klarifikasi] sebesar 20.8%.[1][perinci lagi] Undang-Undang Daur Ulang Wad...

 

القوات الجوية الفلبينية

القوات الجوية الفلبينية   شعار القوات الجوية الفلبينية الدولة  الفلبين الإنشاء 1 يوليو 1947 النوع سلاح الجو الدور حرب جوية الحجم 16.000[1] جزء من القوات المسلحة الفلبينية 247 طائرة الاشتباكات الحرب العالمية الثانية  الموقع الرسمي الموقع الرسمي  الشارة دائري الطـائ...

 

Virginia's 29th House of Delegates district

Virginia state legislature district District map from the 2023 election Virginia's 29th House of Delegates district elects one of 100 seats in the Virginia House of Delegates, the lower house of the state's bicameral legislature. District 29 represents the city of Winchester as well as parts of Frederick and Warren counties. The seat is currently held by Bill Wiley, who was elected in a November 3, 2020 special election. District officeholders Years Delegate Party Electoral history January 12...

Del Shannon

American musician (1934–1990) For the novelist under the pen name Dell Shannon, see Elizabeth Linington. Del ShannonShannon in 1965Background informationBirth nameCharles Weedon WestoverBorn(1934-12-30)December 30, 1934Coopersville, Michigan, U.S.DiedFebruary 8, 1990(1990-02-08) (aged 55)Santa Clarita, California, U.S.GenresRock and rollcountryOccupation(s)MusiciansingersongwriterInstrument(s)Vocals, guitarYears active1954–1989LabelsBigtopNetworkLondonTwirlBerleeAmyLibertyDunhillUnit...

 

Trisetum flavescens

Species of grass Trisetum flavescens Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Angiosperms Clade: Monocots Clade: Commelinids Order: Poales Family: Poaceae Subfamily: Pooideae Genus: Trisetum Species: T. flavescens Binomial name Trisetum flavescens(L.) P.Beauv. Trisetum flavescens, the yellow oatgrass[1] or golden oat grass, is a species of grass in the family Poaceae. It is native to Europe, Asia, and North Africa. It can be found elsewhere, such as ...

 

KNVB beker 1982-1983

KNVB beker 1982-1983 Competizione KNVB beker Sport Calcio Edizione 65ª Organizzatore KNVB Luogo  Paesi Bassi Cronologia della competizione 1981-82 1983-84 Manuale La Coppa d'Olanda 1982-83 fu la 65ª edizione della competizione. Indice 1 Turno preliminare 2 1º turno 3 2º turno 4 Ottavi 5 Quarti di finale 6 Semifinali 7 Finale 8 Collegamenti esterni Turno preliminare 4 e 5 settembre 1982. Partecipano solo club dilettanti. Squadra 1 Risultato Squadra 2 TSV Longa 0 - 0 (dts) Caesar VV O...

William Green (action painter)

British painter This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: William Green action painter – news · newspapers · books · scholar · JSTOR (July 2016) William Green - Action Painter, in action William Green (1934 – 28 January 2001), was an artist who achieved attention in the late 1950s ...

 

沙巴

  关于位於加勒比海的荷屬島嶼，请见「薩巴」。 沙巴Sabah州 州旗州徽颂歌：Sabah Tanah Airku《沙巴我的故土》   沙巴   马来西亚其它州属坐标：5°18′N 117°00′E / 5.3°N 117°E / 5.3; 117首府亞庇省份 列表 西海岸省山打根省古達省內陸省斗湖省 政府[1][2] • 邦元首朱哈·马希鲁丁 • 首席部长哈芝芝·诺面积[3]...

 

Barongan

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. Untuk kegunaan lain, lihat Barongan (disambiguasi). BaronganPertunjukan kesenian ...

دالي حسن باشا

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

 

London Marathon

Annual race held in London, England London MarathonDateAprilLocationLondon, United KingdomEvent typeRoadDistanceMarathonEstablished29 March 1981; 43 years ago (1981-03-29)Course recordsMen: 2:01:25 (Kelvin Kiptum, 2023)Women: 2:15:25 (Paula Radcliffe, 2003)Wheelchair men: 1:23:44 (Marcel Hug, 2023)Wheelchair women: 1:38:24 (Catherine Debrunner, 2022)Official sitewww.tcslondonmarathon.com 2024 London Marathon The London Marathon (also known as the TCS London Marathon for spon...

 

Financial Literacy and Education Commission

US agency The Financial Literacy and Education Commission (the Commission) was established under Title V, the Financial Literacy and Education Improvement Act which was part of the Fair and Accurate Credit Transactions Act (FACT) Act of 2003, to improve financial literacy and education of persons in the United States. The FACT Act named the Secretary of the Treasury as head of the Commission and required 20 other federal agencies and bureaus to participate in the Commission. The Commission co...

Pyotr Potemkin

Russian nobleman and politician (1617–1700) You can help expand this article with text translated from the corresponding article in Russian. (October 2018) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia. Do no...

 

Нельсон, Ирина

У этого термина существуют и другие значения, см. Диана.В Википедии есть статьи о других людях с фамилиями Тюрина, Нельсон и Терёшина. Ирина Нельсон Основная информация Имя при рождении Ирина Анатольевна Терёшина Полное имя Ирина Анатольевна Тюрина[1][2] Дата...

 

Tagbilaran

Peta menunjukan lokasi Tagbilaran City Tagbilaran City adalah kota yang terletak di provinsi Bohol, Filipina. Pada tahun 2007, kota ini memiliki populasi sebesar 92.297 jiwa. Pembagian wilayah Tagbilaran City terbagi menjadi 15 barangay, yaitu: Barangay Luas wilayah(km²) Rankingluas wilayah Penduduk(2007) Rankingjumlah penduduk Kepadatan(per km²) Rankingkepadatan Bool 3.488 4 4,929 10 1413.13 12 Booy 1.464 9 7,896 2 5393.44 6 Cabawan 2.673 6 1,550 15 579.87 15 Cogon 2.044 8 17,266 1 8447.16...

Инаугурация президента США

Инаугурация Барака Обамы в 2009 году. Общий вид церемонии Инаугурация президента США (англ. United States presidential inauguration) — торжественная церемония присяги и вступления в должность президента и вице-президента США. По традиции проводится публично перед Капитолием в Ваши�...

 

Janine Flock

Janine FlockJanine Flock nel 2020Nazionalità Austria Altezza175 cm Peso63 kg Skeleton SquadraBSC Stubai Palmarès Competizione Ori Argenti Bronzi Mondiali 0 2 1 Europei 3 4 4 Mondiali juniores 0 0 1 Campionati austriaci 8 0 0 Trofeo Vittorie Coppa del Mondo 2 trofei Vedi maggiori dettagliStatistiche aggiornate al 20 gennaio 2023 Modifica dati su Wikidata · Manuale Janine Flock (Hall in Tirol, 25 luglio 1989) è una skeletonista austriaca, vincitrice di due trofei di Coppa del ...