## Monday, July 29, 2024

### Computation: Math and the Church-Turing Thesis

(Part 9 in a series on the scientific method)

In the last installment of this series I addressed a philosophical question: what does it mean for a mathematical statement to be true?  I tackled this in the context of a general definition of scientific truth, namely, that a statement is true if it corresponds on some way to the actual state of affairs in objective reality.

(Note that this definition does not assume that objective reality exists.  It's possible that there is no objective reality, and that therefore there are no true statements under this definition.  But the existence of objective reality is, to put it mildly, a fairly well-established scientific theory, and so we're justified in proceeding on the assumption.  Spoiler alert: when we get to talking about quantum mechanics, we will encounter some data that calls the existence of objective reality into serious question, often leading to much philosophical hand-wringing.  I'm sweeping all that under the rug for now, but I wanted to be up-front about the fact that I am sweeping it under the rug.  I promise to unsweep it later.)

In this installment I want to talk about a different aspect of math, namely, how to explain its ubiquity in science.  In this series I have been trying very hard to avoid math because it tends to scare people away.  I think that's mainly due to very poor math pedagogy.  Math need not be any scarier than science itself.  One of the things I hope to accomplish here is to demystify math a bit and make it a little less intimidating.

So here I am going to approach the phenomenon of mathematics as a scientific Problem (with a capital P), namely: why is math so ubiquitous in science?  And why is it so alien and intimidating?

Let's start by asking: what actually is math?  It's hard to formulate a coherent definition.  Wikipedia says, "Mathematics is a field of study that discovers and organizes methods, theories and theorems that are developed and proved for the needs of empirical sciences and mathematics itself."  That might be technically correct, but it's not very illuminating, so instead of trying to define it, I'm going to sweep that under the rug as well and simply observe that math, kind of like pornography, seems to be an identifiable thing that most people recognize when they see it.

One of the characteristic features of math that makes it recognizable is its use of weird symbology, funny-looking squiggles, Greek letters, non-Greek letters written in distinctive fonts (and, of course, numbers).  Math also attaches meaning to the relative spatial relationship between symbols in ways that no other form of human communication follows.  x² means something very different from x₂ which means something very different from 2x.

But all this weird symbology is just window-dressing.  None of it is essential; it is possible to do math without it.  In fact, for most of human history math was done using plain old language, augmented with an occasional drawing.  The only "weird symbols" were numbers.  You can see this by perusing the original manuscript of Newton's Principia, the book that launched the modern scientific revolution.  It consists almost entirely of (latin) text and some drawings.  There is some math, but none of the notation goes beyond what you would find in an elementary-school math class.  The symbology used today only came into being in the last few hundred years.  It was invented because doing math with regular language was becoming too unwieldy.  The state-of-the-art technology for doing math at the time was pen and paper and chalkboards, and so the notation was optimized to allow a lot of information to be compressed into a minimal amount of space.  But what matters is not the symbology, but rather what the symbols mean.  "√3" means exactly the same thing as "the square root of 3", which means exactly the same thing as, "The number which, when multiplied by itself, gives you three."  The only reason to use "√3" is that it takes up less space and is faster to write by hand.

But there is more to math than just weird symbols.  Not all combinations of symbols make sense.  "√3" makes sense but "3√" doesn't.  It's no different from any other language.  "The square root of three" makes sense, but "three root square the of" does not.  Math notation is just another language, and it has grammatical rules just like any other language.

So what exactly is it about math that makes it special?  If the symbology is just window-dressing, and the grammatical rules are no different from natural language, what exactly is it that makes math such a powerful lever for doing science?  The answer is that in addition to grammatical rules, which tell you how to compose mathematical symbols so that they say something that makes sense (but isn't necessarily true), there is another set of rules in math that don't have a counterpart in natural language.  These rules tell you how to manipulate mathematical symbols to produce new mathematical truths, arrangements of symbols that correspond in some way to objective reality, from old ones.

The most familiar example of these rules is the algorithms we learn in elementary school for doing arithmetic.  Using these rules we can know, for example, that if we take (say) a hundred and ninety-two things and combine them (for some manner of combination) with (say) three hundred and seventeen things that we will end up with five hundred and nine things.  We figure this out not by thinking about the actual words that I wrote out, nor directly about the quantities those words denote, but instead in terms of the symbols "192+317=509".  By using these symbols and the right set of rules for manipulating them, we can figure out that 192 plus 317 is 509 a lot faster than we could if we tried to actually count these things.

The art of mathematics, the thing that keeps mathematicians employed, is figuring out what the right rules are.  That is a topic for another day, with a long and storied history.  The main point here is that the thing that makes math useful in science is not its notation, not the weird symbology, but the rules, the fact that it is possible to create sets of rules for manipulating symbols such that the behavior of the symbols corresponds reliably to the behavior of objective reality.  In other words, it is possible to create sets of rules for manipulating symbols that turn the symbols into a model of objective reality.  This turns out to be much more than just a handy-dandy way of producing models; it turns out to have some truly profound philosophical implications.  To see why, we need to take a brief historical detour.

In 1936, Alan Turing published a paper entitled "On Computable Numbers, with an Application to the Entscheidungsproblem" (which is German for "decision problem").  The title obscures what this paper is really about.  In it, Alan Turing invented software.

In 1936 the words "computer" and "calculator" did not refer to machines as they do today but rather to a profession.  A computer (or calculator) was a human who performed computations (or calculations), which is to say, who manipulated mathematical symbols according to rules.  The useful results of this process were generally numbers, which is why the title of Turing's paper refers to "computable numbers", but numbers are a red herring here.  What matters is not the numbers per se, but the symbols; that the symbols can be taken to stand for numbers is a mostly irrelevant detail.  What really matters is the rules by which the symbols are manipulated.

Turing's paper asks the question: what would happen if we tried to build a machine that does what (human) computers/calculators do?  He then goes on to describe a machine that would do just that.  The machine consists of a control mechanism which can be in any of a finite number of states.  These states encode the rules by which the machine manipulates symbols.  The machine has a sheet of paper divided into a grid.  Each square of the grid contains exactly one of a finite repertoire of symbols.  The symbols can be erased and re-written by the machine.  The supply of paper is endless.  (The technical term is "unbounded", which is not quite the same as "infinite".  It's more like there is a paper factory available that makes more paper as needed, but at any given time the actual amount of paper that the machine has to work with is finite.  The distinction between infinite and unbounded won't matter much here but will turn out to be crucial later on.)

The machine's operation is dead-simple.  At any given time, its control mechanism is in one of the possible states, and is "looking" at one square of the grid on the paper.  The control mechanism is just a big lookup table indexed by state and symbol.  Each entry in the table contains just three pieces of information: a symbol to write onto the paper in the current grid square (possibly the same as the symbol that is already there), a direction in which to move on the paper to arrive at a new grid square, and a new state for the control mechanism to go into.  That's it.

I've described Turing's machine in terms of a "sheet" of paper, but Turing's original paper and the literature in general refers to a one-dimensional "tape" rather than a two-dimensional "sheet".  This turns out not to matter.  You can think of the "tape" as being a "sheet" that has been cut up into strips and glued end-to-end.  The net result is the same in both cases.  But in order to conform to tradition, I'm going to switch my terminology and start using "tape" instead of "sheet".

Note that the control mechanism is part of the machine's hardware, and once built, it cannot be changed.  If you want to make a Turing machine that performs a different task, you need to build a new machine.  Or so it would seem at a casual glance.

The remarkable thing about Turing machines is that it is possible to create a control mechanism that is universal, that is, which allows one machine to perform the same computation as any Turing machine you can imagine without changing the hardware.  How does it do this?  By describing the control mechanism of another Turing machine as symbols on the tape.  The universal machine reads the description on the tape, and then behaves as if its control mechanism were the one described on the tape rather than the (universal) control mechanism that it actually has.

At first glance this seems like an interesting intellectual curiosity, but not one with earth-shattering consequences.  From our current vantage point in a world with ubiquitous computers it might even seem a little banal.  But the computer revolution we are living in is only possible because of the existence of universal Turing machines.  Computing and calculating machines existed before 1936, but they were all custom-made for a particular task.  But if you build a (universal) Turing machine, that is the last machine you will ever have to build.  After that, anything you can imagine that can be done by any Turing machine can be done just by writing symbols to a tape, that is, by writing software.  There are only three reasons to every build new hardware: to make the machine run faster, to make it more energy efficient, or if you want to do something that cannot be done by any Turing machine.

Let's think about that third possibility for a moment.  A universal Turing machine can do anything that any Turing machine can do, but that doesn't mean that it can do anything.  In fact, Turing himself showed that there are certain things that no Turing machine can do, like solve the Entscheidungsproblem or the closely related halting problem.  Might we be able to design a completely different machine that can solve these problems?

There is a word for such a machine: it is called an oracle for the decision problem (or the halting problem, or whatever).  But think about what it would take merely to design or even describe such a machine, let alone build one.  Such a design would have to be rendered into a phyical medium somehow; it would have to be written down, or carved into stone, or spoken aloud as an oral tradition, or something.  And if the design could be rendered into a physical medium, then it could be expressed in terms of symbols.  Maybe part of the design would consist of drawings, but a drawing can also be expressed in terms of symbols, specifically, in the form of a computer program (i.e. a Turing machine) that produces that drawing on a suitable display.  Nowadays just about every image you see is actually produced in this way.

Maybe there is some way of rendering a design that cannot be reduced to symbols?  There is no way to prove that this is impossible, but if you can come up with one, it would be one of the greatest breakthroughs in the history of human intellectual endeavor.  It is hard to imagine even what a description of such a breakthrough would look like.  Think about it: all of the information your brain has access to comes through your senses, primarily seeing and hearing.  But we already know that these can be reduced to symbols because we have computers that can produce any image or sound that we can imagine.  Not only that, but we also have digital cameras and digital microphones, so computers can reproduce not only any image or sound that we can imagine, but also any image or sound that can possibly be produced in this universe.  If it exists in this universe, then we can record it or take a picture of it, and thus reproduce it on a computer.

We can stretch our imaginations even further.  Maybe we cannot design or describe a machine that does something a Turing machine cannot do, but maybe we can produce such a machine by some other means.  Maybe there exists a natural phenomenon in our universe whose behavior cannot be described by symbols.  Again, it is hard to imagine what such a phenomenon would even look like.  It would not be possible to describe such a phenomenon in terms of measurements because all measurements can be rendered as symbols.  It would even be impossible to describe such a phenomenon using words, because words are symbols.  So such a phenomenon would have to be radically different from anything in our day-to-day experience.  It is, of course, impossible to prove that there does not exist something beyond the bounds of our imaginations.  But that is what it would take to produce a machine that transcends the Turing machine.  (I'm going to start referring to such a machine as a Transcendant Turing Mahchine or TTM.)

Now, there is actually a candidate for a natural phenomenon that, at least as if this writing, transcends our current understanding, and that might therefore be a TTM, or at least a signpost on the road to a TTM: the human brain.  In particular, human brains produce the phenomenon of consciousness (at least mine does).  Consciousness is a really weird thing, devilishly difficult to render into symbols or otherwise to get any kind of a handle on.  It's hard even to demonstrate that it actually exists despite the fact that everyone professes to experience it.  Consciousness at first glance has many of the characteristics we would expect from a phenomenon that indicates something happening beyond what can be described by Turing machines.  (There is another phenomenon that some people claim transcends TMs, and that is the phenomenon of life itself.  This is just demonstrably wrong, though demonstrating it is not easy, so that will have to wait for a future installment.)

For now I want to make one more observation: the important thing about Turing machines is not just that it is possible to build them, or even that it is possible to build a universal Turing machine.  The important thing about (universal) Turing machines is that building one is not particularly difficult.  Once you start building systems of any complexity at all, it is actually hard to avoid building a universal Turing machine.  You could make one out of Legos or wood.  The ones we build for actual use are made of sand.

The fact that UTMs are so simple and yet so powerful is a deep and profound observation not just about physical reality, but about what is logically possible.  No one ever builds Turing machines according to Turing's original description except for pedagogy or as a parlor trick.  The nature of Turing machines is as much in their description in terms of symbols as in the reifications of that description we humans have built in physical reality.  The fact that it is hard for us to even imagine what a Transcendent Turing Machine might look like is a deep insight.  It is the reason that math is so ubiquitous and effective in science.

The claim that everything that can be described can be described by a Turing machine is called the Church-Turing thesis.  (The "Church" part refers to Alonzo Church.)  The Thesis is not usually stated in this way; the more common formulation is that any computable function can be computed by a Turing machine.  But if you think about it, this amounts to the same thing.  If there were a function that could be computed (whatever that might mean) but not by a Turing machine, it would mean that there existed in this universe some physical phenomenon that could "compute" (whatever that might mean) some function that a Turing machine could not.  That is to say, this phenomenon would have to exhibit some behavior that a Turing machine could not emulate.

The Church-Turing thesis cannot be proven, but a persuasive counterexample has never been demonstrated.  If it's true (and if it isn't that would be Big News) then it places some hard constraints on what is possible in our universe, and that in turn has significant philosophical consequences.  Either the human brain is a TTM or it is not.  If it is, what exactly is happening in there that enables this transcendence?  Is the same thing happening elsewhere in the universe, like maybe in the brains of dolphins or elephants?  Intelligent aliens?  LLMs?  And if the behavior of our brains can be described by a Turing machine, what does that imply for our subjective experience of consciousness and free will?  Turing machines are, after all, deterministic.  If we're nothing more than machines following a program, how can we have moral agency?

Spoiler alert: these questions have answers.  We humans are not TTMs but we have moral agency nonetheless.  I promise I will get to that.  Stay tuned.

Publius said...

Does Not Compute

@Ron:
>(Sorry, I could not figure out a better way of getting Blogger to display a superscript or a subscript.)

>The art of mathematics, the thing that keeps mathematicians employed, is figuring out what the right rules are. That is a topic for another day, with a long and storied history. The main point here is that the thing that makes math useful in science is not its notation, not the weird symbology, but the rules, the fact that it is possible to create sets of rules for manipulating symbols such that the behavior of the symbols corresponds reliably to the behavior of objective reality. In other words, it is possible to create sets of rules for manipulating symbols that turn the symbols into a model of objective reality.

Except the rules of mathematics were not developed to model objective reality. So, then, why are mathematics so effective in describing it? This question of The Unreasonable Effectiveness of Mathematics in the Natural Sciences.

>If it exists in this universe, then we can record it or take a picture of it, and thus reproduce it on a computer.

How about a particle in a state of quantum superposition?

> Maybe there exists a natural phenomenon in our universe whose behavior cannot be described by symbols. Again, it is hard to imagine what such a phenomenon would even look like.

How about the taste of a strawberry?

>If there were a function that could be computed (whatever that might mean) but not by a Turing machine, it would mean that there existed in this universe some physical phenomenon that could "compute" (whatever that might mean) some function that a Turing machine could not. That is to say, this phenomenon would have to exhibit some behavior that a Turing machine could not emulate.

There are an uncountable infinity of uncomputable functions.

Turing machines can only compute rational numbers.

There are irrational numbers of which constitution that have no pattern at all (the absolutely normal real numbers). They are so numerous that, if a number is picked randomly between, for example, 0 and 1 in the real line, it will be an absolutely real number with probability 1 (and the probability of picking a computable number is 0) -- see How real are real numbers?

Physics uses real numbers. Hence spacetime and gravity are uncomputable with Turing machines.

Examples of physical phenomena that can "compute" functions that a Turing machine cannot are radio tuners (RC circuits in general), and sound propagation in air. Turing machines cannot compute the first derivative of continuously differentiable functions. See A computable ordinary differential equation which possesses no computable solutions and On the non-detectability of non-computability and degree of non-computability of solutions of circuit and wave equations on digital computers.

Ron said...

Thanks! I've edited the post accordingly.

> the rules of mathematics were not developed to model objective reality

Of course they were. Math was originally invented to measure land (that is literally what "geometry" means") and enumerate physical quantities like how many goats were in your paddock and how much grain was in your granaries.

> why are mathematics so effective in describing it?

That was the whole point of this post: it's because there is nothing else. Nothing in this universe is a TTM.

> How about a particle in a state of quantum superposition?

Yeah, remember Step 2 in the scientific method?

"Step 2: Make a list of all simplifying assumptions that you are going to make."

And remember how at one point I said I was going to ignore QM for now?

So yes, there is still the possibility that QM will invalidate everything I've said here. (Spoiler alert: it turns out that it doesn't.) You are right to hold my feet to this fire -- but not yet.

> How about the taste of a strawberry?

You must have missed this bit:

"Now, there is actually a candidate for a natural phenomenon that, at least as if this writing, transcends our current understanding, and that might therefore be a TTM, or at least a signpost on the road to a TTM: the human brain."

> There are an uncountable infinity of uncomputable functions.

Only in our imaginations, not in objective reality.

> Turing machines can only compute rational numbers.

That's not true. They can only compute the *decimal expansion* of rationals, but that is simply because they can only produce finite (though unbounded) output. But TMs can certainly compute irrationals, and even imaginary numbers. √3 is not rational, but if you think a TM can't compute it, allow me to introduce you to Wolfram Alpha.

> Physics uses real numbers.

Whether the reals are an accurate model of objective reality is very much an open question. The problems you get when you deal with infinities is exactly the reason most physicists believe that everything is quantized, including space and time.

> Examples of physical phenomena that can "compute" functions that a Turing machine cannot are radio tuners

Not even close. All electromagnetic phenomena are quantized.

Ron said...

@Publius: BTW, you might find this interesting.

Publius said...

Arithmetic, Logic, Set Theory, Probability

>> the rules of mathematics were not developed to model objective reality

@Ron:
>Of course they were.

Mathematics is the study of abstract objects. Why should those abstract objects be useful in solving real-world (concrete) problems?

>That was the whole point of this post: it's because there is nothing else.

I don't follow. There is nothing else than mathematics?

>> There are an uncountable infinity of uncomputable functions.

>Only in our imaginations, not in objective reality.

Well, for my purposes, I only need one uncomputable function to disprove you thesis.

However, your assertion of finiteism is not going to serve you well. If you assert there is no infinity, then:
1) what is the last uncomputable function?
2) what is the largest number?

>That's not true. They can only compute the *decimal expansion* of rationals, but that is simply because they can only produce finite (though unbounded) output.

Which is to admit there are certain numbers they can't calculate. The solutions to some physical systems are transcendental numbers, which a Turing machine can't calculate.

>But TMs can certainly compute irrationals

They can compute rational approximations to irrationals, to a predefined error bound -- which is typically what we only practically need. But they cannot compute the exact solution, which is often a transcendental number.

In addition, perhaps you missed the part about absolutely normal real numbers, which have no pattern to their digits, and therefore no algorithm to compute them -- and how most numbers are of this type. Hence there are an uncountable infinity of numbers that a Turing machine can't compute.

> √3 is not rational, but if you think a TM can't compute it, allow me to introduce you to Wolfram Alpha.

√3 is an algebraic irrational, a miniscule portion of the irrational numbers. Wolfram Alpha also doesn't run on a Turing machine, it runs on a Register machine. While Wolfram Alpha may use special software to compute real numbers, most decimal computations on computers use floating point numbers.

>The problems you get when you deal with infinities

What problems are those?

>Not even close. All electromagnetic phenomena are quantized.

The problem isn't electromagnetic phenomena, it's electronic circuits, and the inability of Turing machines to compute an exact simulation of them.

>BTW, you might find this interesting.

I think his reformulation of trigonometry makes it harder to teach.

Ron said...

> Mathematics is the study of abstract objects.

No, it isn't. There are many abstract objects that are outside the purview of mathematics. Ethics. Wizards. Warp drives. The thing that distinguishes mathematics from other fields of intellectual endeavor is that it involves the manipulation of symbols according to strict rules. Some (but not all) sets of rules turn out to be useful models of objective reality.

> Why should those abstract objects be useful in solving real-world (concrete) problems?

They aren't. It's the process of manipulating symbols according to the right rules that turns out to be useful. Why is that? No one knows. But it's a fact.

>> TMs can certainly compute irrationals

> they cannot compute the exact solution

They can't compute an exact decimal expansion. That is not the same as being unable to compute exact solutions. √3 * √3 is exactly 3.

BTW, being unable to compute an exact decimal expansion is not unique to irrationals. There are many rational numbers for which this is the case as well. 1/3 for example. And all this is contingent on the base you are using. It's impossible to write out an exact binary expansion of 1/10, to the perennial chagrin of newbie programmers.

> I don't follow. There is nothing else than mathematics?

That's right. There is no evidence for any physical phenomenon in our universe that cannot be modeled by a TM, and therefore no phenomenon that cannot be described by manipulating symbols according to rules, a.k.a. mathematics.

> I only need one uncomputable function to disprove you thesis.

No, you need evidence of something in our universe that can actually *compute* a function that a TM cannot. Good luck with that.

> The solutions to some physical systems are transcendental numbers, which a Turing machine can't calculate.

First, a TM cannot calculate the decimal expansion of a transcendental number, but that's just not a very interesting limitation. It cannot calculate the decimal expansion of 1/3 either. Second, the phrase "solutions to ... physical systems" is non-sensical. Physical systems have *behavior*, not "solutions". That behavior can be modeled by mathematical equations (a.k.a. systems of symbols that one manipulates according to rules) and those equations have solutions, but how do you know that those solutions are actually correct, i.e. how do you know that the exact solution is a better model of objective reality than some finite approximation? All the evidence points to the universe being quantized, not continuous.

> there are an uncountable infinity of numbers that a Turing machine can't compute

Yes, that's true. So?

> If you assert there is no infinity

You are confusing infinite with unbounded. TMs are unbounded, but they are not infinite. Infinity is what you get at the "end" of an unbounded process, but an unbounded process has no end, so this is a non-sensical concept.

> what is the largest number?

There is no largest natural number. And yet, every natural number is finite.

> The problem isn't electromagnetic phenomena, it's electronic circuits

Electronic circuits *are* electromagnetic phenomena. It's kind of like saying, "The problem isn't thermodynamics, it's internal combustion engines."

Publius said...

P E D A N T I C

>> Mathematics is the study of abstract objects.

@Ron:
>No, it isn't.

My statement "Mathematics is the study of abstract objects" is certainly true. Mathematics involves the exploration of concepts such as numbers, shapes, quantities, and patterns. This field relies on logical reasoning, symbolic representation, and rigorous proof techniques to understand and describe these abstract entities.

Only Pedantic Ron™ would interpret the everyday English sentence "Mathematics is the study of abstract objects" as referring to all abstract objects.

>> Why should those abstract objects be useful in solving real-world (concrete) problems?

>They aren't. It's the process of manipulating symbols according to the right rules that turns out to be useful. Why is that? No one knows. But it's a fact.

Let's break this down:

>They aren't.

then:

>It's the process of manipulating symbols according to the right rules that turns out to be useful.

How is this not contradicting yourself?

>They can't compute an exact decimal expansion.

Turing computable is defined as using a TM to calculate in finite computation steps a rational approximation |ũ - u| < ϵ, with ϵ being rational.

Turing machines can't even do that to simulate simple RC circuits (and is hopeless for more complicated networks, or for more complicated inputs). Furthermore, it's not possible for the Turing machine to detect when it has encountered a noncomputable function. The first derivative of computable differentiable functions are generally not computable.

>There is no evidence for any physical phenomenon in our universe that cannot be modeled by a TM

I've already given you you two -- simulating RC circuits and oh, saywhistling. You know how to whistle, don't you?

>No, you need evidence of something in our universe that can actually *compute* a function that a TM cannot.

When you tune your radio to 560 AM to listen to your favorite shows on KSFO, your radio tuner is an analog computer which is computing a function a TM cannot.

>You are confusing infinite with unbounded. TMs are unbounded, but they are not infinite. Infinity is what you get at the "end" of an unbounded process, but an unbounded process has no end, so this is a non-sensical concept.

You seem to have an Aristotelian concept on infinity as a potential infinity, or infinity as a process.

That doesn't work in today's mathematics. A simple example of where it fails is in this equality:

1.0 = 0.9...

That is, 1.0 is equal to repetitive 0.9, with the "..." indicating the "repetitive" notation, in which you have a decimal point, then an infinite number of 9s after it. Here is a slightly longer expansion of it:

1.0 = 0.9999999999999999999999999999999999999999999999999999...

For this to be true, you need an "complete", or absolute infinity.

Ron said...

> My statement "Mathematics is the study of abstract objects" is certainly true.

No, it is certainly not. It might be *a* study of abstract objects (even that is questionable), but it is certainly not *the* study of abstract objects. Abstract art, involves study of abstract objects, but it is not mathematics. The thing that distinguishes mathematics is that it involves the manipulation of symbols according to strict rules.

> Pedantic Ron

Final warning: the next time you level an ad hominem here I will stop publishing your comments.

> > They [the abstract concepts denoted by symbols] aren't [useful in solving real-world (concrete) problems]

> > It's the process of manipulating symbols according to the right rules that turns out to be useful.

> How is this not contradicting yourself?

Because symbols are different from the things they denote. Math is useful insofar as the symbols denote *concrete* things, things that can be measured. The abstractions might be useful for pedagogy, but the principal utility of math in science is that it allows you to accurately predict the results of experiments.

> Turing machines can't even do that to simulate simple RC circuits

The link you gave there is actually a very interesting result. Debunking it would take more than a comment. I'll have to write a separate post about it. But thanks for bringing this to my attention.

> For this to be true, you need an "complete", or absolute infinity.

No, I don't. The mere fact that you were able to make this claim in a Blogger comment proves that you are wrong. You wrote "0.9...", a finite string of symbols, to *denote* something infinite, but the thing you wrote to denote this is not infinite, and therefore it is manifestly not necessary to have a "completed" infinity to denote this particular infinite concept.

The only case in which a "completed" infinity is *necessary* is if you want to describe an object with infinite Kolmogorov complexity. The existence of such objects is in considerable doubt. You cannot exhibit one, or even describe one. You can only imagine one. But just because you can imagine something doesn't mean it actually exists. One can imagine an oracle for the halting problem too, that doesn't mean such a thing exists.

Publius said...

An Apology

@Ron:
>Final warning: the next time you level an ad hominem here I will stop publishing your comments.

I'm sorry Ron, I did not mean to level an ad hominem against you, or insult you in any way. Clearly I fell short. Please accept my apology.

>> My statement "Mathematics is the study of abstract objects" is certainly true.

>No, it is certainly not. It might be *a* study of abstract objects (even that is questionable), but it is certainly not *the* study of abstract objects.

Yet mathematicians only study abstract objects.

Let's revise it to make the verb form required:

Mathematicians study abstract objects. Why should those abstract objects be useful in solving real-world (concrete) problems?

>No, I don't. The mere fact that you were able to make this claim in a Blogger comment proves that you are wrong. You wrote "0.9...", a finite string of symbols, to *denote* something infinite, but the thing you wrote to denote this is not infinite, and therefore it is manifestly not necessary to have a "completed" infinity to denote this particular infinite concept.

To prove

1.0 = 0.9...

Requires an infinite repeating 9s after the decimal point. Otherwise, it's false.

Sure, I can't write down an infinite 0.9999..., but so what? Math often has restrictions on what can be done. Matrix multiplication isn't commutative. I can't divide complex numbers. For 0.9..., though, I can access every member of this infinite expansion -- for example, the 10^100th digit after the decimal point is "9".

"Potential infinities" don't work in mathematics.

Ron said...

> Yet mathematicians only study abstract objects.

No, they don't. Many (though not all) fields of mathematics started as studies of physical systems, including arithmetic, geometry, calculus, and probability theory.

> Mathematicians study abstract objects. Why should those abstract objects be useful in solving real-world (concrete) problems?

Because the method they use involves manipulating symbols according to rules, which is a process that can be conducted by a machine, which turns out to be capable of performing *any* task that can be described as a set of rules for manipulating symbols, which turns out to be all you can do in this universe.

> To prove

> 1.0 = 0.9...

> Requires an infinite repeating 9s after the decimal point.

No, it doesn't, because 0.9... is just notational shorthand for the sum of the infinite series 9/10 + 9/100 + 9/1000 etc. That sum is defined as a limit, which is in turn defined by a finite process.

Publius said...

Theory of Errors

>No, they don't. Many (though not all) fields of mathematics started as studies of physical systems, including arithmetic, geometry, calculus, and probability theory.

Yes, they do. It's odd you would provide a link to game theory, as you know that game rules are abstract, right? Right?

> which turns out to be all you can do in this universe.

Can't the universe do things that aren't describable by rules?

>No, it doesn't, because 0.9... is just notational shorthand for the sum of the infinite series 9/10 + 9/100 + 9/1000 etc. That sum is defined as a limit, which is in turn defined by a finite process.

A limit at infinity.

You should review Skepticism in education to determine which error you are making.

Ron said...

> you know that game rules are abstract, right?

No, I don't know that. I don't know what games are like now, but back in the day the rules of games were usually printed on actual paper. Nowadays it's all on line but that doesn't make it any more abstract than these comments.

> Can't the universe do things that aren't describable by rules?

Not that anyone has been able to demonstrate. If someone manages to do it that would be Big News.

> A limit at infinity.

That's just a label. There are no actual infinities involved.

Publius said...

The Talented Universe

>> Can't the universe do things that aren't describable by rules?

>Not that anyone has been able to demonstrate.

What about random processes? While we can describe the probabilities of different outcomes with mathematical rules, the specific outcome of a quantum event cannot be predicted with certainty.

We can partition space, or divide it into sections. The size of those partitions can be described by real numbers, and those real numbers are most assuredly absolutely normal real numbers, which have no pattern to their digits, and therefore not algorithm to compute them.

Gödel's Incompleteness Theorems: In mathematics, Gödel's incompleteness theorems state that in any sufficiently powerful formal system, there are true statements that cannot be proven within the system. This suggests that there are aspects of mathematical truth that cannot be fully captured by any single set of rules or algorithms.

Chaotic Systems: Some systems are highly sensitive to initial conditions, known as chaotic systems. While they are deterministic and can be described by rules, the complexity and sensitivity make long-term prediction practically impossible. This unpredictability can be seen as a form of limitation in rule-based descriptions.

Finally, Ron, tell me a fish story. Are their rules and algorithms for human creativity?

>That's just a label. There are no actual infinities involved.

Modern mathematics doesn't work without actual infinities.

One of the axioms of Zermelo-Fraenkel set theory (ZF) is the Axiom of infinity - there exists at least one infinite set.

The ontology of ZFC includes infinity.

Mathematicians don't focuse on Finitism anymore.

Ron said...

A TM with a random oracle can't compute anything that a deterministic TM can't, so random processes are not TTMs.

But I'm actually planning a whole chapter on random processes. Spoiler alert: there are two kinds of random process in our universe, stochastic processes and quantum processes. Stochastic processes are deterministic while quantum processes are truly random, but neither of these is experimentally distinguishable from a PRF.

> We can partition space, or divide it into sections. The size of those partitions can be described by real numbers

We don't know that. There are reasons to believe that both space and time are actually quantized. In fact, it is exactly the mathematical problems that arise from the continuum that leads one to predict this.

> Gödel's Incompleteness Theorems

Completely irrelevant for science. There are no oracles for the halting problem in this universe (AFAWCT). That's just a fact we have to live with.

> Chaotic Systems

See above.

> tell me a fish story

Two fish walk into a bar. The bartender says, "Shouldn't you guys be in school?"

> Are their rules and algorithms for human creativity?

Yes, as a matter of fact THERE are. (THERE are also rules for English grammar and spelling.) This is the reason chatgpt can come up with jokes like the one above.

> Modern mathematics doesn't work without actual infinities.

The parts of math that actually matter for science, that is, for producing models of reality, all work just fine without infinity.

Ron said...

Oh, almost forgot to mention: often the math only works if you just arbitrarily throw out infinities when you encounter them.

Publius said...

Converging on zero

@Ron:
> There are reasons to believe that both space and time are actually quantized.

There is <a href="https://www.scientificamerican.com/article/einsteins-greatest-theory-just-passed-its-most-rigorous-test-yet/>experimental evidence that it isn't.</a>

><i>Oh, almost forgot to mention: often the math only works if you just arbitrarily throw out infinities when you encounter them.</i>

I think you mean the <i>physics</i> only works if you arbitrarily throw out infinities.

Ron said...

> There is experimental evidence that it isn't.

The quantization of space and time probably happen on the Planck scale: 10^-35m and 10^-44s. Our technology is still many orders of magnitude away from being able to measure that.

> I think you mean the physics only works if you arbitrarily throw out infinities.

Often the math only works as a high fidelity model of reality if you throw out infinities when you encounter them. Is that better?

Ron said...

BTW, your HTML didn't work because you left out the close quote in your href parameter.

Publius said...

Komogorov Infinite

@Ron:
>The only case in which a "completed" infinity is *necessary* is if you want to describe an object with infinite Kolmogorov complexity. The existence of such objects is in considerable doubt. You cannot exhibit one, or even describe one.

Given a language L⊆{0,1}*
Let K(L) be the length of the shortest program that decides L, or K(L)=∞ if L is undecidable.
If a set S of languages is uncountable, then since there are only countably many decidable or recognizable languages, clearly there must exist a language L∈S such that K(L)=∞.

Ron said...

> clearly there must exist a language L∈S such that K(L)=∞.

Maybe I should have been more explicit: the existence of something in objective reality for which a theory with infinite Kolmogorov-complexity is necessary to explain it is in considerable doubt. What would the evidence for such a thing even look like?

(BTW, I'm actually in the middle of writing a whole post on this. You might want to wait for that before you continue this thread.)