PDA

View Full Version : Computation theory question



Clyde
06-28-2006, 04:08 PM
A universal Turing machine can simulate any Turing machine. Right got that. But is it always possible to determine the exact nature of a given Turing machine?

Suppose i hand you some kind of hardwired word processor type thing. One of those weird electronic typewriters, now pretend it wasn't programmed in any language you know (and the machine code is unknown too). All you have is the device but you have available to you all the physical information - so you can watch voltages changing across every chip in the circuit as you use the word processor

Purely with that physical data is it feasible to work out how to simulate the machine on a computer? If it's not feasible how simple do we need to make the machine before it becomes feasible and what kind of scaling in terms of difficulty are we talking about?

VirtualAce
06-28-2006, 10:56 PM
What?

SlyMaelstrom
06-28-2006, 11:33 PM
Bubba: If you knock out the first paragraph and shuffle the words around in the second two, it would appear he's asking if you could take the physical signals going on in the processors and memory and the boards between them, could you decipher what the computer is actually computing.

If that is the question, I would probably have to say that with the right technology, the answer is yes. I'm no engineer, but I'd imagine if you could read the pulses properly, you could convert it to machine code and then to whatever higher level language or psudocode you wish. Of course, I'd say this is probably not a simple procedure.

Again, though, I'm no engineer nor am I a very good programmer. :/

axon
06-29-2006, 12:06 AM
god, i hated that class.

Clyde
06-29-2006, 02:53 AM
If you knock out the first paragraph and shuffle the words around in the second two, it would appear he's asking if you could take the physical signals going on in the processors and memory and the boards between them, could you decipher what the computer is actually computing.

If that is the question, I would probably have to say that with the right technology, the answer is yes. I'm no engineer, but I'd imagine if you could read the pulses properly, you could convert it to machine code and then to whatever higher level language or psudocode you wish. Of course, I'd say this is probably not a simple procedure.


Yes that was essentially my question. I would have thought it was possible in principle but it's not obvious to me whether it's possible in practice, and if it is what are the limits? In the original scenario there is just one hardwired device if that's feasible then could the same approach be applied to software - if you didn't know the machine code of a PC and you could watch all the physical signals is it feasible to suggest someone could deduce the machine code, and then use that to work out what the PC is doing?

Intuitively you expect it to be impossibly difficult, if you imagine writing the best possible algorithm that will look at the signals and look at the output and try and work out what's going on, then i'd have thought the scaling of the algorithm would be truly horrible - so it might manage ok with a single chip fed by a single input stream and outputing some binary lamp on/lamp off output, but as the system of interest got more complex the amount of time necessary to compute would increase at some exponential rate. - e.g. double the no. of components, multiply the time taken for the algorthm to work it all out by 64.

The problem is, since i know next to knowing about the theory underneath computers i don't know whether my guess is right or not (i hope it's not), and i want to find out!

SlyMaelstrom
06-29-2006, 03:13 AM
I actually looked over the part where you said you didn't know the language the system is communicating in. If that's the case, the answer is likely no. Then again, now we're looking more along the lines of cryptography, which again, I'm no specialist in.

anonytmouse
06-29-2006, 09:10 AM
Suppose i hand you some kind of hardwired word processor type thing. One of those weird electronic typewriters, now pretend it wasn't programmed in any language you know (and the machine code is unknown too). All you have is the device but you have available to you all the physical information - so you can watch voltages changing across every chip in the circuit as you use the word processor

Purely with that physical data is it feasible to work out how to simulate the machine on a computer? If it's not feasible how simple do we need to make the machine before it becomes feasible and what kind of scaling in terms of difficulty are we talking about?

Unless you run every input combination (clearly not feasible for any program which accepts non-trivial input), you can't guarantee that you have seen every code path. Therefore, you can't guarantee a 100% complete simulation, although you may be able to get the common code paths, which may be good enough.


In the original scenario there is just one hardwired device if that's feasible then could the same approach be applied to software - if you didn't know the machine code of a PC and you could watch all the physical signals is it feasible to suggest someone could deduce the machine code, and then use that to work out what the PC is doing?

Yes. At the CPU level, input and output can be relatively simple. An instruction may consist of just a few words of input and ouput (operands, op-code, flags, etc). Clearly, if you can monitor the input and output it is probably feasible to reverse engineer the CPU instructions.

Clyde
06-29-2006, 11:03 AM
Unless you run every input combination (clearly not feasible for any program which accepts non-trivial input), you can't guarantee that you have seen every code path. Therefore, you can't guarantee a 100% complete simulation, although you may be able to get the common code paths, which may be good enough.


Ah ok, that makes sense.

Does it make a difference if you can isolate bits of the hardware:

Forget that it's a word processor and look at each chip individually, test each chip interms of inputs and outputs (which from your comment on the CPU would not seem to be unfeasible). Thus work out what each section of the circuit does then put it all together.

If one follows that method can you reconstruct the logic of the underlying code in the machine?

dpro
06-29-2006, 11:55 AM
Unless you have specific and defined behaviors for each chip I would think that is not a feasible way either. Sure you can test inputs and outputs, but in many cases I can see where a chip could have multiple inputs and outputs, which causes a huge amount of tests. Its probably more feasible than testing all non-trivial output, but to me it seems like it would still be too hard to get the base logic of the machine.

This is a thought only however, its just a feeling that, that particular method would not work too well.

Rash
07-08-2006, 12:24 PM
It's impossible, even if you isolate bits of hardware. You don't know whether a chip retains information from what was typed in 30 days ago, or 2000000 years ago, and there's no way you can guarantee that it doesn't. Perhaps one chip says that every Nth keypress, where N = 5 trillion, it shifts the letter value by 1. You could not prove that there is no value of N for which the chip does this.

Clyde
07-08-2006, 01:26 PM
It's impossible, even if you isolate bits of hardware. You don't know whether a chip retains information from what was typed in 30 days ago, or 2000000 years ago, and there's no way you can guarantee that it doesn't. Perhaps one chip says that every Nth keypress, where N = 5 trillion, it shifts the letter value by 1. You could not prove that there is no value of N for which the chip does this.


But if i can look inside the chip (say with an electron microscope) if i can see the physical structure of the gates (there are gates in chips right?) then can i work out what any chip is going in a reasonable amount of time? Or is it still impossible?

Mario F.
07-08-2006, 01:59 PM
If the technology is right I think it's common sense to believe that it's always possible to determine the whole from the parts. No matter how nuclear the parts may be.

Clyde
07-08-2006, 02:33 PM
If the technology is right I think it's common sense to believe that it's always possible to determine the whole from the parts. No matter how nuclear the parts may be.


So armed with a good enough microscope and a complete knowledge of the computational theory and the relevent physics but without knowing any of the syntax of any languages, you could reconstruct the logic of say windows XP if i gave you a PC with it installed on (assuming your microscope is able to measure without destroying) within say 100 years. Feasible, or stupendously ridiculous?

SlyMaelstrom
07-08-2006, 02:39 PM
Why do I feel like for the past week and a half Clyde has been sitting in front of a homework paper with a check box for "Yes" and one for "No" waiting for a straight answer? :p

Mario F.
07-08-2006, 02:58 PM
Clyde, Turing machines are a theory largely based on imagined scenarios. It's probably the closest thing we have to "computational psychology" (if such a thing existed).

So the answer is... anything is possible.
And mainly this is so because... turing machines don't exist.

In an imagined scenario where turing machines existed, of course the answer is a sound 'yes'. What else?

Clyde
07-08-2006, 03:54 PM
Why do I feel like for the past week and a half Clyde has been sitting in front of a homework paper with a check box for "Yes" and one for "No" waiting for a straight answer?


I'm way past homework :). The question was actually motivated by reading neuroscience stuff.



So the answer is... anything is possible.
And mainly this is so because... turing machines don't exist.


Really? I thought computers used the Von Neuman architecture and the Von Neuman architecture was a way of making a universal turing machine. I thought my PC was a universal Turing machine. I've made a mistake?

Mario F.
07-08-2006, 04:23 PM
Yup. You've made a mistake. Your computer is not a Turing Machine (http://en.wikipedia.org/wiki/Turing_machine#Comparison_with_real_machines), much less an UTM.

shintaro
07-10-2006, 04:42 AM
Wouldnt the Altair computer be a better test for binary calculations that a Turing machine? You can download simulators of the Altair at sites like this:
http://incolor.inetnebr.com/bill_r/computer_simulators.htm

I really dont understand the significance of the Turing machine in computer theory, it uses symbols instead of zeros and ones, so what is to limit the complexity of the alphabet in this set of symbols?

Clyde
07-10-2006, 05:46 AM
Yup. You've made a mistake. Your computer is not a Turing Machine, much less an UTM.


Cool, thanks for the link, now i must discover why this:



The difference lies only with the ability of a Turing machine to manipulate an unbounded amount of data. However, given a finite amount of time, a Turing machine (like a real machine) can only manipulate a finite amount of data.


leads to this:



One way in which Turing machines are a poor model for programs is that many real programs, such as operating systems and word processors, are written to receive unbounded input over time, and therefore do not halt. Turing machines do not model such ongoing computation well (but can still model portions of it, such as individual procedures).


I'm not sure it really alters the natyre of my question, - which is basically given all the physical information is it always feasible to unravel the underlying logic. Never the less i am gratefull for the clarification.

Mario F.
07-10-2006, 07:10 AM
It may look like a contradiction at first. However, the answer lies a few paragraphs before.

Arguably this is an hard concept to understand, since our brain cannot model very well the workings of a Turing machine. Only maths can model it. This is ironic because our brain is probably the only turing machine currently in existence in the world. However, I belive the key in understanding TMs and the answer to that apparent contradiction you explored is that TMs, contrary to any man-made machine to date, are not finit deterministic machines.

In the world of machines to this date, given a current state and a condition, you can only have one transition state. We observe this behavior in the real world out there; A door is closed. If we open it we set an open state. And if we close it we set a close state. We can at best formulate from this state machine and expand it using other state processes. If the door is open a draft state is set. If it is closed the draft state is cancelled. However each transition state table is a contained finit and deterministic unit. Computers simply cannot process infinit non-deterministic states. That's what intelligence does.

The maths behind the description of finit state machines and turing machines are well beyond my capabilities. However, the resulting concept is more or less the above.

A turing machine is not necessarily a sentient being though. It is simply an hypothesis of a machine that can process infinit and non-deterministic states. A turing machine would probably, for instance, be able to produce random numbers much the same way we humans do, however it would be incapable of using that information for anything more than what it was programmed to do.

We can simulate turing machines by tricking our computers (and our brains) into thinking we are working with an infinit non-deterministic set of information and states. However, it's all hocus pocus. As the random tables in any computer are. Just a trick to simulate.

We cannot build turing machines... yet.

Clyde
07-10-2006, 07:30 AM
Computers simply cannot process infinit non-deterministic states. That's what intelligence does.


Hmm i must confess that I don't think intelligence processes an infinite number of states - presumably a neuron can only be a finite (though possibly absurdly large) number of states.



It is simply an hypothesis of a machine that can process infinit and non-deterministic states.


I understand why you refer to the infinite part bit but i'm pretty sure there are both deterministic and non-deterministic turing machines. Which checking wiki seems to be right:

http://en.wikipedia.org/wiki/Turing_machine#Deterministic_and_non-deterministic_Turing_machines

So i'm not so sure whether the non-determinsitic part is necessarily the important bit.

Thanks for explaining your view though.