MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## finite programs will either complete or run forever [closed]

I have a simple 5 page proof to show that finite programs will either complete or run forever. Though this has been done before I believe that this approach highlights some immediate and practical implications for moden OS and applications.

My problem is that though I have a comp. sci. honours degree it has been some time since I graduated so I have lost contact with the academic world.

I need some feedback on the proof from those who have published. I tried the usenet group comp.theory but since I only have access via Google groups it takes a week for my posts to show up.

What would be the best way for me to get serious feedback on the proof before trying to publish?

-
What alternatives are possible? I mean, when you're showing that they complete or run forever, what else could they possibly do? – James Cranch Aug 4 2011 at 16:27
If anything, I would try cstheory.stackexchange.com – Asaf Karagila Aug 4 2011 at 16:58
@Simon: er. So you are contradicting the halting theorem? – Qiaochu Yuan Aug 4 2011 at 18:02
Oh, I see. If a program runs forever and has a finite number $N$ of possible states, then its behaviour is eventually periodic (and enters a period in time less than $N$). So to see if it will run forever, just watch it for $N+1$ steps and see if it hits the same state twice. We on the same wavelength? – James Cranch Aug 4 2011 at 18:13
@Qiaochu: Not necessarily, depending on what Simon means by "finite program". The halting problem is decidable for certain types of machines with finite memory. – Beren Sanders Aug 4 2011 at 18:14