CODEWITHSUNDEEP
language-agnostichalting-problem
user1202136
user1202136

Reputation: 11567

Halting really undecidable for computers with limited memory?

Turing proved that the halting problem is undecidable over Turing machines. However, real computers are not actually Turing-complete: They would be, if they had an infinite amount of memory.

Given the fact that computers have a finite amount of memory, hence are not quite Turning-complete, does the halting problem become decidable? My intuition tells me that yes, but the program that solves this restricted halting problem might have a time and space complexity exponential to the size of the memory of the targeted computer.

Upvotes: 4

Views: 1616

Answers (1)

Neil Forrester
Neil Forrester

Reputation: 5241

The halting problem can be solved for a Turing machine with finite tape by a Turing machine with infinite tape. All the infinite Turing machine has to do is enumerate every possible state of the finite Turing machine (and there will be a finite, though very large, number of possible states) and mark which states have been visited by the Turing machine in the course of running a program. Eventually, one of two things will happen:

  1. The finite Turing machine will halt.
  2. The finite Turing machine will revisit a state. If it revisits a state, then you know there is an infinite loop, since the machine is deterministic, and the next state is therefore determined entirely by the previous state. If there are n states, the machine is guaranteed to revisit one of them on the n+1th step.

Upvotes: 4

Related Questions