Timeline for Can computers do things Turing machines can't?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 6, 2018 at 3:16 | comment | added | Tim B II | Let us continue this discussion in chat. | |
| Feb 6, 2018 at 3:12 | comment | added | Roddus | And possibly my understanding. I've spent the last 18 years including 10 in post-grad research trying (foolishly?) to explain what the extra thing is. It's been hard getting out of the computational mode of thinking about the problem. Hence the question, Can computers do things TMs can't (TMs being probably the accepted definition of machine computation). Just off-hand, I'm not sure Turing machines can run the simple program described above. They have to scan ("identify") a symbol in order to manipulate it, but the small program doesn't, in part, seem to do this. | |
| Feb 6, 2018 at 2:54 | comment | added | Tim B II | While I agree with your synopsis, it's a can of worms I've opened many times on this site. Mathematically, it's possible that our ability to learn and make our own choices is all an illusion. Empirically, I agree with you; something more is happening. Regardless, the machine we call a computer cannot extend itself past its programming although we can emulate that phenomenon pretty convincingly. The question then becomes whether or not we're merely emulating that same phenomenon so convincingly that we've even fooled ourselves, but that's WELL beyond the scope of your question. :) | |
| Feb 6, 2018 at 2:45 | comment | added | Roddus | On your point that the program would ALWAYS do the same thing to the same inputs. That's right. Presumably the neural processes (programs) that process neural inputs always do the same things to the same inputs, too. But the point is that depending on the inputs, the MACHINE does different things. The program never learns. It's the machine that learns. In other words, the machine brain is more than hardware plus software. There's something else there. And learning is embodied in this extra thing. (I made this comment just before your last one) | |
| Feb 6, 2018 at 2:43 | comment | added | Tim B II | Yep, that's exactly what I'm saying. When I read Turing's paper, I'm accumulating knowledge. When I integrate that knowledge into my understanding of algorithms and how computers work to change the way I do or think something, that's learning. Another way of putting that is that a HDD full of data hasn't 'learnt' anything more than a blank HDD because neither HDD can change its behaviour as a result of the data contained within. Neither can a computer program running against either HDD, it just does what it's programmed to do against a defined input. | |
| Feb 6, 2018 at 2:35 | comment | added | Roddus | Turing in his 1950 paper raised the issue of learning, saying that learning is a case of the rules of operation of the machine changing, and how was this possible since the rules of operation (program) are fixed from the start no matter what the machine's history might be. (Then the posited "ephemerally valid" rules to explain learning - whatever they might be). My small program doesn't change and treats all input the same way. Is this what you mean? That learning is a change in rules, and if no change then (by definition of "learning") learning doesn't happen? | |
| Feb 6, 2018 at 2:25 | comment | added | Tim B II | No, actually the machine hasn't learned from experience, it's reacted in a predetermined way to changes in the input data. That the program is at least in part responsible for the change in the input state is irrelevant. The program would ALWAYS do the same thing to the same inputs, regardless of how those inputs were created. This is why hacking is possible; computers don't actually know anything about the data; it's an input to a set of instructions and while we may observe what looks like data dependent behaviour, it's merely value driven conditional processing. | |
| Feb 6, 2018 at 2:16 | comment | added | Roddus | But the program doesn't change. And the whole small program runs. It doesn't know (or care) what is stored in loc. 1 or 2. But the behaviour of the machine does change (is different from session to session). Hence the machine's behavior can't be explained by the program. Something else has to explain it. The something else is the content of the input stream (and by extension, if it came from a sensor, then the something else is the sensed environment). So the machine has learned from its experience. So does this mean that the idea of the Turing machine can't explain learning from experience? | |
| Feb 6, 2018 at 1:41 | comment | added | Tim B II | I understand what you're saying, but the issue I have with it is that programming takes into account variables that have different values at different states, including input. the outputs will change according to the inputs, yes, and even the steps that the program takes are different, but the scope of the program has not changed. That you change the inputs only means that different parts of the same program run at different times, not that the application has changed how it would handle either input | |
| Feb 6, 2018 at 1:35 | comment | added | Roddus | Hi Tim B I'm not sure I completely understand your comment, but how about this reply: The machine has a simple program. All it does is take the first two input symbols to arrive and stores them in locations 1 and 2. All further input symbols are compared to the one at loc. 1. In the event of a match, the machine emits as output a copy of the symbol in loc. 2. Isn't the machine's behaviour dependent on the input data, not the program (or not just the program)? Running a new instance of the program will almost certainly result in different machine behaviour (the input stream is variable). | |
| Feb 6, 2018 at 1:20 | comment | added | Tim B II | Hi Roddus. Your explanation is exactly why we can't say determine their behaviour. Even Neural Networks are Finite State Machines, and how different values trigger movement between those states is defined in advance. The sheer complexity of the code behind a Neural Network can make it appear that new data can change the programmed output but the core program doesn't change, and if you run the same data through it with the same random seed, you'll get the EXACT same outputs, every time because the process is still deterministic. | |
| Feb 6, 2018 at 1:02 | comment | added | Roddus | Tim B II You say "...computers can accumulate new data and can use that data to drive their behaviour, but only according to the rules of a Turing machine" But what about instead of "drive their behaviour", we say determine their behaviour. New data can determine behaviour - but doesn't that contradict Turing's theory of the Turing machine? A UTM runs a description of a TM. This description (program) defines the input-output behaviour of the UTM, whatever that behaviour might be, present, past and future. But can't new data change that definition of input-output behaviour? | |
| Feb 5, 2018 at 23:46 | history | answered | Tim B II | CC BY-SA 3.0 |