Is it possible for a math to be non-algorithmic? Can you give example?
Most math is non-algorithmic.
In general, math makes declaratory statements.
In contrast, algorithms make imperative statements.
N = N + 1;
That is an imperative statement. When executed, it will cause a variable "N" to be incremented.
Taken as a Math statement, it is a declaration which is false.
Since you asked for a specific example of a Math statement that is non algorithmic, her is one:
$$ x^2 + y^2 = r^2 $$
When Penrose spoke about non-algorithmic thing.. he didn't mean it's non-math then? This is about his book "The Emperor New Mind".
I did read "The Emporer's New Mind", but not recently enough to remember clearly.
As I recall, "algorithmic" in that context referred to any process that was equivalent to how conventional (non-quantum) computers process information. He was arguing against the generation of consciousness by "algorithmic" information processing by arguing that all such processing was the equivalent of reading the algorithm from a printed document and working it out manually. Since that printed document exercise does not elicit its own "consciousness", neither would any other mechanical or electronic equivalent.
You meant Penrose was saying quantum computers were non-algorithmic yet still describable by math? I'm trying to search his book now where he strings the word "math" and "non-algorithmic" together..
I searched all instances of the words "Non-algorithmic" in Penrose book and saw the following: "In Chapter 10, I shall try to present arguments to show that the action of our conscious minds is indeed non-algorithmic (i.e. non-computable)".
I first read the book about 10 years ago and my first impression was non-computable means can't be solved by math. So I thought non-algorithmic means it can't be solved by math. But then are there maths that are non-computable? Any examples? Many thanks!
Quantum computers operate on information in a fundamentally different way that conventional computers. And therefore, the potential for creating consciousness through a QM process is not affected by Penrose's analogy to reading a printed description of the algorithm.
The only reason I am not answering your question with a simple "yes" is that there are QM algorithms (ex, Shor's, Grover's, annealing). So if Penrose said that quantum computers are non-algorithmic, then he was using the term "non-algorithmic" is a very context-dependent sense.
And yes, what quantum computers can be described by Math.
There are non-computable functions. This means that for the function there is no algorithm, which can compute the function for any input. The standard example is Turings halting problem. There is however widespread belief that the Church-Turing thesis is valid and that computers and human brains are insofar equally powerful that any non-computable function for one is also non-computable for the other, and that computers can solve any mental task that a human can solve. It is known that Quantum computers are also in that sense equivalent to conventional computers, even though they are likely faster for certain tasks.
I think of an algorithm as being a sequence of steps to solve a problem. (@.Scott correctly points out that Shor's Algorithm is called an "algorithm" and I don't know if that use of the term is because it is done is a two step sequence (traditional computer step, then quantum computer step) or not.)
Usually mathematics is a set of equations and facts that are all simultaneously true, not done in a sequence. The mathematical version of the computer N = N+1 would be Nnew = Nold+1. In my interpretation of the term "algorithmic", that would make most math "non-algorithmic".
I think the question in OP can be interpreted in a few ways.
At any rate, whether math "itself" (as some sort of entirely objective entity) is algorithmic or not relates to Godel's rather well-known statement whose paraphrasing is:
"the mind cannot be mechanized” or “there are absolutely undecidable statements.”
Note that the first statement would seem to assert/relate mind to mathematics closely. Regardless even if one believes the first statement, it would still leave some important points unanswered.
Assuming the first statement to be true, it seems that Godel is really talking about "potentiality". But the concrete (mathematical) assumption/formalisation under which the potentiality can be achieved is left as unanswered.
Also, given the disjunction, there seems to be a certain implicit assumption in the second statement (hopefully just mentioning it doesn't add more confusion). To talk about it more meaningfully, suppose we restrict our "space" to just number-theoretic statements (to avoid trouble with more difficult issues). It seems to me that the second statement implicitly assumes that the boundary between "knowable" and "unknowable" should be algorithmic in some sense?
But then again, I am not sure why this can reasonably be taken as more plausible than say the boundary being non-algorithmic? Perhaps I am missing something....
Also I personally feel unease with such a disjunction unless one is very clear about exactly what "statements" are included in the second part of disjunction (for example, a restriction to number-theoretic statements as in "Edit" above is perfectly fine). But nevertheless, this might digress a bit so I leave it here.
Regardless, since you mentioned Roger Penrose:
I have never really thought about Roger Penrose's argument much (nor I have enough knowledge to understand the link), so I don't have any opinion or understanding of it. Regardless, it seems important to settle/formalise some abstractions beforehand before discussing it.
Nevertheless, it is interesting to see though that it is considered subtle.
Anyway, regardless of this discussion, math seems to reason "about" non-computable objects all the time. The real numbers (treated in standard way) are not only non-computable but seem to be quite radically so.
It seems a bit of nitpicking admittedly, and that is not my intention. More or less what you have written is correct.
Just adding a little distinction, Church Thesis strictly applies to functions. If a given "mental task" can be "considered" suitably abstracted as a function then (assuming CT) what you have written is quite correct indeed.
We posted the replies at the same time so maybe you didn't see the message above it. I was saying I searched all instances of the words "Non-algorithmic" in Penrose book and saw the following: "In Chapter 10, I shall try to present arguments to show that the action of our conscious minds is indeed non-algorithmic (i.e. non-computable)".
I first read the book about 10 years ago and my first impression was non-computable means can't be solved by math. So I thought non-algorithmic means it can't be solved by math. But then in your understanding, can you give some examples of maths that are non-computable in the context of Penrose's? Thanks a lot Scott!
"non-computable" may just mean there is a random component. If so, that can be addressed mathematically.
Non-computable denotes that the algorithm cannot complete, cannot complete in a finite amount of time, or cannot complete with all available resources in the universe. It refers to a task set to run on a Turing machine or other classical computer.
Consider the Halting problem. It is uncomputable in the sense that it has been proven that it can not be solved in the general case on a computer.
However, as a Math problem, it has been solved - It 1930, Alan Turing proved Mathematically that it was an uncomputable problem for the general case. That proof was the Mathematical solution.
There are Math problems that remain unsolved - here's the wiki site with a list of them:
Separate names with a comma.