# simple halting problem question

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

## Recommended Posts

first post with a stupid question: if a turing machine is finite is the halting problem solvable?

##### Share on other sites
Yes. Easily made intractable, but solvable.

An infinite Turing machine may never halt but still be aperiodic. A finite Turing machine may never halt but will become periodic.

##### Share on other sites
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 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 on other sites
Quote:
 Original post by VorpyEven 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 on other sites
Quote:
 Original post by intrest86Not 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.

1. 1
Rutin
70
2. 2
3. 3
4. 4
5. 5

• 21
• 10
• 33
• 20
• 9
• ### Forum Statistics

• Total Topics
633430
• Total Posts
3011825
• ### Who's Online (See full list)

There are no registered users currently online

×