PDA

View Full Version : Computer states



vasanth
03-07-2004, 11:39 AM
A computer has an n(bits) amount of ram... So a computer can be in permutation/combination of n states.. which ofcourse will be very vey large.. does this mean.. that if it was ever possible to generate all the states.. every possible program or situation a computer could be ever run will be achieved in these states..

your thoughts??

axon
03-07-2004, 12:03 PM
this reminds me of the idea that if you have a huge cylinder divided into 80 (number of characters in a line) individual disks, each disk having the whole alphabet, all punctuations and numbers on it, thatís you could print out everything that has ever been written, is being written at the moment you read this, and will be written in the future. I hope this makes sense.

Unfortunately this process would take a HUGE amount of time...I'll get you the stats when I get home...most of whats printed out would be complete gibberish, but in between you could find a full line from Hamlet.

It is really quite interesting. I made a program to simulate this, but I only set it to a couple million "turns", I checked all the words against a dictionary, and stored only the lines that had words in them or mathematical formulas....the results were fascinating.

sorry, that this is kind-of off topic

BMJ
03-07-2004, 12:04 PM
Ask this same question... only replace "computer" with "brain", and "program" with "action".

kermi3
03-07-2004, 12:48 PM
Vasanth -

I think that you could archive every possible state of the computer, but not the program. Arn't programs nothing but a series of states? I could randomly generate a series of bits that show me the current Opera screen that I'm seeing now, but in order to see what will happen when I click submits I'd need a whole new set of random bits to accoplish that state. That sends the element of chance needed to archive the program up exponetially. I think it's akin to the Hamlet line. Your chances of finding one complete line of Hamlet are much better than finding the entire work.

VirtualAce
03-07-2004, 05:01 PM
Well, let's say you have 100 16-bit opcodes each composed of...16 bits...duh.

It would be possible to come up with every permutation and thus you would also come up with correct opcodes. However, you would have to run through this algo for each line of code for as many lines as you want the program to be.

This would take an awful long time to generate but eventually yes you would come out with a fully functional assembly program given that your random number generator did not follow any type of pattern. If it did, then the repetition would throw the whole thing off and you'd never get a program. As well you would have no way of knowing when to stop the algo when a certain opcode was hit - for instance you could end up with

mov ax,bx
inc dx
lds esi,[32bitfullpointer]
ret

Now this is a program and the opcodes are correct but the code is not correct. This would crash hard and do nothing, but it is a valid program. See...you would need more rules to go by when selecting random opcodes.

The very thought of this makes my head spin.

It is the same with bitmaps. Theoretically a bitmap is just a collection of pixels. Given a 20x20 bitmap and 256 colors, if you randomized it enough you could come up with every picture one could ever create with 256 colors. But its not that simple and if you try it...even on the 1 millionth iteration you will probably only end up with colored snow - with no meaning to the pic at all. But a human could take these 256 colors and create a picture out of it in no time - the computer could never do this simply by random chance.



int main(void)
{
double iteration=1.0;
int loopcondition=1;
unsigned int offset=0;
unsigned char far *Screen=(unsigned char far *)MK_FP
(0xA000,0);

do
{
offset=0;
for (int i=0;i<20;i++)
{
offset=i*320+j;
for (int j=0;j<20;i++)
{
Bitmap[i][j]=SomeCompletelyRandomFunc(256);
Screen[j*320+i]=Bitmap[i][j];
offset++;
}
}
getch();
asm {
push di
les di,[Screen]
mov al,0
mov ah,0
mov cx,32000d
rep stosw
pop di
}
iteration+=1.0;
} while (loopcondition==1);
return (0);
}



You could run this a million times and never come up with a meaningful picture.

Better yet take a known picture and its 256 color palette and randomly pick which pixel of the bitmap to plot. The possible combos with having a known palette are 256*256*256* - 400 times. This is because in each of the 400 bitmap pixels or texels we can choose from 256 colors and since the colors can be repeated it would be 256*256*256* - 400 times.

This would be like playing a lottery that had 256 balls and 400 digit positions. Would take forever.

Most lotteries are 7 numbers ranging from 0 to 44 or something like that, thus 44*44*44*44*44*44*44.

adrianxw
03-08-2004, 02:27 AM
"Ford!'' he said, "there's an infinite number of monkeys outside who want to talk to us about this script for Hamlet they've worked out.''

Arthur Dent to Ford Prefect, HHGTTG, Douglas Adams.

joshdick
03-08-2004, 11:14 AM
I've been thinking about something similiar that's in my discrete math book. It talks about finite state machines and then says that they're incapable of certain tasks. Next it describes Turing machines. By the Church-Turing thesis, any algorithm can be expressed as a Turing machine.

However, there exist certain things that don't use an algorithm to solve; thus, it's possible that no Turing machine can solve them. In fact, several problems have been proven to be unsolvable by any Turing machine. This is comforting in a way, because it means that mathematicians will never be replaced by Turing machines. However, this poses a question about the nature of the human brain. What is the model of our brains that is capable of so much more than finite state machines of Turing machines? And if we could build a machine based on the same model as our brains, a number of questions could arise. Would such a machine have intelligence and be sentient? Would it be capable of proving theorems, something only humans can do?

Let me know what y'all think.

linuxdude
03-08-2004, 01:05 PM
I really don't think a computer would be able to prove theorems. It would have to have all the postulates, corrolaries etc. in its knolweldge base, but the thing would be that it can't look at something logically and induce information from it.

gcn_zelda
03-08-2004, 03:04 PM
Originally posted by linuxdude
I really don't think a computer would be able to prove theorems. It would have to have all the postulates, corrolaries etc. in its knolweldge base, but the thing would be that it can't look at something logically and induce information from it.

Artificial Intelligence.


A lot of it.

webmaster
03-08-2004, 04:37 PM
Automated theorem provers exist and have been used, among other things , to rigorously prove Godel's Incompleteness Theorem.

Sebastiani
03-09-2004, 12:05 AM
>> that if it was ever possible to generate all the states

It isn't a question of possibility - only practicality.

>> every possible program or situation a computer could be ever run will be achieved in these states..

What good is a state by itself? It's almost meaningless outside of the context of the states that would have normally led up to it.

vasanth
03-09-2004, 04:46 AM
Originally posted by Sebastiani
>> that if it was ever possible to generate all the states
What good is a state by itself? It's almost meaningless outside of the context of the states that would have normally led up to it.

Its meaning less for now.. but there are some systems which need to have a limited state... so that all outcomes can be predicted.... FOr example a real time system which controls he braking system in a car will have very limited memory.. and the bit pattern in te memory will do various tasks.. So all possible states are cheked while testing... And tis was the reason i asked this question...

VirtualAce
03-09-2004, 06:06 PM
I actually tried the bitmap thing I talked about. I ran the code for 2 million iterations and it never got the right combination of pixels even working with a known palette from a bitmap.

vasanth
03-10-2004, 06:12 AM
Originally posted by Bubba
I actually tried the bitmap thing I talked about. I ran the code for 2 million iterations and it never got the right combination of pixels even working with a known palette from a bitmap.

may be you should have run it for a month .. :D:D