Today's electronic digital computers are often referred to as universal Turing machines. That is, the concept of the UTM is used to understand today's stored-program electronic digital computers. But is this concept adequate? In fact can today's computers do things that UTM's can't do? If they can do more than a UTM can do, it could be important to AI, since AI (and Searle and his Chinese room argument) use the UTM concept to define the abilities of AI's research and development platform - the electronic digital computer.
37
-
1Turing machine is an abstraction, and electronic computers are physically implemented, so they can perform physical actions and affect physical things, like keyboards and monitors, they can visualize their outputs, while Turing machine can not, they can do equivalent tasks much faster, etc. However, theoretically any program a computer can execute can be in principle executed by a (physical realization of) a Turing machine.– ConifoldCommented Feb 6, 2018 at 0:58
-
3@Roddus As a mathy abstraction a Turing machine has infinite tape, so your question should probably be the other way round :)– ngnCommented Feb 6, 2018 at 3:53
-
Today's computers, no. However, there are problems that have answers that today's computers can't solve. It's theoretically possible someone will create a "magic" computer (that looks very different from a Turing machine) that can answer these questions.– user935Commented Feb 8, 2018 at 18:51
-
Create heat. Take up space. Break down. Run out of memory.– user9166Commented Feb 9, 2018 at 2:40
-
@jobermark Running out of memory i'd agree with. But a TM would be really easy to make (more tape being added whenever needed) and the motor would generate heat, the machine would take up space,... I was thinking more about random access memory and actually receiving input. And anything else?– RoddusCommented Feb 10, 2018 at 10:29
|
Show 32 more comments
1 Answer
Short answer is no; modern computers cannot do things that Turing machines can't do. What they can do is run very sophisticated, complex Turing machines that simulate things that Turing machines would not be able to do.
This is an important point; Artificial Neural Networks, Genetic Algorithms, Fuzzy Logic Algorithms, and all the other types of 'machine learning' and 'artificial intelligence' mechanisms that computers can execute are still deterministic and algorithmic in nature. They still run a strict series of commands, and most importantly do not deviate from those commands no matter what. They're good at solving NP (Non-Polynomial) problems only insofar as they emulate the process that a human would undertake, but that emulation isn't perfect and may never be. Even the 'random' elements in a Genetic Algorithm isn't truly random; you seed an ordered (but seemingly random) list of numbers with a starting value and every call for a random number is taken from this list from a point determined by the seed value.
In that sense, computers can accumulate new data and can use that data to drive their behaviour, but only according to the rules of a Turing machine. In that sense, the computer cannot extend itself beyond its programming, even though it may seemingly emulate that capacity by the way it uses the data it accumulates.
There is some debate going on now as to whether or not a quantum computer will break that model, but then if it does, then it's not a 'classical computer' and we will have only used the name 'computer' for it to extend a metaphor that we already understand. That said, whether or not a quantum computer can operate in a non-deterministic way will be a very interesting question to try and answer in due course.
-
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?– RoddusCommented Feb 6, 2018 at 1:02
-
1Hi 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.– Tim B IICommented Feb 6, 2018 at 1:20
-
2No, 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.– Tim B IICommented Feb 6, 2018 at 2:25
-
1On 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)– RoddusCommented Feb 6, 2018 at 2:45
-
1