patternMinor
Can the mind be a finite automata and still invent the Turing machine?
Viewed 0 times
canfinitetheautomataturingmindmachineandstillinvent
Problem
The Turing machine was invented by a human mind. Presumably, nothing less powerful than a Turing machine can invent a Turing machine.
However, a Turing machine has infinite tape, whereas the mind is situated in a finite universe, and thus can only be a TM with finite tape. A TM with finite tape can be simulated by a finite automata, which is strictly less powerful than a Turing Machine. This seems to imply that a Turing machine was invented by an automata that is less powerful than a Turing machine, contradicting the initial premise.
Is this a problem? Or, is the initial premise false? Is it possible for a finite automata to somehow "invent" a machine that is more powerful, a kind of bootstrapping, if you will?
While it is difficult to formally define "invent," it does not seem a finite automata can even represent finite TMs effectively. For example, on the wikipedia page, it states a DFA will require quadrillions of states to represent a TM with a few hundred states. So, to even just represent the useful subset of halting TMs, my impression is that a DFA representation will probably exceed any computational capacity we have. There appears a big disconnect between DFAs and TMs, such that it is hard to imagine a plausible bootstrapping to go from one to the other.
There is also the related issue of how a finite automata can prove the halting problem for TMs.
However, a Turing machine has infinite tape, whereas the mind is situated in a finite universe, and thus can only be a TM with finite tape. A TM with finite tape can be simulated by a finite automata, which is strictly less powerful than a Turing Machine. This seems to imply that a Turing machine was invented by an automata that is less powerful than a Turing machine, contradicting the initial premise.
Is this a problem? Or, is the initial premise false? Is it possible for a finite automata to somehow "invent" a machine that is more powerful, a kind of bootstrapping, if you will?
While it is difficult to formally define "invent," it does not seem a finite automata can even represent finite TMs effectively. For example, on the wikipedia page, it states a DFA will require quadrillions of states to represent a TM with a few hundred states. So, to even just represent the useful subset of halting TMs, my impression is that a DFA representation will probably exceed any computational capacity we have. There appears a big disconnect between DFAs and TMs, such that it is hard to imagine a plausible bootstrapping to go from one to the other.
There is also the related issue of how a finite automata can prove the halting problem for TMs.
Solution
Some Turing Machine Details
Can a weak system invent a stronger one?
The answer here, I think, is yes, depending on your definition. For example, the language of all valid Turing Machines can be described using a context-free grammar, a computationally weaker formalization. You can even describe a regular language that describes what a valid Turing Machine looks like, and they're finite. (Spoiler alert, this doesn't say much, because you can map each integer onto a Turing Machine, so the regular language $\{0,1\}^*$ can be the set of all valid Turing Machines).
And, it's important to distinguish recognizing a thing, or inventing a description of something, and inventing all the things. We can recognize what a Turing machine is, but we can't see all of them, and because of things like the Halting problem, we certainly can't even understand all of them.
Other Infinite Things
This question is ultimately no different than asking how a finite mind could understand the natural numbers, or the function $y=x$ in $\mathbb{R}^2$. Both are infinite, but can be described in finite ways.
But, there are functions and sets and real number and such that are truly infinite, that can never be described by any possible spoken or written formula (because there are uncountably many reals, but countably many finite sentences in any human language.) And there are more true theorems than there are proofs, a la Gödel.
So we can describe infinity, and speak of its properties, perhaps without truly understanding it, at least without understanding every facet of it.
- A Turing Machine does not have infinite tape, it has unbounded tape. There is no limit to how many symbols can be stored on it, but at any given time, only a finite number of symbols are ever on the tape. So while we cannot conceive of all runs of a machine, we can always conceive at least some states of the machine.
- In a sense, Turing Machines carve out the "finite" portion of all languages, in the sense that it carves out the portion that can be finitely represented (by a Turing Machine). There are uncountably many languages, but countably many Turing Machines, so there's a bunch of stuff we will never understand because it is truly infinite, in too big of an infinity.
- Most problems that we can conceive of don't actually require the power of a Turing Machine. Many can be written using primitive recursion or other well-founded recursion schemes. So most algorithms don't actually require the infinite-ness of Turing Machines.
- For a Turing Machine that halts, there is always a function describing the max amount of memory used in relation to the input size. So we don't need to understand infinity, we simply need to understand the relationship.
Can a weak system invent a stronger one?
The answer here, I think, is yes, depending on your definition. For example, the language of all valid Turing Machines can be described using a context-free grammar, a computationally weaker formalization. You can even describe a regular language that describes what a valid Turing Machine looks like, and they're finite. (Spoiler alert, this doesn't say much, because you can map each integer onto a Turing Machine, so the regular language $\{0,1\}^*$ can be the set of all valid Turing Machines).
And, it's important to distinguish recognizing a thing, or inventing a description of something, and inventing all the things. We can recognize what a Turing machine is, but we can't see all of them, and because of things like the Halting problem, we certainly can't even understand all of them.
Other Infinite Things
This question is ultimately no different than asking how a finite mind could understand the natural numbers, or the function $y=x$ in $\mathbb{R}^2$. Both are infinite, but can be described in finite ways.
But, there are functions and sets and real number and such that are truly infinite, that can never be described by any possible spoken or written formula (because there are uncountably many reals, but countably many finite sentences in any human language.) And there are more true theorems than there are proofs, a la Gödel.
So we can describe infinity, and speak of its properties, perhaps without truly understanding it, at least without understanding every facet of it.
Context
StackExchange Computer Science Q#75553, answer score: 7
Revisions (0)
No revisions yet.