Computer states

This is a discussion on Computer states within the A Brief History of Cprogramming.com forums, part of the Community Boards category; A computer has an n(bits) amount of ram... So a computer can be in permutation/combination of n states.. which ofcourse ...

  1. #1
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683

    Computer states

    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??

  2. #2
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Location
    Mt. Prospect, IL
    Posts
    2,572
    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

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  3. #3
    BMJ
    BMJ is offline
    Banal internet user BMJ's Avatar
    Join Date
    Aug 2002
    Location
    Chicagoland
    Posts
    1,380
    Ask this same question... only replace "computer" with "brain", and "program" with "action".

  4. #4
    Lead Moderator kermi3's Avatar
    Join Date
    Aug 1998
    Posts
    2,595
    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.
    Kermi3

    If you're new to the boards, welcome and reading this will help you get started.
    Information on code tags may be found here

    - Sandlot is the highest form of sport.

  5. #5
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    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.

    Code:
    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.
    Last edited by VirtualAce; 03-08-2004 at 12:04 AM.

  6. #6
    It's full of stars adrianxw's Avatar
    Join Date
    Aug 2001
    Posts
    4,831
    "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.
    Wave upon wave of demented avengers march cheerfully out of obscurity unto the dream.

  7. #7
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    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.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  8. #8
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    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.

  9. #9
    Rad gcn_zelda's Avatar
    Join Date
    Mar 2003
    Posts
    942
    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.

  10. #10
    Administrator webmaster's Avatar
    Join Date
    Aug 2001
    Posts
    969
    Automated theorem provers exist and have been used, among other things , to rigorously prove Godel's Incompleteness Theorem.

  11. #11
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,702

    Re: Computer states

    >> 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.
    Code:
    bool flip(bool value)
    {
        return std::pow(std::exp(1), std::complex<float>(0, 1) 
        * std::complex<float>(std::atan(1)*(1 << (value + 2))))
        .real() < 0;
    }

  12. #12
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683

    Re: Re: Computer states

    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...

  13. #13
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    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.

  14. #14
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    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 ..

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 34
    Last Post: 02-26-2006, 12:16 PM
  2. Major Computer Problem
    By Olidivera in forum Tech Board
    Replies: 10
    Last Post: 07-15-2005, 11:15 AM
  3. Tabbed Windows with MDI?
    By willc0de4food in forum Windows Programming
    Replies: 25
    Last Post: 05-19-2005, 10:58 PM
  4. Computer will not boot.
    By RealityFusion in forum Tech Board
    Replies: 25
    Last Post: 09-10-2004, 04:05 PM
  5. Regarding Undergraduate Computer Majors
    By UnregdRegd in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 10-04-2003, 11:55 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21