flat assembler
Message board for the users of flat assembler.

 Index > Heap > About the halting problem
Author
l4m2

Joined: 15 Jan 2015
Posts: 648
l4m2
Assume there are infinity computers with id 0,1,2,...
We can use
Code:
```exist(i){
...
}    ```
to know whether there is at least one computer running the code make i true. No loop is allowed in this code block.
It's obvious that we can get more than one variable with
Code:
```bb=id&-id;
r1=(id/bb)%bb;
r2=(id/bb/bb)%bb;
...    ```
.
We firstly think of testing if a program halt by using
Code:
```for(i=0;i<r1;i++)step();
return(halted);    ```
but because of the limit of No loop, we can't.
However, as this page said, everything can be solved in O(1) if you give a big-enough number, where we can directly use r2 to be one. Therefore, you can make a halting judge.
However, if so, i can also make
Code:
```int main(){
while(haltable(main))
;
}    ```
to stop you from getting the right answer.
So what's wrong?
05 Mar 2015, 05:58
tthsqe

Joined: 20 May 2009
Posts: 724
tthsqe
Is this relevent?
Quote:
So, the solution above is an O(1) solution to the halting problem, but not to the halting problem of generic Turing machines but rather to the much simpler case of Turing machines that use a bounded length tape (as well as for non-deterministic Turing machines that use a bounded length tape).
05 Mar 2015, 11:28
l4m2

Joined: 15 Jan 2015
Posts: 648
l4m2
tthsqe wrote:
Is this relevent?
Quote:
So, the solution above is an O(1) solution to the halting problem, but not to the halting problem of generic Turing machines but rather to the much simpler case of Turing machines that use a bounded length tape (as well as for non-deterministic Turing machines that use a bounded length tape).
yes and use a varying number to be the length
05 Mar 2015, 11:31
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou can attach files in this forumYou can download files in this forum