Timeline for Can computers do things Turing machines can't?
Current License: CC BY-SA 3.0
39 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 2, 2018 at 1:08 | comment | added | user9166 | The advantage of the UTM is simply that it is easy to specify and has very restrictive rules. So for issues of absolute possibility and impossiblity, it is the earmark example (Turing was focussed on proving an impossible problem impossible). For issues of comparative performance, people usually fall back on recursive functions (Kleene was concerned with constructive and applied math). For issues related to abstract descriptions of behavior and relative complexity of expression, they often fall back on relational algebra concepts like combinators.... | |
| Mar 2, 2018 at 1:04 | comment | added | user9166 | So no, there is not one way to look at computers: recursive functions, lambda calculus, general deductive systems, universal algebra, the theory relational forms, the category of cartesian closed categories, the abstract semantics of open types, the topology of marked discrete tilings of a plane, etc. etc. etc. are all ways of looking these phenomena. And they are all isomorphic to UTMs. But each one of them lets us look at these things from a different vantage point and makes different problems harder or easier to depict. | |
| Mar 2, 2018 at 0:51 | comment | added | user9166 | It could, and if those relationships are between discrete entities, the result would be provably isomorphic to a UTM. So why not look at a UTM as a device which creates instances of associative relationships? Oh, right. People already have, through relational and universal algebras. The paper I cited gives five very unrelated ways of looking at these phenomena, all isomorphic to UTMs, but having different strengths. Did you even follow the link? Do you care to listen, or should we all just stop talking? You seem bent on just not hearing. | |
| Mar 2, 2018 at 0:07 | comment | added | Roddus | @jobermark This is a basic question I'm interested in. The concept of the UTM is used to understand the actual particular electronic devices, computers. Could other quite different concepts be used to understand these same devices? Is the UTM the only idea we have with which to understand the machine? What about the concept of association of particulars? Could the machine be usefully understood as a device which creates instances of associative relationships? | |
| Feb 26, 2018 at 16:29 | comment | added | user9166 | @Roddus only to the extent that device has chaotic or analogue components. To the degree a digital computer is digital it is isomorphic to a UTM. Electronics that is not digital is not generally considered a computer in modern parlance. There is a certain degree of refusing to understand what you don't want to admit going on here. | |
| Feb 24, 2018 at 8:30 | comment | added | Roddus | @jobermark Thanks. So the idea of assignment abstracts away from causal specifics. Or assignment can be realized in different causations. I suppose some would say that that's the main value of abstraction (and the language will indicate the specifics by its context). And Turing machines (UTMs) are the most useful? ultimate? most accurate? abstraction of the stored program electronic digital computer? But it still seems possible that UTMs don't reflect (or whatever the right word is) everything computers can do. There seems to be an independence between the UTM and the electronic device. | |
| Feb 19, 2018 at 20:25 | comment | added | user9166 | We use UTMs as a model to remove all of this ambiguous talk, since the same things can be accomplished so many different ways that we cannot know exactly what we mean when we talk about something as simple as 'assignment' -- Does it move the contents? Does it change pointers? Does it just clue the compiler that two things are the same, without any real effect at execution time? Won't the language just choose that by context? Sticking to the most constrained and least powerful model keeps us from saying pointless nonsense. | |
| Feb 19, 2018 at 20:22 | comment | added | user9166 | This discussion of reference and identification falls apart when you realize that most languages are going to assign $a=$b by letting the two symbols point to the same address. The symbols a and b and the address have been 'identified' but there is no concept of their contents at all. The question is so ungrounded that it is meaningless to ask whether and how 'the contents' are 'identified' or not. | |
| Feb 18, 2018 at 21:21 | comment | added | Conifold | More or less, we could of course have a physical theory for what goes on inside the black box but it may be computationally (in the abstract sense) intractable to employ it. Neural nets are often used as black boxes even though in principle they could be analyzed computationally. | |
| Feb 16, 2018 at 21:43 | comment | added | ngn | @Roddus FHE is more than the mail sorter you describe. It can compute on the content of the envelopes without opening them. | |
| Feb 16, 2018 at 15:36 | comment | added | user9166 | Here is a basic example. drona.csa.iisc.ernet.in/~deepakd/atc-2008/murec.pdf. (But, all told, looking up basic coursework for undergrad math classes is something you should just do for yourself.) . Given that all bit manipulation instructions are recursive functions, this applies to the whole range of digital machines. Analog machines fall under a different rubric, and to the extent they logically process Real numbers rather than integers and allow for real randomness they are not covered by this result. | |
| Feb 16, 2018 at 9:46 | comment | added | Roddus | @Conifold so "empirically certain " means an inductive inference? And the specifications are Skinnerian stimulus-response (input-output) type specifications? Computation = " transformation of inputs into outputs according to transcription rules". That's helpful. So for the analogue black-box computer the rules are unknown, and inductive inference implies invariant rules and hence invariant input-output pairing. | |
| Feb 16, 2018 at 9:35 | comment | added | Roddus | @jobermark "bit-manipulation and UTMs are fully equivalent". OK. Could you give a link to the formal proof? | |
| Feb 16, 2018 at 7:24 | comment | added | Roddus | @ngn just taking the idea of blind signing a ciphertext, suppose a machine at a post office reads the addresses on the outside of envelopes that arrive through the post, then shoots the envelopes into different bins according to some element of the address, say country. That machine presumably computes on the addresses, but does it compute on the symbols sealed inside the envelopes? Presumably not. How is this different from the following variable assignment: a$ = b$? Does the program compute on the contents of b$? | |
| Feb 14, 2018 at 20:46 | comment | added | Conifold | This is the narrow meaning of "computation" in this theory. If we are using an analog computer then it can employ a black box causal process for the transformation. As long as we are empirically certain that the result accords with our specifications we do not need to worry as to what is inside the box. But then it is not susceptible to theoretical analysis as a computation either. | |
| Feb 14, 2018 at 17:01 | comment | added | user9166 | @Roddus We have a formal proof that bit-manipulation and UTMs are fully equivalent except for speed. Regarding speed, the primary difference would be the availability of randomness. Modern machines do not use it, but quantum machines would leverage it in spades. We also have NTM=DTM, so in principle a nondeterministic machine can be no more powerful than a deterministic one, but the combination of parallel processing and true randomness can theoretically be much faster. So 'can do' is still not adequately defined. | |
| Feb 14, 2018 at 9:54 | comment | added | ngn | @Roddus both TMs and computers can do fully homomorphic encryption | |
| Feb 14, 2018 at 8:07 | comment | added | Roddus | @jobermark I understand that the concept of the TM is in effect the definition of machine computation. I'm trying to look at the electronic computer as a causal system and ask, well, can it perform sorts of processing on symbols that TMs can't? I mean is there a fundamental difference? Or does the UTM fully explain the abilities, the possibilities, of the electronic device? | |
| Feb 14, 2018 at 7:58 | comment | added | Roddus | @Conifold the tokens that arrive from sensors are the objects digital sensors emit and which travel to the computer ('symbols'). Thanks for a definition of computation. I'll think about it. I'm trying to look at the physical machine as a causal system, and the concept of the symbol brings with it a lot of linguistic baggage (that Searle makes great use of). But if a computer can manipulate an input 'symbol' without transforming it into an output symbol according to a transcription rule, is the computer doing something other than computing on the symbol? | |
| Feb 14, 2018 at 7:36 | comment | added | Roddus | @ngn something like blind signing a homomorphic encryption. | |
| Feb 13, 2018 at 19:08 | comment | added | user9166 | @Roddus Turing machines are not physical objects. Period. If you built a physical model of one, it would not be one, any more than a machine that generates permutations is a group. As such they do not have a computation speed, and so linear and random=access memory are equivalent. | |
| Feb 13, 2018 at 1:17 | comment | added | Conifold | Computation is processing of symbols not matter so I am also not sure what your analogy is getting at. I am not sure what "tokens that arrive from sensors" are but what difference does it make of principle whether we consider them to be the input or add an extra layer of computation and view them as processed. Computation is defined as transformation of inputs into outputs according to transcription rules. Those are approximately implemented in physical computers, everything else that they do is irrelevant in this abstraction. So your empirical questions are not about computation. | |
| Feb 13, 2018 at 0:08 | comment | added | ngn | @Roddus When you say "blind", are you trying to describe something like fully homomorphic encryption? | |
| Feb 12, 2018 at 22:34 | comment | added | Roddus | @ngn By "without identifying the symbols" I mean can a TM do stuff to symbols - process them, manipulate them - without identifying them. I'm thinking about a computer program that can do this, e.g., var2 = var1. This copies whatever is in the variable (whatever is stored at the location named) var1 and writes it to var2. Can a TM do this sort of "blind" copy? Or does it have to identify the symbols in var1 then execute conditionals where the Scan operation is successful. E.g., if "1" is in var1 then does the TM have to execute the Scan conditionals: if "0" then ...; if "1" then ...? | |
| Feb 12, 2018 at 22:21 | comment | added | Roddus | @Conifold So when a meat grinder grinds meat, does that mean the meat grinder performs a computation on the meat? What I'm trying to get at is can a computer process tokens that arrive from sensors without performing computations on them? Is whatever a computer does to the input defined as "computation"? Or is "computation" defined in some other way without reference to what computers do? If so, the question "Do computers necessarily compute" Is empirical. And maybe they can process what the process without computing on what they process (and this has implications for the CRA). | |
| Feb 12, 2018 at 0:47 | comment | added | Conifold | Computation is by definition what transforms the input into the output, where they come from and where they go is abstracted from. You can assume that "the world" already scribed all the symbols on the tape that is fed to TM. For that matter, you can imagine that said tape is fed to it "in real time", but that makes no difference to what it does with it. | |
| Feb 12, 2018 at 0:38 | comment | added | Roddus | @Conifold That's interesting about the nature of computation. I'll look at the reference. Why is the source of the symbols not relevant to the nature of computation? (intuitively the source seems irrelevant, but can the intuition be explicated?) I'm thinking of symbols received by the TM from an external system, not symbols Printed on the tape by the TM itself (which could be considered input to the executing algorithm, but the source of this "input" is the TM itself). | |
| Feb 11, 2018 at 23:00 | comment | added | Conifold | Whether the input is in real time or pre-typed on the input tape is not relevant to the nature of computation. Issues with formalizing inputs and outputs for TM were discussed on Math SE: Input and output of a Turing machine. | |
| Feb 10, 2018 at 21:25 | comment | added | ngn | @Roddus a TM can simulate random access, only not as efficiently. I don't understand what you mean by "without identifying the symbols" in your last comment. Obviously, a TM must know at least the source/destination offsets on its tape in order to do copying. | |
| Feb 10, 2018 at 20:09 | comment | added | Roddus | @ngn cont. What about (in Basic) A$=B$ in other words copy the contents of variable B$ and store the copy in variable A$? The program has no idea what B$ contains. Can a TM perform a copy operation without identifying the symbols to be copied? Or in C: a=*b, take what is stored at b and assign it to a. Or in assembler, mov EAX, EBX, copy the contents of register EBX to register EAX. in all these programs the thing to be manipulated is not identified by the program. Can a Turing machine manipulate a symbol without identifying (scanning) it? | |
| Feb 10, 2018 at 19:48 | comment | added | Roddus | @ngn My interest in whether computers are Turing machines comes from Searle's Chinese room argument. He understands the electronic machine with the concepts of the universal Turing machine. But is the electronic digital computer a UTM? It's not (as I understand it) in the sense that UTMs have no random access memory (only Left, Right, one square at a time) and have no real-time input. But is there a program that will run on the electronic machine but which no Turing machine could run (ignoring RAM and a UTM's lack of input)? | |
| Feb 10, 2018 at 19:41 | comment | added | Roddus | @Conifold It's always seemed strange that Turing machines (as per Turing's 1936 paper) have no real-time input. The one that prints 0 1 0 1... has no input at all. The Universal machine has its S.D. (program) loaded and is input in this sense, but once the machine starts running the program, there is no input. (If there were, symbols would have to appear in empty squares as if by magic). I just wonder if there is something important about this lack of the possibility of real-time input in a 1936 Turing machine. | |
| Feb 10, 2018 at 10:29 | comment | added | Roddus | @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? | |
| Feb 9, 2018 at 2:40 | comment | added | user9166 | Create heat. Take up space. Break down. Run out of memory. | |
| Feb 8, 2018 at 18:51 | comment | added | user935 | 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. | |
| Feb 6, 2018 at 3:53 | comment | added | ngn | @Roddus As a mathy abstraction a Turing machine has infinite tape, so your question should probably be the other way round :) | |
| Feb 6, 2018 at 0:58 | comment | added | Conifold | Turing 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. | |
| Feb 5, 2018 at 23:46 | answer | added | Tim B II | timeline score: 5 | |
| Feb 5, 2018 at 22:22 | history | asked | Roddus | CC BY-SA 3.0 |