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).
0

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?

flag
14 
 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
3 
 If anything, I would try cstheory.stackexchange.com – Asaf Karagila Aug 4 2011 at 16:58
3 
 @Simon: er. So you are contradicting the halting theorem? – Qiaochu Yuan Aug 4 2011 at 18:02
3 
 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
2 
 @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
show 4 more comments

closed as too localized by Andres Caicedo, Douglas Zare, Andreas Blass, Ryan Budney, Charles Matthews Aug 5 2011 at 10:47

Browse other questions tagged or ask your own question.