Agreed. Our 9 year old keeps talking about "When I grow up I'm going to be a chef", he's really set on it. Our 5 year old says she wants to be a "girl scientist".
It tears me up inside to think that we might not even have food and water by the time they get there, let alone the level of pretend we have to maintain so that their childhood is preserved now.
I grew up thinking there was a decent chance we would run out of oil and civilization would collapse. EVs were not a thing and I remember reading about how an economical battery big enough to give a car good range was not possible, and that modern civilization in general was impossible without cheap oil. I read detailed articles about how impossible powering modern society without fossil fuels was… articles that are now clearly wrong.
My parents grew up thinking they might die at any moment in a nuclear war.
I’m not saying nothing will happen. Obviously we are already dialed into this and it’s physics and it will have effects. I’m also not saying past successes guarantee future ones.
I’m just saying that every generation since WWII has grown up with at least one impending doom scenario and yet here we are.
“May you live in interesting times.”
Personally I think we will be forced to adapt to climate change, and that it will be expensive and in parts of the world ugly. It will drive migration and conflict. It will rob us of dividends we could have spent on better things but instead must be spent on infrastructure mega projects. It will kill and impoverish and start wars.
But we will make it.
People will say never again, let’s never ignore warnings like that again. But we will probably forget that lesson, unfortunately, and future generations will grow up under some other avoidable doom cloud.
There's a button next to "gyro" labeled "hands." Click on it, and the browser will ask for the camera permission. For me (Chrome, mac), I had to click on the "cal" button next to it the first time to actually switch to the camera.
Ahhh this is fantastic thank you; it _is_ hard to reconcile whether problems come with the original topic or whether they are introduced by the abstraction that we _need_ to make in order to quantify a thing/explain it to ourselves and others.
Regarding the downcast/upcast; I think it _can_ be possible to do this successfully;
> I have a glass, I throw it at a hard surface. What will happen? Well (duh) the glass will (most likely) break.
This hypothesis completely ignores nearly 100% of all relevant physics and the laws surrounding the problem; the arrangement of air molecules, the arrangement of the molecules in the glass, the physical forces governing me, it reduces the entire equation down to some really basic napkin physics.
But; does the outcome work? Has my interpretation of the universe and its physics actually predicted what will happen?
Probably a stupid example, but I think that a lossy picture of the universe can still yield a correct answer.
I can't physically run a simulation of the entire universe in my brain, as my brain is part of that same universe. Lossy representations/models are a necessity in the thinking-ham bound world in which we exist.
You're right. But consider this: the geocentric model perfectly predicted planetary positions for centuries, and it was certainly useful. But could we say it was the essence of the universe? In the end, it's a useful model within limited cognition, but whether it's 'fundamental' is a separate question.
I think the key is that different phenomena require different approaches, and even if you interpret a single phenomenon through multiple mental models, none of them necessarily captures its essence. Ultimately, it's about which mental model is shared by a 'group'—not about what's fundamentally true.
We currently share the model of computation, but whether that makes it fundamental is a different story.
As a programmer, I'd put it this way: no matter how well an API describes the backend, the backend itself is not the API.
Here, the API is human knowledge, and the backend is the world
This is what makes me sad about the AI age; many articles now have the same phrasing, the same analogies, the same quips, structure, the same wording; once you start to see it there's no going back.
I actually laughed quite a lot to begin with, GPT models saying things like "...might look like P, but is NP wearing a hat and a lab coat..." and "...is a haunted house disguised as a git repository..."; but alas when you've heard them a million times everywhere it really starts to bite.
Something has always nagged me about the halting problem, might be my mis-understanding of the problem space but;
- You have a piece of software
- That software does in memory compute only
- The software does not touch any peripherals, networking, or any other external source which introduce unpredictability (x)
I'm convinced that somehow this can be solved/proven whether the execution will halt or not.
(x) The second you touch any external peripherals or networking, you're effectively asking the question of "If I phone my friend, will they pick up the phone?" -> to which the only answer is, "They'll pick it up, only if they pick it up/are there". You can't answer that question without trying it.
Am I missing the point? I'm sure you can introduce other edges even in the limited model above, e.g. where a memory stick stops responding or something; but all in if you have reliable kit and don't touch anything external, why can't this be solved?
For the finite case, the more relevant question is, can you predict whether or not the computation will halt in less time than 1. executing the algorithm and 2. checking whether or not the algorithm ever loops?
Bear in mind checking whether or not the algorithm ever loops means taking the full state of the system and checking against a database of all previous states of the system. Bear in mind that the Atari 2600, and its whopping 128 bytes of RAM, has with that amount of RAM more states than there are planck volumes * planck time intervals in the known universe... by over sixty orders of magnitude. And every three additional bits you add to the RAM of the system your are looking at adds an order of magnitude (minus a bit) to that, so, nearly 3 orders of magnitude more states per byte... not per megabyte or gigabyte, per byte. Call it 2 orders of magnitude per byte if you want to be conservative.
It can be solved, if by nothing else simply by running it, in the mathematical sense. In the practical sense it's not even close. That's why we use the Turing machine analysis... technically it's an approximation because we don't actually have real Turing machines. However the size of the finite state machines we have is such that it is far more productive to simply say "the halting problem is unsolvable" than to argue about how many orders of magnitude of orders of magnitude of resources it takes to solve the question of whether or a given program terminates.
Thank you for your insightful answer, in reduction; "Don't fight a god, you won't win, and you'll definitely die in the process!"
The approach you describe though is brute force. I don't think (if there even is an answer to this problem) that it can be brute forced; that's where you run into the limits of hardware/computation/energy and start talking about timeframes which exceed the life of the universe.
I think brute force might be a useful tool in places to validate results, but if there _is_ an answer to this problem it's purely mathematical.
Apologies for sounding both excited and naive; these sorts of challenges make me happy in strange ways that no other thing does!
There is no general solution other than brute force. That's not a terribly difficult extension of the halting problem, it just takes more paperwork to deal with the edge cases, but you'll get to that result. The same basic technique works: Your supposed solution to the problem is itself some finite program, and you can feed it the "I halt only if I don't halt" problem too. The difference is that brute force is a solution, because now instead of an infinite sequence of programs you have a bounded set of programs. So whatever concrete "I halt only if I don't halt" you pass to someone within the specified limits, there is definitely some answer, but your technique won't be able to tell what it is short of just running it.
For the same reason the halting problem doesn't even have a good heuristic, neither does this. Unpredictable chaos is not an exceptional case, it is the exponentially-normal case. You have to go the other way, and construct programs deliberately designed to have the ability to tell if they halt. The term for that if you want to learn more about it is "non-Turing complete programming language", sometimes called a "sub-Turing" programming language: https://increment.com/programming-languages/turing-incomplet...
You can read that as "this is how hard it is to construct code that we can make execution guarantees about". That focuses on code that is deliberately constructed to be finite in scope and may be something that can be strictly bounded in memory use or time or both. You'll note if you spend any time working with them how hard they are to work with. That's a reflection of the limits of generalizing any such proofs of time or space of a given program.
If there is a general algorithm that does what you think, we don't even have a clue what it would look like. And we have a lot of clues there can't be any such thing.
Thanks for the link, great read. I think I get you here; in the context of a DSL where it's impossible to travel more instructions than X, suddenly you don't have a halting problem anymore as you've artificially limited that language's ability to travel beyond a known/fixed set of states.
The second you wield a language which has constructs like Haskell, where in theory you can iterate over an infinite list of items (thinking about it even any language where for i in input_var is possible); the halting problem hits you in the face like a brick.
Its almost a chicken and the egg problem, where you can't know how long it will run for/whether it will halt without already knowing the answer, but if you knew the answer, you wouldn't need the program to find it.
Assume H(P,i) to be a program that tells you whether the program P will halt on input i. Returns true if it halts and false if it doesn't.
Define a new program G(x) that halts if x does not halt on itself as input and loops forever if x halts on itself as input:
def G(x):
if H(x,x):
while True:
pass
else:
return
Does G(G) halt?
If G(G) halts then H(G,G) is true so we end up in the infinite loop, a contradiction. If G(G) does not halt then it returns without looping, also a contradiction.
So our halting oracle H does not exist, so there can not be a function that tells you whether another function will halt on itself as input, so there can not be a function that tells you in the general case whether some other computation will halt, QED.
Imagine a program that generates the digits of pi, one after the other and stops when it is finished. A general purpose program analysing this program to decide if it stops or not would have to know about pi. And about every other possible algorithm.
Thank you internet stranger, for introducing me to hard-maths drugs; am hooked!! \o/
I love the idea of this. So the BB problems are individual iterations of the halting problem right? To truly solve the problem one would have to come up with a program which would operate on all possible BB numbers?
This truly leads into "computation"; when we're dealing with known quantities, yes, we can "solve" the halting problem. The second you move into "we don't know the answer yet", the can of worms opens. Thank you.
There remain undecidable problems even with finite memory/state space.
Linear bounded automata (LBA) the halting problem is decidable. But many properties of LBA are undecidable:
Emptiness: Does an LBA reject all possible inputs?
Universality: Does an LBA accept all possible inputs over its alphabet?
Equivalent: Do two LBA accept the same language?
Finiteness: Does an LBA accept a finite number of strings.
Computation is the study of infinity. That is how I like to think about it. It doesn't seem that way when you're building a website (well, in some ways because it's not at that point), but every algorithm, data structure, etc is an investigation into a certain part of infinity. Think of the way in which we generally categorize algorithms (Big-O notation)... that's just characterizing infinity.
If the memory is bounded then your software is a simple finite automaton, and can be decided in finite time. The issue is with unbounded memory. The issue with the halting problem is a simple characteristic of infinity. This is actually what people are noticing when they say that computation is a fundamental part of the universe. They are correct! The universe deals with infinitisemals all the time. As humans, we have only discovered ways of dealing with certain classes of infinitesemals (calculus). The others remain beyond our ability to characterize. Indeed, some have been proven to be uncharacterizable.
You might enjoy the book Escher Gödel Bach, the Eternal Golden Braid by Douglas Hofstadter, which will open up the world, power, and "danger" of proofs using contradiction to you.
I'm not a religious person but this seems relevant to your comment;
> So I commended the enjoyment of life, because there is nothing better for a man under the sun than to eat and drink and be merry.
As someone with autism and ADHD; I have spent my life trying to understand better ways to do things, optimisations, doing things "right" or "better" or "faster", and trying to come to terms with others who don't really give a shit about any of it.
The conclusion I arrived at is that the snapshot of time I get in this form is best spent enjoying what this form has to offer, nothing more.
- My sausage'y shaped fingers can't manipulate time or gravity; but they can tickle my children and make them laugh.
- My heart can't fix anything; but it can help me to understand others suffering and guide my actions.
- My eyes can't see the whole electromagnetic spectrum; but they can appreciate a beautiful vista and fill me with wonder.
When TFA mentions that a star just ate a planet, I remember just how small and unimportant I am outside a tiny speck of the world; and rejoice that I'm not responsible for anything super important outside that little speck. \o/
Made me laugh while drinking; messy, but worth it for the smiles I'll have every time I remember it! Outstanding job, internet stranger.
reply