frontpage.
newsnewestaskshowjobs

Made with ♥ by @iamnishanth

Open Source @Github

Open in hackernews

Peano arithmetic is enough, because Peano arithmetic encodes computation

https://math.stackexchange.com/a/5075056/6708
63•btilly•17h ago

Comments

btilly•17h ago
This is a stack overflow question that I turned into a blog post.

It covers both the limits of what can be proven in the Peano Axioms, and how one would begin bootstrapping Lisp in the Peano Axioms. All of the bad jokes are in the second section.

Corrections and follow-up questions are welcome.

Cheyana•16h ago
Thanks for this. In another strange internet coincidence, I was asking ChatGPT to break down the fundamentals of the Peano axioms just yesterday and now I see this. Thumbs up!
burnt-resistor•20m ago
I suspect in the near future (if not already) ChatGPT data will be sold to data brokers and bough by Amazon such that writing a prompt will end up polluting Alexa product recommendations within a few minutes to hours.
im3w1l•10m ago
Well there was a post on mathmemes a day ago about teaching kids set theory as a foundation for math with some discussion of PA. So maybe related ideas are echoing across the intertubes in this moment?
anthk•49s ago
Boot sector Lisp bootstraps itself. Also, lots of Lisp from https://t3x.org implement numerals (and the rest of stuff) from cons cells.

Ditto with some Forths.

dooglius•10h ago
The interesting part to me (I have a background in both math+programming) isn't so much the encoding of computation but that one can work around the independence of goodstein's theorem in this self-referential way. I think this implies that PA+"PA is omega-consistent" can prove goodstein's theorem, and perhaps can more generally do transfinite induction up to epsilon_0? EDIT: I think just PA+"PA is consistent" is enough?
btilly•7h ago
Now we're getting a little beyond the detail that I feel comfortable making statements about.

ChatGPT tells me that PA+"PA is consistent" is not quite enough. I believe that it has digested enough logic textbooks that I'll believe that claim.

codeflo•8m ago
I also like the recursion. In essence, you're making a meta-proof about what PA proves, and given that you trust PA, you also trust this meta-proof.

> I think just PA+"PA is consistent" is enough?

It's not clear to me how. I believe PA+"PA is consistent" would allow a model where Goodstein's theorem is true for the standard natural numbers, but that also contains some nonstandard integer N for which Goodstein's theorem is false. I think that's exactly the case that's ruled out by the stronger statement of ω-consistency.

gsf_emergency_2•2h ago
https://math.stackexchange.com/questions/4408124/what-does-t...
atsmyles•1h ago
Related to PA consistency, it can be proven in PA. https://youtu.be/6pjLmmkZnIA
robinhouston•1h ago
This definitely needs some context for the non-logicians in the house! Gödel's second incompleteness theorem shows that, if PA can prove its own consistency, then PA is inconsistent (and can therefore prove anything, including false things).

The work linked here doesn't show that PA is inconsistent, however: what it does is to define a new, weaker notion of what it means for PA to “prove its own consistency” and to show that PA can do that weaker thing.

Interesting work for sure, but it won't mean anything to you unless you already know a lot of logic.

RossBencina•43m ago
But is computation enough? The computable reals are a subset of the reals.
psychoslave•13m ago
This is an under specified question, until some observable goal is attached to "enough". Enough for what?
A_D_E_P_T•2m ago
"Reals" (tragically poorly named) can be interpreted as physical ratios.

That is: Real numbers describe real, concrete relations. For e.g., saying that Jones weighs 180.255 pounds means there's a real, physical relationship -- a ratio -- between Jones' weight and the standard pound. Because both weights exist physically, their ratio also exists physically. Thus, from this viewpoint, real numbers can be viewed as ratios.

In contrast, the common philosophical stance on numbers is that they are abstract concepts, detached from the actual physical process of measurement. Numbers are seen as external representations tied to real-world features through human conventions. This "representational" approach, influenced by the idea that numbers are abstract entities, became dominant in the 20th century.

But the 20th century viewpoint is really just one interpretation (you could call it "Platonic"), and, just as it's impossible to measure ratios to infinite precision in the real world, absolutely nothing requires an incomputable continuum of reals.

Physics least of all. In 20th and 21st century physics, things are discrete (quantized) and are very rarely measured to over 50 significant digits. Infinite precision is never allowed, and precision to 2000 significant digits is likewise impossible. The latter not only because quantum mechanics makes it impossible to attain great precision on very small scales. For e.g., imagine measuring the orbits of the planets and moons in the solar system: By the time you get to 50 significant digits, you will need to take into account the gravitational effects of the stars nearest to the sun; before you get to 100 significant digits, you'll need to model the entire Milky Way galaxy; the further you go in search of precision, the exponentially larger your mathematical canvas will need to grow, and at arbitrarily high sub-infinite precision you’d be required to model the whole of the observable universe – which might itself be futile, as objects and phenomena outside observable space could affect your measurements, etc. So though everything is in principle simulatable, and precision has a set limit in a granular universe that can be described mathematically, measuring anything to arbitrarily high precision is beyond finite human efforts.

Fired 700 People and Replaced Them with AI-Now Hiring Them Back

https://future4days.com/fired-700-people-and-replaced-them-with-ai-now-klarna-is-hiring-them-back/
1•Sontho•2m ago•0 comments

Phasing out Bazaar code hosting

https://blog.launchpad.net/general/phasing-out-bazaar-code-hosting
1•ngws•5m ago•0 comments

China's booming EV industry – BBC News [video]

https://www.youtube.com/watch?v=YLRXCbq0gWI
1•prmph•9m ago•0 comments

Stuxnet

https://en.wikipedia.org/wiki/Stuxnet
1•cryptoz•13m ago•0 comments

Show HN: VerbaScan – Context-aware image translation

https://www.verbascan.com/
1•coolpool•16m ago•0 comments

Roundup of Events for Bootstrappers in June 2025

https://bootstrappersbreakfast.com/2025/05/29/roundup-of-june-2025-bootstrapper-events/
2•skmurphy•19m ago•1 comments

[video] New ways to interact with windows in iPad OS

https://www.youtube.com/watch?v=QYUFSEcwx4U
1•stefanv•23m ago•0 comments

Show HN: App Store Webhook Proxy for Slack/Teams – Monitor App Review Status

https://github.com/yannisalexiou/appstore-webhook-proxy
1•yannisalexiou•26m ago•0 comments

Show HN: A tool to make AI text undetectable

https://besthumanizer.com
1•TomTsime•26m ago•0 comments

HTML spec change: escaping < and > in attributes

https://developer.chrome.com/blog/escape-attributes
1•fuomag9•30m ago•0 comments

The New Coventry Light Rail Is Here [Geoff Marshall, YouTube] [video]

https://www.youtube.com/watch?v=jHd_e62FIf8
1•JdeBP•42m ago•2 comments

S.1975 - Dark Web Interdiction Act of 2025

https://www.congress.gov/bill/119th-congress/senate-bill/1975/text/is?overview=closed&format=xml
1•baobun•42m ago•0 comments

Maya Blue: Unlocking the Mysteries of an Ancient Pigment

https://www.mexicolore.co.uk/maya/home/maya-blue-unlocking-the-mysteries-of-an-ancient-pigment
2•DanielKehoe•45m ago•1 comments

Postgres Extensions in Rust

https://depth-first.com/articles/2021/08/25/postgres-extensions-in-rust/
1•fanf2•52m ago•0 comments

The Coming Front End Framework Disruption

https://medium.com/@resti.guay/the-coming-frontend-framework-disruption-why-the-next-trillion-dollar-company-might-come-from-web-dbb734589859
1•jurisjs•53m ago•0 comments

WWDC 2025: Unlock GPU computing with WebGPU [video]

https://developer.apple.com/videos/play/wwdc2025/236/
1•pjmlp•55m ago•0 comments

You don't need to blog every week to rank on Google (what works in 2025)

https://news.seoforfounders.com/p/seo-myth-busting-6-you-can-t-do-seo-without-blogging-every-week
4•benchmarkapp•1h ago•3 comments

First 2D, non-silicon computer developed

https://www.psu.edu/news/research/story/worlds-first-2d-non-silicon-computer-developed
1•taubek•1h ago•0 comments

Danish department determined to dump Microsoft

https://www.theregister.com/2025/06/13/danish_department_dump_microsoft/
48•taubek•1h ago•10 comments

Mechanisms for Detection and Repair of Puncture Damage in Soft Robotics [pdf]

https://smr.unl.edu/papers/Krings_et_al-2025-ICRA.pdf
1•PaulHoule•1h ago•0 comments

In America, we don't do kings

https://www.nokings.org
3•doener•1h ago•0 comments

Wars and Casualties of the 20th and 21st Centuries

https://scaruffi.com/politics/massacre.html
3•thomassmith65•1h ago•2 comments

fastmigrate: A simple tool for database migrations

https://twitter.com/alexisgallagher/status/1933615376732131477
1•tosh•1h ago•0 comments

How the Cybertruck Came to Embody Tesla's Problems

https://www.wsj.com/business/autos/tesla-problems-cybertruck-trump-musk-feud-89501946
4•markgavalda•1h ago•1 comments

I built 13 text manipulation tools in 17 days

1•pqchanh•1h ago•0 comments

To fuel AI, US Congress moves to fast-track nuclear plant approvals

https://www.wsj.com/articles/to-feed-power-wolfing-ai-lawmakers-are-embracing-nuclear-a461ab7d
5•markgavalda•1h ago•3 comments

Occurences of swearing in the Linux kernel source code over time

https://www.vidarholen.net/contents/wordcount/#fuck*,shit*,damn*,idiot*,retard*,crap*
1•microsoftedging•1h ago•0 comments

New and Unexpected Discovery

https://www.livescience.com/health/fertility-pregnancy-birth/completely-new-and-totally-unexpected-finding-iron-deficiency-in-pregnancy-can-cause-male-mice-to-develop-female-organs
1•01-_-•1h ago•0 comments

Labubu Live Wallpaper – Bring Your Screen to Life with Magic and Whimsy

https://www.labubu-live-wallpaper.com/en
1•sweeii•1h ago•1 comments

Legendary 'Storm Tracker' Gary England – first to warn with Doppler – has died

https://www.washingtonpost.com/obituaries/2025/06/13/gary-england-tornadoes-weather-dies/
2•markgavalda•1h ago•0 comments