flat assembler
Message board for the users of flat assembler.

Index > Heap > About the halting problem

Author
Thread Post new topic Reply to topic
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?
Post 05 Mar 2015, 05:58
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
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).
Post 05 Mar 2015, 11:28
View user's profile Send private message Reply with quote
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
Post 05 Mar 2015, 11:31
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.