# Re: Qualia and mathematics

```
On 31 Jan 2012, at 19:33, meekerdb wrote:```
```
```
```On 1/31/2012 10:25 AM, Bruno Marchal wrote:
```
```
```
That's the reason mind exist, it accelerate the processing much more quickly. In fact, just by software change, the slower machine can always beat the faster machines, on almost inputs, except a finite number of them.
```
I can accept that intuitively, but can you point to a technical proof?
```
```
```
I basically got in mind Gödel's length of proof theorem of 1936, and Blum's speed-up theorem of 1967.
```
```
Adding an undecidable sentence, undecidable by a theory/machine T, to the theory/machine T, not only makes an infinity of undecidable sentences decidable, but it shorten infinitely many proofs.
```
```
In T + con(T), for example, infinities of (arithmetical) propositions are decidable (and undecidable in T), and infinity of proofs can be arbitrarily sped up.
```
Blum obtained in 1967 a related result in term of computational speed.

```
GÖDEL K., 1936, On the Length of Proofs, translated in Davies 1965, pp. 82-83.
```
```
BLUM, M., 1967, "A Machine-Independent Theory of the Complexity of Recursive Functions", Journal of the ACM 14: 322–336.
```
```
A characterization of the self-speedable machines has been made by Blum and Marquez in term of "subcreative sets", which generalizes the creative sets (provably equivalent, in some sense, to the universal sets /sets/machine/numbers). So you have a notion of subuniversal numbers, with the universal one as special cases, which correspond to the self-speedable machine/ numbers. All universal numbers are speedable, but not all speedable numbers are universal.
```
```
BLUM M. and MARQUES I., 1973, On Complexity properties of Recursively Enumerable
```Sets, Journal of Symbolic Logic, Vol 38, N° 4, pp. 579-593.

Another interesting paper is:

```
ROYER J.S., 1989, Two Recursion Theoretic Characterizations of Proof Speed-ups, The
```Journal of Symbolic Logic, 54, N° 2

```
Quite interesting and relevant for the Löbian number's bio-psycho- theology is:
```
```
GOOD I.J, 1971, Freewill and Speed of Computation. Brit. J. Phil. Sci. 22, 48-49.
```
Some good books:

```
ARBIB M., 1964, Brains, Machines and Mathematics, McGraw-Hill, 2ème éd. : 1987,
```Springer-Verlag, New-York.

CALUDE C. Theories of Computational complexity, North Holland, 1988.

SALOMAA A.,1985, Computation and Automata, Cambridge University Press,
Cambridge.

Ah, you can look here too:

http://en.wikipedia.org/wiki/Blum's_speedup_theorem

Bruno

http://iridia.ulb.ac.be/~marchal/

--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to