• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Explaination wanted: Index Transformation

 
Ranch Hand
Posts: 581
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,
Sadly I found the following text rather obscure( in order to avoid misleading, I didn't translate the original text into English ):
...
Wir betrachten dazu ein Programm P, das als Eingabe Werte f�r zwei Eingabevariablen x und u ben�tigt; wir wollen nun einen bestimmten Wert f�r die Eingabevariable u festhalten und das Programm so modifizieren, da?es nur noch eine Eingabe f�r x erwartet.(till here I know what the text is saying.) Dazu mu?nur jeder Zugriff auf die zweite Eingabe u ersetzt werden durch einen Zugriff auf die Konstante u w�hrend der Zugriff auf die erste Eingabe x jetzt zum zugriff auf die einzige Eingabe x wird. ( ??? ) Um dies formal zu untersuchen, betrachten wir in einer Familie A von Algorithmen die vom Algorithmus Ai berechnete 2-Stellige Funktion F(2)i. Modifiziert man den Algorithmus f�r F(2)i so, da?er, anstatt eine zweite Eingabe zu erwarten, einen festen Wert einsetzt und die bisherige erste Eingabe als einzige Eingable verwendet, so bedeutet dies einen �bergang zu einem anderen Algorithmus mit einem anderen Index bei gleichzeitiger Ver�nderung der Stelligkeit der Funktion.
...
Wird eine 2-Stellige Funktion F(2) durch einen Algorithmus mit Index i berechnet, ist also F(2) = F(2)i, so mu?der Index j eines Algorithmus, der f�r die bislang zweite Eingabevariable u einen festen Wert vorsieht, durch eine in A berechenbare Funktion ermittelt werden k�nnen, die vom Index i des ersten Algorithmus und dem festen Wert f�r die bislang zweite Eingabe variable u abh�ngt.
In order to understand the text above, I read the part of recursion theorem and fix point theorem in the book Introduction to the Theory of Computation by Michael Sipser. Mr. Sipser presented the theorems via some construction of Turing machine and the presentation is not difficult to understand. Came back to my assigned text book, things became "unklar" again. Index transformation, index of what? My understanding is the index of algorithms. Every algorithms in the family A has a index, but how is the index generated? Anyway the conceptions of the family of algorithms A and the index is not clear to me. Anyone could explain a little bit? Thank you very much in advance.

Regards,
Ellen
 
Ellen Zhao
Ranch Hand
Posts: 581
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Peter I saw you speak in German in some other thread and you are a theoretical physicist, maybe the text above is just a piece of cake for you...are you around??
Regards,
Ellen
 
author
Posts: 3252
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Map, thanks for drawing my attention to this.
Ellen, "rather obscure" must count as the understatement of the month. This reads like an attempt to explain a simple concept in the most ponderous language possible (and German is already ponderous without trying!) in order to make things totally incomprehensible for foreigners :roll: My (loose) translation would be:

We consider therefore a program P with two parameters x and u. The task is now to modify P so that uses a constant value for u and only expects a single parameter x. In order to achieve this, every access of the second parameter u should be replaced by an access of the constant u, and every access of the first parameter x becomes an access to the only parameter x.

You're not missing anything, it is that obvious. This reminds me of the Operations Research lecture where the lecturer, discussing a factory utilisation problem, spent half an hour proving that the function u(t), taking the value 0 or 1 depending on whether the factory was in operation or not, was integrable. This was for an audience of third year maths students!!! Anyway...

To explore this formally, consider in a family A of algorithms the 2-parameter function F(2)_i calculated by A_i. If one modifies the algorithm for F(2)_i in such a way that, instead of taking two parameters, it takes a single parameter and uses a fixed value for the second parameter, one has mapped the algorithm A_i to another algorithm A_j with a different index and different number of parameters taken by the function.

In other words: if you consider a collection A of algorithms A_i representing n-parameter functions F(n)_i, take the subset of two-parameter functions F(2)_i and modify them to take only one parameter, you end up with different functions F(1)_j and hence different algorithms A_j from A. Well, to be honest, without knowing more about both A and the constant values that can be chosen for the second parameter, it is not at all clear to me that your modified functions would map to algorithms in A at all, but never mind.

If the 2-parameter function F(2) is calculated by an algorithm A_i, then its 1-parameter modified counterpart F(1) should correspond to some different algorithm A_j in A with a different index j. The index j depends on i and the constant value used for the second parameter u.

That's it. All the text seems to say is that your "turn a 2-parameter function into a 1-parameter function" operation defines an mapping inside the family A of "all" algorithms, and that this mapping depends on the constant value you pick for the second parameter.
Does that help?
- Peter
[ May 19, 2003: Message edited by: Peter den Haan ]
 
Ranch Hand
Posts: 925
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I can just imagine the author trying to pick someone up in a bar. Kind of like that scene in 'a beautiful mind' but taking half an hour
 
Ellen Zhao
Ranch Hand
Posts: 581
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Peter,
I have studied your translation closely and it makes great sense to me. I highly appreciate you.
There are two kinds of people I always adore: mathematicians of number theory and poets who written in German. This week our lecture go into number theory, and we study how to encode every programme. Lecturing of Goedel Numerierung, the professor himself got lost for a while, what I don't understand is not several lines but several pages, and it is said that those several mysterious pages are philosophically very meaningful....well, all my wish is that the professor please be aware we are not Kurt Goedel when he is conceiving the exam. And I agree with you, the German language is clumsy. Those who write beautiful poetries in German really possess remarkable talent.
Best Regards,
Ellen
 
Sheriff
Posts: 6450
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Ellen Zhao:
Those who write beautiful poetries in German really possess remarkable talent.


I bet it must be hard as hell to write a decent haiku in German. I suppose each line could consist of a single word.
 
Ellen Zhao
Ranch Hand
Posts: 581
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Map,
Thank you very much for having dragged Peter to my question.
Finally there's some fun beside the extremely dry computability study. This semester we are doing some practical software project, in my group there are 3 students who have been German citizens for more than 10 years ( they speak perfect German ) but originally from Russia. These three students are truely creative, delligent and productive, I am learning from them a great deal. Kudos Russians!!!

I can say "good morning" in Russian now, why that long??
Best Regards,
Ellen
[ May 20, 2003: Message edited by: Ellen Zhao ]
 
Leverager of our synergies
Posts: 10065
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
EZ: There are two kinds of people I always adore: mathematicians of number theory and poets who written in German.
"Everyone in the sciences secretly believes that mathematicians are smarter than they are."
Paul Graham
Hackers and Painters
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Now that I see the translated version (thanks PdH), I will suggest that Gödel, Escher, Bach will probably give a much more interesting and readable (IMO) treatment of this material. Despite what you might guess from the names in the title (and of the author), it's originally written in English - though you can probably find a German, Chinese, or Russian translation if you prefer.
[EZ]: Every algorithms in the family A has a index, but how is the index generated?
I assume that if this is related to Gödel's theorem as applied to computer science, A is intended to represent something like "all algorithms which could possibly be implemented in [whatever programming language you want to discuss]". So i represents an index of all possible programs, or perhaps all programs that fit certain criteria. Actually calculating these index values is something you would never want to do in real life (unless you're immortal and bored); you only want to convince yourself that it's theoretically possible to do it. One possible algorithm:

Here isAcceptable() can filter to whatever criteria we may choose to specify. For example, allow only functions named "f" which return an int and accept a single int parameter named "x". (Hmmmm... for Gödel discussions better use BigInteger rather than int, but you get the idea...). And as for MAX_LENGTH, you'll eventually want to make this infinite, which requires extra handwaving of course...
[PdH]: Well, to be honest, without knowing more about both A and the constant values that can be chosen for the second parameter, it is not at all clear to me that your modified functions would map to algorithms in A at all, but never mind.
True - but I'm guessing they set it up something like the above, so that A basically represents any possible algorithm you could program. Which leads to questions like, are there any algorithms which could not possibly be programmed? Which leads to all sorts of weird stuff which makes you want to recheck a lot of the assumptions that were made along the way, which is probably why they're spending the extra verbiage on "obvious" stuff.
[ May 20, 2003: Message edited by: Jim Yingst ]
 
SJ Adnams
Ranch Hand
Posts: 925
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

will suggest that G�del, Escher, Bach will

No, No, No, I forbid you.

Read Wittgenstein http://www.amazon.co.uk/exec/obidos/ASIN/0415254086/
Then go to a library, pick up GEB after the first dozen pages you can come back & thank me. If that doesn't work, take up astronomy.
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Boy, are you ever in trouble now. Speaking ill of GEB!
You may be able to appease Thomas by changing your link to
http://www.amazon.com/exec/obidos/ASIN/0415254086/jranch-20/
However, I suspect that nothing will be able to save you from the wrath of Mapraputa. So long Simon; it was good knowing you, however briefly.
 
Mapraputa Is
Leverager of our synergies
Posts: 10065
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
No, No, No, I forbid you.
Read Wittgenstein http://www.amazon.co.uk/exec/obidos/ASIN/0415254086/

How are these two connected?
I can say "good morning" in Russian now, why that long??
Mmm.. You mean that Russian expression for "good morning" is too long? Five syllables instead of three, but more important, I just realized that literate translation for Russian "good morning" would be "kind morning", interesting substitution of "kind" instead of "good".
 
Mapraputa Is
Leverager of our synergies
Posts: 10065
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
However, I suspect that nothing will be able to save you from the wrath of Mapraputa.
When I was typing my response, this Jim Yingst guy wedged himself again! Well, I guess, you, Simon, is doomed now!
 
Mapraputa Is
Leverager of our synergies
Posts: 10065
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You mean that you do not like GEB???
 
SJ Adnams
Ranch Hand
Posts: 925
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
No, I do not like GEB, I do not agree with GEB, I am stubborn and will not be moved.

If that doesn't work, take up astronomy.


go figure.
 
Ellen Zhao
Ranch Hand
Posts: 581
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Jim,
Thank you very much for your homework. Your java code is much more accessible than the psuedo code in our text book. I'm going to print off this page.

Simon,
Then go to a library, pick up GEB after the first dozen pages you can come back & thank me.
Sure sir, I'm going to do it in my next life. But I thank you now anyway.

If that doesn't work, take up astronomy.
Astronomy is something definitely too spiritual to me, staring at the stars I can hardly think of math. Maybe next life again??
Best regards,
Ellen
 
Ellen Zhao
Ranch Hand
Posts: 581
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Chinese: zao3 an1 2 syllables
English: good morning 3 syllables
German: guten Morgen 4 syllables
Russian: dobroje utro 5 syllables
conclusion: Chinese is the most economic language
[ May 24, 2003: Message edited by: Ellen Zhao ]
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just ignore Simon about GEB; he is a godless heretic.
Well OK, actually it is Map and I who are godless heretics. But Tom is apparently neither, and he agrees with us about GEB.
Chinese is the most economic language
That's 'cause you've got all those extra vowel sounds we westerners can't distinguish between. Fewer syllables; more phonemes. So you're just cheating, really.
"Good morning": well, most of the time I only need two syllables: "Mornin'." Sometimes more though: "What are you looking at? And where's the coffee (grumble)?" Depending on mood, and whether I've found the coffee yet, of course. Fortunately most people who know me wait until after I'm caffeinated before they approach.
[ May 24, 2003: Message edited by: Jim Yingst ]
 
Mapraputa Is
Leverager of our synergies
Posts: 10065
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Interesting question. That Russian "good morning" is longer (in syllables) than English, can be an accident. For example, there is a joke: "What is the shortest anecdote? - "Rodil". This 5-leter Russian word means "gave a birth" and it has masculine gender. But statistically, Russian words are longer than English. I do not remember exact coefficient for texts, something around 1.2 Why is it so? One hypothesis, the Russian language, as Michael Matola pointed out, is a synthetic language, as opposed to analytical English. It means that words have different forms, depending on gender, number etc. Accidentally in "dobroe", there is one "meaningful" syllable of 4 letters, just like in "good", the last two letters serve to indicate neutral gender, singular number.
What I found most interesting, though, that "dobroe utro", literally means "kind morning" -- an interesting substitution of "kind" for "good". It is said that language express nation's "na�ve model of world". Recently I was reading comments of a university instructor who teaches Russian to American students. She noticed something, I never paid attention to. In Russian "I have X" often (in spoken language almost always) is said literally as "near me is X" (or "there is X near me", if it is more clear .
Perhaps this can explain why property rights have never been particularly respected in Russia -- the very language exposes its transitory nature. Yesterday this thing was near you, today it's near me, life is like that...
 
Ellen Zhao
Ranch Hand
Posts: 581
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Mapraputa Is:

Yesterday this thing was near you, today it's near me, life is like that...


philosophically ja richtig!
 
reply
    Bookmark Topic Watch Topic
  • New Topic