* | | But without that would it be computational theory? *

* | Good God, why not? It was before that was perpetrated, it has been all along by mathematicians, and even computer scientists have realised it. *

Here's the lengthy background, which you probably already know, but I can't say things that make sense without referencing this background:

Modern theory of computation isn't about what machines can do.

It's about what people following a set of rules to manipulate symbols can do. When Turing used the words "computer", "computation", and "computable" in 1936 he was talking about people: "computer" was a job title.

The problem Turing was looking at was Hilbert's Entscheidungsproblem: "Given any statement p in a system S, is there an effective method for determining whether or not p is provable in S?"

People stating that problem sometimes used the words "definite method" or "mechanical method" or "algorithm" instead of "effective method". They were all informal ways of saying the same thing (and I've no idea what the equivalent in German was for Hilbert).

So Turing didn't just prove things about computation - that came second.

First, Turing gave a formal definition of what an "effective method" of computation or "algorithm" consists of.

Second, once he'd defined what he meant by that, he introduced as a thought experiment the idea of a Logical Computing Machine that could "follow an algorithm" or "do effective computation" as so defined - and then proved it could follow *any* algorithm (so defined), and then proved there were things that such a theoretical machine could not do.

It turned out that others (Church, Post, etc) were also trying to define what an "algorithm" or "effective computation" was, and their formal definitions were all equivalent to Turing's. And pretty much everyone took those definitions as being the last word on what "computing something by following an algorithm" really means.

**Computation theory, and work on limits and abilities of "computing machines", wasn't about giving limits on what machines can do, or limits on what mechanical systems can do, or limits on what physical systems are capable of[1].**

**It was about limits on what machines that follow algorithms to manipulate symbols "the way that people do" are capable of. By "the way that people do" we mean that: the input and output sets must be finite, and drawn from a finite alphabet set of symbols, and the number of operations done must be finite, and the set of rules being followed has to be finite too. Though they can be arbitrarily large.**

So:

So if you dislike the "deification of language recognition in computation" then it seems like you are taking issue with the truly fundamental feature of computation as Turing understood it, which is that computation is just symbol-manipulation, following a set of rules. It's all about language, in that it's all about symbols with meaning.

([1] And my comment up above about analog systems and real numbers is because the people who think uncomputability relates to what physical systems are capable of are making big assumptions about the nature of infinity and reality. They're not necessarily wrong, but such people owe us an explanation about why work on the limits of human capabilities should apply to what the universe is capable of, as it all seems a bit anthropocentric.)

]]>If you find yourself getting offended, note the subreddit.

]]>Er, no, not in the slightest. What I am referring to is the approach of Cook et al. (P, NP etc.) dominating the thinking in this area; my use of "language recognition" was in the technical sense. Turing, Church and Goedel were not so limited, nor were the numerical analysts who predated the computer scientists.

]]>Browsing somewhat through articles, I guess it was "Verfahren", which could be translated by "procedure" or "method".

Actually, German wiki defines Hilbert's Tenth Problem as

Man gebe ein Verfahren an, das für eine beliebige diophantische Gleichung entscheidet, ob sie lösbar ist.

In English wiki:

Find an algorithm to determine whether a given polynomial Diophantine equation with integer coefficients has an integer solution.

The original text by Hilbert would be:

Eine Diophantische Gleichung mit irgend welchen Unbekannten und mit ganzen rationalen Zahlencoefficienten sei vorgelegt: man soll ein Verfahren angeben, nach welchem sich mittelst einer endlichen Anzahl von Operationen entscheiden. läßt, ob die Gleichung in ganzen rationalen Zahlen lösbar ist.

Shorthand translation, "A Diophantine equation with any unknowns and rational integer coefficient shall be given: one should give a method according to which one could decide in a finite number of operations if the equation has a solution in rational integers."

Err, sorry, parsing this sentence is somewhat hard, hope I got it right.

]]>I hadn't realised that Hilbert set the "finite number of operations" limit himself in his question. That's an interesting bit of history.

Sadly, I haven't found the original German version by Hilbert for the latter, but given his, err, elaborate code (exhales deeply) I guess he used a.similar wording there.

Maybe I'm more lucky tomorrow, but browsibg and typing on my phone is no fun...

]]>https://en.wikipedia.org/wiki/Heikegani#Origin_of_the_carapace_pattern

I might add some musings about divine providence vs. selective cognition later on... ;)

]]>I'd ask if "mit ganzen rationalen Zahlencoefficienten" might not be "with completely rational interger coefficients".

No idea what difference that might make to the mathematical meaning.

]]>You are translating "ganz" as an adverb, though in that case you wouldn't use the declensed form "ganzen" (dative plural femininum, actually), but plain "ganz".

It's quite similar in English, for the adjective case, imagine "with complete rational integer coefficients".

Sorry, took me some time to work out, quite a lot of native language use is preconscious, which makes for you knowing the answer automatically, but working it out is hard. I'm not sure if I used the right term, but I just read an article by Oliver Sacks on blindsight-like phenomena in PCA where it's used in this sense.

Err, and mods, sorry, first off I borked the tags again, then I didn't care for the reply, this is the final version...

Err, sorry for the mess.

]]>]]>

https://en.wikipedia.org/wiki/Polynomial_Diophantine_equation

Though there are no citations on this article, and I have somewhat dropped out with the mathematicians in my circle of friends, so I can't verify it. As for my books, still in storage...

https://math.dartmouth.edu/opencalc2/cole/lecture19.pdf

Part of the reason that such things are interesting is that, if A is a ring, the ratio of two elements in A is a field. I am VERY rusty, so may have forgotten whether there are any other conditions - I could still work that out, but not now.