title: Halting really undecidable for computers with limited memory?
body: <p>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.</p>
  
  <p>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.</p>