Sign in to follow this  

simple halting problem question

This topic is 3593 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

ah.

the reason i ask is that my lecturer/teacher is using the concept of a java program to illustrate the halting problem, and java programs are of finite size.

and i asked here and not to him because its a sunday and i wanted a quick answer. ;)

Share this post


Link to post
Share on other sites
Even with a finite program size, as long as memory is unlimited the halting problem is undecidable. Usually programs only have a finite size, even in the more theoretical models. It is memory that is unlimited. If the memory is finite, then it's just a finite state machine.

Share this post


Link to post
Share on other sites
Quote:
Original post by Vorpy
Even with a finite program size, as long as memory is unlimited the halting problem is undecidable. Usually programs only have a finite size, even in the more theoretical models. It is memory that is unlimited. If the memory is finite, then it's just a finite state machine.

Not quite. As long as you se an upper bound for program complexity then there can be a solution for the halting problem. To observe this, we can generate a table that holds the result of the halting problem for the finite number of possible programs, and this will be a solution.

What is not possible is coming up with a solution to the halting problem that is correct for all programs of any length. And even though it is possible, creating solutions for programs of any complexity is not solved.

Share this post


Link to post
Share on other sites
Quote:
Original post by intrest86
Not quite. As long as you se an upper bound for program complexity then there can be a solution for the halting problem. To observe this, we can generate a table that holds the result of the halting problem for the finite number of possible programs, and this will be a solution.

I said the program size was finite, not that it had an upper bound. The halting problem is undecidable because there exists no general algorithm that will decide it for all finite programs.

Share this post


Link to post
Share on other sites

This topic is 3593 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this