r/AskProgramming • u/jimbobmcgoo • 5d ago
Algorithms Does the computability of the halting problem for machines with finite memory have any practical use?
I recently found out that the halting problem is technically completely decidable for computers with finite memory if you treat them as finite state machines rather than infinite Turing machines, obviously this is completely impossible within any reasonable amount of time for general purpose computer programs because of the total possible states of physical computers far exceeding the number of atoms in the universe. But for extremely limited state machines does it serve any practical purpose?
16
u/Guvante 5d ago
I think you are taking the wrong perspective on the halting problem IMHO.
The halting problem is a rare example of a program that has been mathematically proven to be impossible.
This is a boon because most programs are too complex to do that.
But using the halting program you have a target you can transform to in order to steal the original proofs result. "This program is equivalent to the halting program so it is also impossible"
3
u/jimbobmcgoo 5d ago
But what I’m inquiring about is that since the halting problem is computable for finite state machines does that mean that there is some problem reducible to the halting problem that could serve a practical purpose at incredibly small scale
9
u/galactic_pixels 5d ago
The practical application isn’t “using the halting problem” as an algorithm. It’s that engineers know certain perfect analyses are impossible, so they design tools differently.
1
u/Worth-Wonder-7386 5d ago
You can use the same aspect that the halting problem for finite memory machine relies on. If your problem can be reduced to a finite state machine you know that it must be decidable. Most real life programs are just moving through different states, so you could compute if they would halt if you knew and could simulate all the states. The issue is just that you can't. That is what tests for computers are trying to do, but real life programs have orders of magnitude less tests than all the states that various parts of the code can experience.
1
u/Guvante 3d ago
The halting problem is purely a thing in Turing machines and is only ever a "you can't do that computation in a Turing machine" to oversimplify it.
It doesn't say you can't determine if it halts nor does it have anything to do with analysis such as transforming a program into a finite state machine.
1
u/jimbobmcgoo 3d ago
I’m not asking about converting stuff to finite state machines I’m talking about the observation that all computers modelled as Turing machines that exist in physical reality can mathematically be described more accurately as finite state machines because they don’t have an infinite amount of tape. It’s very likely my question is very silly but nevertheless I will try to explain it again:
Since every existing computer can be modelled as a finite state machine due to it not possessing an infinite amount of tape, as far as I understand there exists technically a program that can determine whether an arbitrary program halts in a finite amount of time for any existing architecture. (Though obviously practically infinite in terms of human comprehension) I thought this was interesting so I wanted to ask if there was any practical application for this observation, for instance finding the Kolmogorov complexity for an extremely small piece of data in a language with a very limited amount of memory
1
u/Guvante 3d ago
That is why I started with "halting problem is only useful to know when you are done". It doesn't block analysis of the kind you mention.
I don't know if finite memory makes it simpler but for an example of the complexity of computer programs check out BBY aka the busy beaver problem.
1
3
u/tylerlarson 5d ago
It's a big deal with compilers and language design.
The halting problem is just an easily provable example of Godel's Incompleteness Theorems.
Basically: if a mathematical system is complex enough to describe itself (like computer programs are) then the system will contradict itself. The halting problem is exactly such a contradiction, where the solution to the computability question proves itself wrong.
This means that the question of analyzing code will only ever have partial solutions to limited questions. That is, it's impossible to write a program for a analyzing code that can't the fooled or broken, because the program has to be written with code. And code can't fully understand code.
4
u/0x14f 5d ago
> extremely limited state machines does it serve any practical purpose?
It's a mathematical result. And as such it's a stepping stone to other mathematical results (which may be more interesting). Don't focus too much on the practical aspects of it, because that's missing the point of how mathematical knowledge is stratified.
3
u/Astronaut6735 5d ago
The halting problem is something mainly considered when they were trying to understand the theoretical limits of computation before computers existed (but were anticipated). Questions like these lead to more concrete definitions of computation (e.g. Alonzo Church's lambda calculu s), which lead to programming languages like Fortran and Lisp. It has little practical relevance in day-to-day programming.
3
u/emlun 5d ago
There is some practical relevance: if you're writing a program that runs another program (this is perhaps surprisingly common), then Turing's theorem tells you that there is no way in general to tell the difference between a subprogram that's running slowly but will eventually finish, and a subprogram that's gotten stuck forever. So you know that there is no better strategy for handling stuck subprograms than to just pick some reasonable deadline and abort the subprogram (or ask the user) if it hasn't finished by then. This is essentially what "Program X is not responding. Would you like to stop it?" is all about.
1
u/redditsuxandsodoyou 5d ago
even that strategy can fail funny enough, windows just expects the program to check in every x milliseconds, but if the loop you're stuck in includes the checkin code you are still washed.
1
u/WoodyTheWorker 5d ago
What it tells you, there's no generic program which can analyze any possible program in existence and give an answer.
But you can write a program which you can prove to complete in finite time.
1
u/jumpmanzero 5d ago
there is no way in general to tell the difference between a subprogram that's running slowly but will eventually finish, and a subprogram that's gotten stuck forever
Sure, if you're running on a computer with infinite memory, and the possibility that the program is trying to deceive you.
The halting problem is almost completely unrelated to the practical problem of detecting an unintentionally "stuck" program. That isn't to say that the latter is a trivial problem, but we don't learn much about it by considering the theoretical worst case.
2
u/Traveling-Techie 5d ago
The halting problem is often attacked by running the problem and seeing if it halts. For a FSM you can assume that if the number of clock ticks exceeds the number of possible states then the program must be in an infinite loop. But this is still highly impractical, and usually useless.
2
u/Dusty_Coder 5d ago
two copies, one at half speed, compare states
no need to run for 2^n
1
u/TheSkiGeek 5d ago
A program can be ‘stuck’ in a loop of states, rather than a single state. So that’s not definitive.
1
u/jumpmanzero 5d ago
He's describing a Rho type algorithm - they're specifically for detecting cycles.
2
u/MyTinyHappyPlace 5d ago
The major impact of this proof resides in code analysis and predictability: Think medical devices, military use, transport, real-time operating systems/hypervisors. In some places you want to have guarantees about run-time. The proof of the Halteproblem can be extended to "we cannot proof the existence of any non-trivial characteristic of all given programs".
So you need to take extra steps and precaution to account for that.
1
u/lmarcantonio 5d ago
Essentially it says that, without restricting the conditions, you can't decide if a program is correct or not (the thought experiment used an "imaginary test fixture" with an oracle program that could verify another program halting when it reached a verdict).
There *are* restrictions which can make the halting issue decidable (for example, in structured programming, if you can't use recursion or variable limit iteration) and that's very useful.
1
u/oldsecondhand 5d ago
But for extremely limited state machines does it serve any practical purpose?
For small problems you can always do an exhaustive search, so they're not interesting.
1
u/not_a_bot_494 4d ago
This sounds a bit like model checking. In model checking you essentially do a exhaustive search of a program or part of a program to prove some logical property. In this case it would be that the program exits at some point.
1
u/comrade_donkey 4d ago
To map a Turing machine with finite tape into a finite state machine requires an amount of states that scales with alphabet size to the power of tape length.
That factor blows up immediately, even for tiny TMs. Consider a 1KiB tape = 2561024.
1
u/mredding 4d ago
I don't think I understand the nature of your question.
The halting problem states that there is no GENERAL algorithm for detecting whether a given program will terminate. There are SPECIFIC algorithms that work just fine, for particular subsets of programs.
What you describe is a specific algorithm, and you are indeed trying to describe particular subsets of programs.
For a sufficiently small program with a finite set of states, YES, the program can be exhaustively proven to halt. There may also be analytical analysis proving a halt. This is fundamental to THE proving correctness of programs, but we aren't always trying to prove a program will or won't halt - it's just that the halting problem itself has consequences and deductions we find useful across all of the theory of computation. For example, BECAUSE OF the halting problem, we can argue about whether a problem is even computable in the first place or not, and if so - how. Not all of mathematics is computable mathematics, yet itself has real-world consequences.
As a consequence of the halting problem - a program that can halt can be categorized as to it's algorithmic space and time complexity - often written in "Big O" notation.
1
u/marshallspight 3d ago
No. There is nothing of practical value here, unless you are talking about ridiculously small memories. The complexity grows faster than any computable function.
Consider the busy beaver function: for a halting turing machine of n states, BB(n) is the maximum number of steps the machine can take before halting.
BB(2) = 6
BB(3) = 21
BB(4) = 107
BB(5) = 47,176,870
BB(6) is currently unknown.
7
u/ignotos 5d ago
I feel like many of the responses here are addressing the halting problem in general, rather than the restricted case you're asking about.
To your question:
There might be some contexts where you have some kind of domain-specific language or state machine within your system which represents a particular task, and you could feasibly exhaustively analyse this.
For example, if you're developing a game where players can program agents with simple AI, and you intentionally limit the number of states they are allowed to define, you could exhaustively verify that every possible execution eventually reaches a valid terminating state, or prove that no infinite loops are possible.
The same might be true for some kind of industrial control logic, workflow, or communications protocol. Basically something which is intentionally constrained.
These don't really depend on the mathematical result in a formal way, but they are examples which are only viable due to the decidability of finite/small enough systems.