Recursive Ordinals and Creativity

[SSequence]

This question came up here recently (see later half of my post#9):
https://www.physicsforums.com/threads/how-can-we-construct-ordinals-after-large-veblen.934141/
Possibly post#4 may be of some relevance too.

I have already described my view more or less at length before (post#83 and post#169) in the following rather extensive (old) thread:
https://www.physicsforums.com/threads/penrose-chess-problem.911538
So there is no need of repeating it (apart from if there is a need to clear-up some point in detail) .

Since this question came up again (though somewhat indirectly) in this recent thread, I supposed it would be interesting to gather various opinions on this (the question is of mostly mathematical interest than practical one). And this is the purpose (so if you partially/totally disagree with me, feel free to express so).

@Deedlit Sorry for tagging so many times (didn't know there would be many threads all of a sudden), what is your opinion/understanding of this? Or of any other experts (on this specific topic) that read this?

Below I will just quote what number of (eminent) people have said regarding this (with a brief sentence or two in the beginning adding some context) ... well possibly to generate some interest :p. If some quotes are slightly (or more than slightly) out-of-context, then my apology. Just as one example, opinions can change sometimes.

(i) Kurt Godel
"Kurt Godel Collected Works Volume II -- Some remarks on the undecidability results (1972a)"
What I have read is that it isn't clear whether this note was meant for publication.

A philosophical error in Turing's work
Turing in his 1937, page250 (1965, page 136), gives an argument which is supposed to show that mental procedures cannot go beyond mechanical procedures. However, this argument is inconclusive. What Turing disregards completely is the fact that mind, in its use, is not static, but constantly developing, i.e., that we understand abstract terms more and more precisely as we go on using them, and that more and more abstract terms enter the sphere of our understanding. There may exist systematic methods of actualizing this development, which could form part of the procedure. Therefore, although at each stage the number and precision of the abstract terms at our disposal may be finite, both (and, therefore, also Turing's number of distinguishable states of mind) may converge toward infinity in the course of the application of the procedure. Note that something like this indeed seems to happen in the process of forming stronger and stronger axioms of infinity in set theory. This process, however, today is far from being sufficiently understood to form a well-defined procedure. It must be admitted that the construction of a well-defined procedure which could actually be carried out (and would yield a non-recursive number-theoretic function) would require a substantial advance in our understanding of the basic concepts of mathematics. Another example illustrating the situation is the process of systematically constructing, by their distinguished sequences $\alpha_n \rightarrow \alpha$, all recursive ordinals $\alpha$ of the second number-class.

(ii) Stephen Kleene
This is a comment on remarks in (i).

Reflections on Church's thesis

Let me now address an argument reported in [29], p. 222 (after Wang [28],
p. 325): "Godel . . . objects that Turing 'completely disregards' that:
(G) 'Mind, in its use, is not static, but constantly developing.'
. . . Gόdel granted that
(F) The human computer is capable of only finitely many internal (mental)
states.
holds 'at each stage of the mind's development', but says that
(G)' '. . . there is no reason why this number [of mental states] should not
converge to infinity in the course of its development.' "

If one chooses to believe (G)', I can see that it would imply that there need be no end to the possibilities for the human mind to invent stronger and stronger and stronger . . . formal systems that would, in the face of Godel's ever renewing incompleteness theorem, decide more and more and more . . . number theoretic
propositions ...
But I reject that (G)' could have any bearing on what number-theoretic functions are effectively calculable.

(iii) Solomon Feferman
Even though I have quoted the full sentence only for the sake of completion, it is the part that I have underlined that I believe is important here. Partly because he wasn't specifically talking about number-theoretic functions, but a more generic point. And given some of the most important work of the author seems to be quite related to the topic at hand, it seems fair enough to quote this.

https://math.stanford.edu/~feferman/papers/penrose.pdf
Penrose's Godelian Argument

I must say that even though I think Godel’s incompleteness theorems are among the most important of modern mathematical logic and raise fundamental questions about the nature of mathematical thought, and even though I am personally convinced of the extreme implausibility of a computational model of the mind, Penrose’s Godelian argument does nothing for me personally to bolster that point of view, and I suspect the same will be true in general of similarly inclined readers.

Edit:
I have removed the post-script and some quotes to keep the OP relatively short (and mainly just relevant to actual question).

 

[Stephen Tashi]

I don't detect a clear statement of a mathematical question in your lengthy post. I myself don't object to posts that are observations rather than questions. However, I don't find any introduction or even a topic sentence in what you wrote!

I'll respond to what you quoted from Godel:

A philosophical error in Turing's work
Turing in his 1937, page250 (1965, page 136), gives an argument which is supposed to show that mental procedures cannot go beyond mechanical procedures. However, this argument is inconclusive.

If we consider a human mind to be implemented by a human brain then we must consider the possibility that a human brain is an analog computation device, not a digital computation device. Are there mathematical results about what functions can be computed by analog computers?

Discussions of what the human brain can accomplish in mathematics usually visualize only the function of conscious thought and they visualize the actions accomplished as producing a mathematical proof - presumably in the form of a written mathematical paper. So instead of considering the total function of the brain they are considering a restricted set of operations - in particular, operations involving language, both formal and "natural" language.

 

[SSequence]

I'll respond to what you quoted from Godel:

Actually, I didn't want to quote the whole part (it is the last sentence that or two that are most important for the question in original post). I quoted the full part because otherwise it seems that some context would be missed (by the reader).
And even though all the quotes are at least partially related to the question at hand, it would just get too lengthy and off-topic to try to match their relevance with question. I will try to explain the question directly below instead (the relevance of quotes can be understood after that anyway).

If we consider a human mind to be implemented by a human brain then we must consider the possibility that a human brain is an analog computation device, not a digital computation device. Are there mathematical results about what functions can be computed by analog computers?

This is an interesting discussion (regardless of my specific views regarding it). But this is well-discussed (generally speaking online and otherwise) and the discussion would shift to Physical Church's Thesis (which was not my question).
Regarding your second sentence, it does seem there are some results regarding it (but I am completely unaware of any details at all regarding analog computation).

I don't detect a clear statement of a mathematical question in your lengthy post. I myself don't object to posts that are observations rather than questions. However, I don't find any introduction or even a topic sentence in what you wrote!

Yes it seems you are right! There is a lot of explanation but I didn't write clear enough problem statement. I will try to explain below what I was trying to say.

Consider what I wrote (towards end of post#9 in thread referred to at very beginning of OP):

****The only type of analogue that I can think of might be whether there are always mathematically fully reliable techniques that can determine a non-recursive set using increasingly more sophistication. Such discussions usually just seem to become one philosophical position against other (say for number theory specifically, platonism versus unreliability of LEM) ... or which tradition is more likely to be adopted by mathematicians. But the question just mentioned shifts the focus from "ability" to do something to "principle techniques". If we take the question back to "ability" (which is what is under discussion for question in main post) it seems to turn into a rather vague discussion. Same old discussion ... can you reliably(mathematically) determine halt of first 1000 programs, 10000 programs, 100000 programs etc.

You will notice that this is a common topic that related discussions seem to come up frequently in general or even specialised forums (despite the fact that apparently this is a rather general philosophical sort of question). Consider the following discussions (if you don't have enough time just briefly read the second link):

https://cs.nyu.edu/pipermail/fom/2017-November/020689.html
(click on "next message" towards the end of page to follow the response)

https://mathoverflow.net/questions/282869/the-enigmatic-complexity-of-number-theory

I originally removed these links from my OP, but it seems it might help a bit (with analogy) to explain what I was saying in OP. Instead of non-recursive set in quote above replace it with "number theoretic statements". When I used the term "principle techniques" really I just meant quite simply that one can settle all number-theoretic statements using reliable mathematical techniques. When I said "ability" in quote above what I simply meant was that can human being always rely on their ability (after a certain minimum understanding of certain ideas) to be able to eventually come-up with such techniques. So we have:
(a) existence of reliable mathematical techniques to solve all problems in a given domain
(b) having humanly enough ability (after certain minimum of understanding) to be able to come-up with those techniques whenever they exist (time, space and other basic idealisations assumed)

Consider the scenario with (a) and (b) both true. This is the most optimistic one. But our seeming inability to come up with reliable techniques to even determine small values of $BB$ (busy beaver) (basically halt of even small programs) seems somewhat disconcerting (and puts a real doubt in (b) at least ... regardless of what one believes in (a)). I don't think I am the only person who finds this rather strange.
In the second half of post#51 of the thread (https://www.physicsforums.com/threads/penrose-chess-problem) I suggested a thought experiment.

On the one hand, the picture(in large) developed by logicians/set theorists is rather exorbitant/sophisticated (and one has to say, extraordinary). On the other hand, there is a disconnect of being unable to settle issues that are microscopic within the big picture.

I think one can explain this better from an isolationist point of view. Suppose you were given an unbounded (but finite time) from some kind of mathematics grandmaster to learn as much of maths as you possibly could (limited domain is number-theory). But at some point you had to be in permanent isolation. The truths of number-theory being a non-recursive set (assume CT for idealisation), the GM(grandmaster) couldn't transfer them to you in finite time. So all the GM could do would teach you would be more and more and more mathematical techniques.
Maybe the GM could teach you enough techniques to solve till BB(1000), maybe BB(10000), maybe even more. But at the point that GM disconnects, could you trust yourself enough to be able to keep coming up with more techniques reliably enough. I can only speak for myself, but I can simply declare this impossible for myself (no amount of optimism and trying will suffice).

=====================

Now my main question is simply the same one but not for number-theoretic statements but for being able to come up with (recursive) well-order relations for recursive ordinals (in terms of "ability" ... in terms of "principle techniques" it seems rather close to impossible for me to try to see how they can't exist for every element in question). I have expressed my belief on this at length in the second thread linked in OP (as I already mentioned there) so I don't repeat it. The reasons are not that simple (and are based on certain intuitions and experience).

And while this is not strictly mathematical question, there are mathematical side questions/goals that can result from it (unfortunately some of them are sophisticated enough that I can't describe them fully precisely). For example, suppose that someone comes up with notations (for clearly very large elements) using rather difficult to intuit methods**** (methods that look just like coming up with unexplainable intuitions or proof of hard number-theoretic statements ... and this is simply not something I trust myself with ... in a fully absolute sense). A strictly mathematical goal would be to show that you can provably come up the notation for the same points (or beyond) using very traditional bottom-up methods (it doesn't matter how tedious the methods are or aren't) that have an understandable approach (in principle).

As an example, explaining "collapsing" (if one deems it non-conventional) using the traditional fixed-point approach (I call it definitely traditional because it is very explainable/understandable from programming pov) does seem to come under it.
Another important point would be removal $\omega_1$(and beyond) and replacing it with $\omega_{CK}$ (and related countable elements) ... even though intuitively the main point really is just the record of selections. But I suspect that doing it fully rigorously without being too tedious might be too hard.**** I admit my complete ignorance with regards to how many logicians or other people have devised.

 

[jacquesb]

I am fascinated by the topic of transfinite ordinals, which has the particularity of being the only mathematical domain that cannot be automated. In all other domains of mathematics, it is at least theoretically possible to deduce the theorems automatically from a formal system consisting of a finite set of axioms and rules. But Gödel proved that given any formal system of a theory sufficiently powerful to contain arithmetics, it is possible to build a proposition that expresses its own unprovability in this formal system. This proposition, which is very huge, has also a meaning as an ordinary arithmetic proposition, but is very useless in ordinary arithmetics. If the formal system is consistent, then this proposition is undecidable.

At first sight one could think that we just have to add this proposition to the system as an axiom, but this augmented system also have its own Gödelian proposition. If we start with an initial system $S_0$, this system has a Gödelian proposition $G(S_0)$, we add it as an axiom to obtain a system $S_1 = S_0 \cup \{G(S_0)\}$, which has a Gödelian proposition $G(S_1)$, then we add it to $S_1$ to obtain the system $S_2 = S_1 \cup \{G(S_1)\}$, and so on. Even if we consider the system $S_\omega = S_0 \cup S_1 \cup S_2 \cup ...$, it also has its Gödelian proposition $G(S_\omega)$ which we have to add to $S_\omega$ to obtain $S_\omega+1$, and so on.

But according to Solomon Feferman in "Penrose’s Gödelian argument" :
http://math.stanford.edu/~feferman/papers/penrose.pdf p.9 :
"one obtains completeness for all arithmetical sentences in a progression based on the transfinite iteration of the so-called global or uniform reflection principle"

The uniform reflection principle, which is something similar to adding the Gödelian proposition as an axiom, is described for example in John Harrison's paper "Metatheory and Reflection in Theorem Proving: A Survey and Critique"
http://www.cl.cam.ac.uk/~jrh13/papers/reflect.ps.gz p.18 :
$\vdash \forall n . Pr(\lceil \phi[n] \rceil) \Rightarrow \phi[n]$
Harrison also says p.19 :
"Feferman showed that a transfinite iteration based on it proves all true sentences of number theory".

So I think we can say that the construction of transfinite ordinals can store all the creative part of mathematics.

Another question is : does the theorem of Gödel apply to the human brain ? Perhaps, but in a more "fuzzy" way than to formal systems or computer programs. Beyond a certain level of complexity, it will become more and more difficult to manage this complexity. If we imagine more and more powerful systems for constructing big ordinals, beyond a certain point, we may fall in a loop without realizing we are in a loop because we don't perceive some regularity. I think perception of regularities is the essence of intelligence.

 

[SSequence]

I am fascinated by the topic of transfinite ordinals, which has the particularity of being the only mathematical domain that cannot be automated.

Yes the creativity part is very interesting.

... Gödel proved that given any formal system of a theory sufficiently powerful to contain arithmetics, it is possible to build a proposition that expresses its own unprovability in this formal system. This proposition, which is very huge, has also a meaning as an ordinary arithmetic proposition, but is very useless in ordinary arithmetics. If the formal system is consistent, then this proposition is undecidable.

At first sight one could think that we just have to add this proposition to the system as an axiom, but this augmented system also have its own Gödelian proposition. If we start with an initial system $S_0$, this system has a Gödelian proposition $G(S_0)$, we add it as an axiom to obtain a system $S_1 = S_0 \cup \{G(S_0)\}$, which has a Gödelian proposition $G(S_1)$, then we add it to $S_1$ to obtain the system $S_2 = S_1 \cup \{G(S_1)\}$, and so on. Even if we consider the system $S_\omega = S_0 \cup S_1 \cup S_2 \cup ...$, it also has its Gödelian proposition $G(S_\omega)$ which we have to add to $S_\omega$ to obtain $S_\omega+1$, and so on.

But according to Solomon Feferman in "Penrose’s Gödelian argument" :
http://math.stanford.edu/~feferman/papers/penrose.pdf p.9 :
"one obtains completeness for all arithmetical sentences in a progression based on the transfinite iteration of the so-called global or uniform reflection principle"

The uniform reflection principle, which is something similar to adding the Gödelian proposition as an axiom, is described for example in John Harrison's paper "Metatheory and Reflection in Theorem Proving: A Survey and Critique"
http://www.cl.cam.ac.uk/~jrh13/papers/reflect.ps.gz p.18 :
$\vdash \forall n . Pr(\lceil \phi[n] \rceil) \Rightarrow \phi[n]$
Harrison also says p.19 :
"Feferman showed that a transfinite iteration based on it proves all true sentences of number theory".

So I think we can say that the construction of transfinite ordinals can store all the creative part of mathematics.

This is topic that seems to come up (perhaps especially on online forums/discussions) with a rather high frequency. I do not know any of the specifics regarding this topic so I won't try to point out any specific issue, but things are nowhere as simple (as one can guess after skimming only few of the discussions that many of the associated results come with lot of caveats).
I suspect many of the positive results to involve some kind of pathology one way or the other (perhaps in a way not too different from way that numeric functions associated with sequences can be made uncomputable well-below ω_CK) ... but I can't say for sure (someone more knowledgeable can comment better).