7
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Mathematics is a finite (in endless time, enumerable) system whose objects can be far more infinite, starting with the real numbers. How can mathematics possibly exist? $\endgroup$
    – Thumbnail
    May 18, 2017 at 10:18
  • $\begingroup$ Maybe you're basing your analysis on the wrong assumptions that the human brain has a finite tape :) $\endgroup$
    – Federico Ponzi
    May 19, 2017 at 17:21

2 Answers 2

Reset to default
3
$\begingroup$

You do indeed have a premise problem. We are not FSMs or TMs. Don't forget that all of these computational theory devices are simple mathematical abstractions composed of a series of axioms and limited input. The computational theory systems (Godel's, Turing's, and Church's) are merely designed to allow us to make proofs about whether certain kinds of functions are computable or not.

By contrast, we:

  1. filter through literally infinite information
  2. possess consciousness (whatever that means)
  3. exist in the physical world

One simple proof that we are not TMs is what you've just outlined: we can invent Turing Machines, but Turing Machines cannot invent us in turn. It is absolutely trivial for us to see the endpoint of an infinity of TM configurations before they run (though there also exist infinite TMs that we cannot see the endpoint for), but no TM can trivially determine the endpoint of a human before he or she lives.

There's a saying from cartography that can be very useful here: The Map is Not the Territory

These axiomatic systems are very cleverly designed to get at some tiny (albeit important) set of ideas, but trying to reduce a human to a Turing Machine's 7-tuple and short series of axioms makes about as much sense as reducing humans to any other abstract axiomatic system. While these systems are useful for seeing aspects of the real world, they are not complete pictures, and we are not Finite State Machines or Turing Machines any more than we are Number Theory or Set Theory.

Improve this answer
$\endgroup$
8
  • $\begingroup$ It's pretty questionable that we filter through infinite information. There may be infinite information in the real world, but only a finite amount of it is detected by our senses. All our senses have limited resolution. $\endgroup$
    – jmite
    May 18, 2017 at 3:39
  • $\begingroup$ It is nevertheless true. There are, at any moment, an infinity of things that you could turn your attention (your primary mode of filtration) to, both internal and external. You can even turn your attention towards things that your senses cannot detect directly, and as a species, we have a propensity towards finding ways of converting virtually anything from that undetectable set of information into something that we ultimately can detect. $\endgroup$
    – Ben I.
    May 18, 2017 at 11:20
  • $\begingroup$ These are good points, but humans exist within the physical universe, and all physical laws can be simulated on a Turing Machine. Thus, it would seem that humans are at least reducible to Turing Machines. How can a human be reduced to a TM, yet be capable of actions that a TM cannot do? Either the reduction is impossible and humans are to some degree non-physical, or TMs can do everything humans can do. $\endgroup$
    – yters
    May 18, 2017 at 14:40
  • 1
    $\begingroup$ But, nature can create a circle with resolution upto Plank length only. Real debate is if the natural laws, as we understand now, merely describe transformations of information from one state to the next, then what constitutes the state. $\endgroup$
    – Devendra Bhave
    May 20, 2017 at 12:58
  • 1
    $\begingroup$ @yters, It is clearly possible that not everything in the universe is fully deterministic. I used quantum wavefunction collapse as an example not because it is indeterministic, but because whether it is deterministic is currently an open question. Even if it turns out to be, however, that does not make guarantees about the rest of the universe. Second, the only conclusion I can see from "everything is accurately modelable" is that then the entire universe is a FSM with no more input; we are simply running on $\epsilon$ transitions until we will, at some point, either halt or loop. $\endgroup$
    – Ben I.
    May 22, 2017 at 21:06
6
$\begingroup$

Some Turing Machine Details

  • 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – yters
    May 18, 2017 at 14:31
  • $\begingroup$ @yters But that's the point of my answer. There's a huge difference between being able to simulate all steps of a Turing Machine, and being able to simulate what it means to be a Turing Machine. You can finitely represent a Turing Machine without running it. DFAs are bad at running Turing Machines, but are just fine at understanding what it means to be a Turing Machine. $\endgroup$
    – jmite
    May 18, 2017 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.