is there an 'opposite' of compiling code? Theorem of machine intelligence

[bwanaaa]

Consider if i gave you a string of 0s and 1s,

1) is there a way to design a machine that could make sense of that string as executable code

2) is the resulting machine design unique or are there infinite possibilities?

 

[Sahakiel]

Originally posted by: bwanaaa
Consider if i gave you a string of 0s and 1s,

1) is there a way to design a machine that could make sense of that string as executable code

Yes, that's why compiled code is sometimes called a binary.

2) is the resulting machine design unique or are there infinite possibilities?

Infinite possibilities, each possibility representing a different architecture.

 

[uart]

Programs called "disassemblers" have long been available to convert binary code into assembler intructions, obviously this is pretty easy to do. However I suspect you are looking more at something that can truely make sense of the code, even comment it or whatever.

 

[blahblah99]

Originally posted by: bwanaaa
Consider if i gave you a string of 0s and 1s,

1) is there a way to design a machine that could make sense of that string as executable code

Isn't that what a computer does already? You feed it 0's and 1's, and it spits out 0's and 1's.

2) is the resulting machine design unique or are there infinite possibilities?

Infinite possibilities. If your string is N bits long, then there are 2^N possibilities.

 

[LurchFrinky]

Originally posted by: blahblah99
Infinite possibilities. If your string is N bits long, then there are 2^N possibilities.

Heh, you sort of contradicted yourself there . There may be 2^N combinations of a string N bits long, but it can be interpreted in more. Consider a string consisting of just one bit, 0. It could be ignored, interpreted as a placeholder, or it can be interpreted to indicate "The Rise and Fall of the Roman Empire". I'd think infinite possibilities would be closer to the mark.

 

[bwanaaa]

I didnt express myself clearly. If I generated a random string of 0s and 1s, is it possible to design a machine that will accept that random sequence as a valid set of instructions that execute. To make it even harder, that the code should execute something useful.

Can such a virtual machine be simulated in software?

Is there a program that can be written to generate said virtual machine?

 

[CTho9305]

Originally posted by: bwanaaa
I didnt express myself clearly. If I generated a random string of 0s and 1s, is it possible to design a machine that will accept that random sequence as a valid set of instructions that execute. To make it even harder, that the code should execute something useful.

Not if you want to do something useful, unless you define only a few instructions which each do something useful in one instruction.

Can such a virtual machine be simulated in software?

See previous

Is there a program that can be written to generate said virtual machine?

Why would anyone want to interpret randomness? You'd never know what you'd get out, and the VERY vast majority of the time, you'd get nothing. Just for kicks, try running some random numbers through your x86 chip - a LOT of combinations make for valid instructions. You'll see how pointless it is .

 

[glugglug]

Originally posted by: bwanaaa
I didnt express myself clearly. If I generated a random string of 0s and 1s, is it possible to design a machine that will accept that random sequence as a valid set of instructions that execute.

It's called a 65C816 (used in Apple //gs & Super Nintendo). 8 bit opcodes with all 256 possibliities used up with valid instructions.

To make it even harder, that the code should execute something useful.

"useful" is a matter of opinion.

Can such a virtual machine be simulated in software?
Is there a program that can be written to generate said virtual machine?

Yes, there are emulators....

 

[rjain]

A virtual machine is a simulation of a machine in software.

 

[bwanaaa]

i didnt know that about the apple//gs-- a 65c816. So then if we arbitrarily assigned 8 bits per byte and broke up the random string into byte long chunks, i could see how one might try to 'evolve' a virtual machine for this data--

1)start with a given set of opcodes assigned to a specific set of byte long numbers.
2)run the 'program' and see what happens
3)reassign the given set of opcodes to a different specific set of byte long numbers
4) keep going back to #2 until all possible combinations have been used
5)compare the outcomes

I dont think this is 'interpreting randomness', rather it is using a pattern of data to establish a rule set. I was having this warped thought after reflecting on the significance of statistics. In the forward direction, an equation specifies a relationship of one set of datapoints to another. In the reverse direction, two sets of datapoints are used to 'derive' or estimate an equation/function/relation.

When we thinkk of writing code, one set of inputs is mapped to a set of outputs. the 'mapping function' is the 'application'. If one had a set of inputs (the string of 0s and 1s) and a set of outputs(the particular goal/result/target) then a mapping function should exist. This mapping function (application) is the rule set relating the 2 datasets. Finding a method to generate such an application would help automate the writing of code.

 

[Matthias99]

I'm lost. What you're talking about in the last paragraph is decompilation / disassembly, which is fairly routine in the programming world. The steps you listed above would be meaningless if applied to "random" data -- what you would possibly map them to other than random inputs? Unless there was some sort of pattern in the data, but then it wouldn't really be "random". From a string of pseudorandom numbers you could figure out (a possible) program that would produce them (ie, an RNG), but that's it.

Going from assembly language to binary code is a 1-to-1 mapping. That's the whole point of assembly language -- it's just a set of mnemonic devices for writing binary code in a form that's (somewhat) human-readable. The 'application' (or mapping function) happens to be called an assembler. A disassembler just runs the same process in reverse. But you have to establish the ruleset first (although I guess if you had matched assembler source and binary output, you could in theory deduce the structure of the assembler).

The problem is that going from a high-level language to a low-level one is *not* a 1-to-1 mapping. The process of translating between them (compilation) involves actually parsing the C code and expanding it into different assembly instructions. The reason this is so much more difficult has to do with the Chomsky Language Heirarchy -- C is a context-free language, whereas all current assembly/binary languages are regular expression languages. There are many (potentially an infinite number of) C programs that could produce a given assembler file. It's this many-to-one mapping that makes decompilation very difficult, and impossible for any large volume of code.

 

[bwanaaa]

I am not referring to compilation/decompilation. That is the translation of high level code to low level code and vice versa. Rather I am considering the code itself. Consider the following : For example, what is the binary representation of the NOP command? Now why is it that? Could the function of the NOP command be represented by a different binary string?

 

[aka1nas]

Are you thinking about genetic algorithms or something? I.E. you wanna generate what amounts to random collections of instructions and then test them until you find a string that does what you want more or less?

 

[aka1nas]

Originally posted by: bwanaaa
I am not referring to compilation/decompilation. That is the translation of high level code to low level code and vice versa. Rather I am considering the code itself. Consider the following : For example, what is the binary representation of the NOP command? Now why is it that? Could the function of the NOP command be represented by a different binary string?

The binary representation is totally arbitrary and assigned by whomever designed the architecture and instruction set. It could be represented by something else, but that would change the architecture.

 

[Matthias99]

Exactly. The opcode corresponds to bits loaded into a register in the processor core, which enable/disable various busses and components in the CPU in order to make the desired function happen the next time the clock "ticks". Your question makes no sense. Perhaps you're trying to ask something else and just not phrasing it right?

You started talking about mathematical functions there, and deriving functions from inputs and outputs. That made sense, at least sort of. But trying to decode random instructions can't possibly get you anywhere. There has to be some sort of pattern or structure there for you to find something.

Given an input to a program, and the program, you can produce the output. Given the input and output, you can try to deduce the program. Given a program and an output, you can try to deduce the input. But I'm not sure what you're trying to do. If you have *just* an output (like a random binary executable for an unknown processor), there's no more information to be gleaned from the system.

 

[Sahakiel]

Originally posted by: bwanaaa
I am not referring to compilation/decompilation. That is the translation of high level code to low level code and vice versa. Rather I am considering the code itself. Consider the following : For example, what is the binary representation of the NOP command? Now why is it that? Could the function of the NOP command be represented by a different binary string?

Forgive me, but I had a long day...
You're an idiot.


Read up on processor design, especially the part where it says "bit strings mean nothing. They can be interpreted any way you want."

And the NOP command can vary from ISA to ISA. It all depends on how the ISA was designed in the first place.

If you're trying to create a programming language or application that automatically produces code when given only a single problem, good luck. You're headed in the wrong direction. As has been reiterated time and time again, bit strings mean nothing by themselves. The same sequence in one application can and almost certainly will produce different behavior on different architectures.

 

[m0ti]

It's sort of a pointless question. Yes you could evolve something which could even do interesting things (for example, an "early" example of a program in Lisp (~1973) was able to teach itself numbers, addition, primality, etc. based on the length of lists), but if you don't want to give it any direction at all it's pretty useless. You need to have interaction with something... in other words, you're looking at some sort of a GA approach where you obviously need some type of fitness function. If we assume our output can be random as well (i.e. the fitness function is random) then our chances of getting "meaningful" results are pretty much 0... especially since you haven't defined yet what "meaningful" means.

To state your problem in a more theoretical sense:

1. Generate a random Turing machine (random number of states, the delta function is also randomly (but legally) set).

2. Take your random input.

3. Run the Turing machine on the input (... umm... halting problem, anyone?).

Even without the halting problem getting in the way, you still need to assign some meaning to the results. About the only thing that I can think of would be to look at the joint entropies of the outputs, but again this almost certainly will not be "meaningful".

 

[uart]

Hehe bwanaaa, sorry to say it but you've outdone all previous attempts for asking silly questions in this thread.


If you need a new silly thought to persue perhaps you could consider this one. "Why is the second last letter of the Alphabet ?" (it only works when you say it out aloud hehe.)

 

[bwanaaa]

thank you almost all of you for your patient replies. yes 'genetic algorithms' is the word pair that took me in the direction i was looking to go (google is a wonderful thing)

uart,

stick your finger in your ear and spell the abbreviation for mountain out loud

 

[uart]

Originally posted by: bwanaaa
thank you almost all of you for your patient replies. yes 'genetic algorithms' is the word pair that took me in the direction i was looking to go (google is a wonderful thing)

uart,

stick your finger in your ear and spell the abbreviation for mountain out loud

Hmmm, M, T, M, T, em, tee, em, tee, em, tee, empty. Hehe very funny.

 

[rjain]

Doh. I thought he meant for us to interpret "your ear" as "your rear" as well. I was wondering what having a well-functioning colon had to do with an attempted insult.

 

[bwanaaa]

RJAIN,

For the benefit of those people who cannot understand how Rjain confused his ear with another orifice, self stimulation to empty the colon is only required for those people with spinal cord injury. Though Rjain is familiar with this process, most of the world is not. It is a natural mistake Rjain, I'm sorry that you have to do it that way. Try mag citrate as well, it helps the colon as well as the clarity of thought.