Gemara

Question: A Beraisa obligates a Korban for idolatry only for an action, such as bowing. Bowing is not an act!

Answer (R. Yochanan): Bending one's posture is an act.

Horayos 4a (Mishnah): If the Sanhedrin forbade idolatry, but exempted one who bows...

They forbade spreading the hands and feet while bowing. They permitted bowing without doing this.

Megilah 22b - Question: When Rav came to Bavel, all fell on their faces, but Rav did not. Why didn't he?

Answer #1: There was a stone floor. One may not prostrate on it due to "v'Even Maskis Lo Sitnu b'Artzechem Lehishtachavos Aleha" - you may not bow on your stone floor, but you may bow on the floor of the Mikdash.

Rav used to spread his hands and feet when prostrating.

(Ula): The Torah forbids only spreading the hands and feet.

Answer #2: An important person is different. R. Elazar taught that a great person may fall on his face only if he is sure that he will be answered, like Yehoshua - "va'Yomer Hash-m El Yehoshua Kum Lech..."

(Beraisa): "Kidah" is (bowing) on one's face - "va'Tikad Bas Sheva Apayim Artzah". "Kri'ah" is on the knees - "mi'Kro'ah Al Birkav." "Hishtachava'ah" is spreading hands and feet - "...Lehishtachavos Lecha Artzah".

(R. Chiya bar Avin): I saw Abaye and Rava fall on their faces and lean on their sides.

Rishonim

Rif (Megilah 13a): A great person may fall on his face only if he is sure that he will be answered. Abaye and Rava fell and leaned on their sides.

Rosh (Megilah 3:4): The Rif holds that Abaye and Rava leaned on their sides due to R. Elazar's teaching. This is wrong. Mid'Rabanan prostrating on the face is forbidden even without spreading hands and feet. Rav Hai Gaon says that Abaye and Rava leaned so it would not look like they bow.

Rambam (Hilchos Avodah Zarah 6:6): The Torah forbids Even Maskis. One who prostrates on it, even to Hash-m, is lashed. It was the way of idolaters to put a stone in front (of the idol) and prostrate on it. Therefore, one may not do so to Hash-m. One is lashed only if he spreads his hands and feet on the stone and he is totally on it, which is what the Torah forbids.

Question (Turei Even Megilah Sof 22b) Here, we say that Hishtachava'ah is only with spread hands and feet. Krisus 3b says otherwise!

Minchas Chinuch (28): I would have said that one is liable for idolatry served through bowing even without spread hands and feet, and for other idolatry only with spread hands and feet (due to "Lo Sishtachaveh Lahem"). However, the Rambam and Sefer ha'Chinuch do not say so.

Kiryat Sefer (Azharah 37): One is liable for bowing to idolatry with or without spread hands and feet because this is how they bow to it.

R. Y. Perla (on Rav Sadya Gaon Lav 1, brought in Hagahos Minchas Chinuch): He holds that the Rambam obligates for Stam idolatry without spread hands and feet, for this is how they serve it, but not for an idolatry served only with spread hands and feet.

Rambam (7): This is why the custom of all Yisrael is to put mats on the floor of the Beis ha'Keneses if it is of stone, or straw to separate between the face and the stones. If he cannot find anything to separate, he goes elsewhere and prostrates, or bows and leans on his side lest his face be flush on the stone.

Rambam (8): Anyone who prostrates to Hash-m on Mefutzalos (split) stones without spreading hands and feet, he is lashed mid'Rabanan. One who is prostrates to idolatry with or without spreading his hands and feet, once he puts his face flush on the floor, he is (liable to be) stoned.

Rambam (Hilchos Tefilah 5:14): When doing Nefilas Apayim after Tefilah, some do Kidah and some prostrate. One may not prostrate on stone except for in the Beis ha'Mikdash, like we explained in Hilchos Avodah Zarah.

Rambam (9:5): After finishing Tefilah, the Shali'ach Tzibur falls on his face and leans a little to the side. The Tzibur does also.

Hagahos Ashri (Berachos 1:20, citing Or Zaru'a): With spread hands and feet, even if he tilts his head a little it is forbidden on a stone floor. However, one may do like our Shali'ach Tzibur, without spreading hands and feet. If there is no stone floor, it is permitted even with spreading hands and feet, as long as he tilts his face a little.

Question (Beis Yosef OC 131 DH v'Hagahos): Why must one tilt when there is no stone floor? Perhaps it is a decree lest one prostrate without tilting on a (stone) floor. Or, it is like the Rivash says in the name of Rav Shrirah Gaon, that Abaye and Rava were concerned for Even Maskis even on a non-stone floor, lest this floor was built on top of a stone floor. Or Zaru'a holds that it is a mere suspicion; even if there is stone underneath, it is not evident, so it suffices to tilt. However, this is not enough on a stone floor.

Rivash (412): Falling on the face is not a Chiyuv of Tefilah. It is a custom from the days of Chazal. The Gemara asked why Rav did not fall on his face. R. Eliezer's wife stopped him from falling on his face (Bava Metzia 59b). If it were obligatory, surely he would not let her stop him! Since it is a mere custom, in some places they do not say it on certain days, e.g. Chanukah and Purim and in a mourner's house at Minchah. Also the Ritz Ge'as says so. Since it is optional, we need not stand. One may sit, like for most Tefilos. Just Shemoneh Esre must be said standing. One need not sit for Nefilas Apayim. It is supplication, which is always standing. It is better to stand, like for Shemoneh Esre, Viduy and Berachos, but we do not burden people. We do not roll a Sefer Torah b'Tzibur, for this would burden people to stand at the time. One must be meticulous not to spread the hands and feet if there is a stone floor. The first version in Megilah forbids on a stone floor even without spreading hands and feet. Perhaps this is mid'Rabanan. This is why Abaye and Rava leaned for Nefilas Apayim, for even without spreading hands and feet it is forbidden on a stone floor. Ritz Ge'as says that they were concerned lest there is a stone floor underneath; the Rambam says that whenever there is a Hefsek, we are not concerned.

Poskim

Rema (OC 131:8): No one may fall on his face, stretching out his hands and feet, even if there is not an Even Maskis. If he leans a little to the side, it is permitted if there is an Even Maskis.

Beis Yosef (DH v'Rashi): Rashi and the Rambam hold like the Rif connotes. Shibolei ha'Leket, citing Rav Hai Gaon, says that R. Elazar forbids only directly on the face, but if he tilts a little, it is permitted. The Tur, Tosfos and Mordechai hold like the Rosh, that one version in the Gemara forbids mid'Rabanan without spreading hands and feet, unless he tilts.

Magen Avraham (20): It is forbidden only if his face is flush on the floor, but one may bow in Tefilah even if there is a (stone) floor (Kesef Mishneh, Rivash, Maharalbach. Ben Lev forbids on a marble floor. Keneses ha'Gedolah permits. However, Nefilas Apayim is forbidden even if his face is not flush on the floor, since he does not intend to prostrate, just to fall on his face. It seems that we do not forbid on a brick floor, for the Torah says "stone", and bricks are not stone - "the bricks were in place of stone." The Rambam connotes like this.

Kaf ha'Chayim (113): On a brick floor it is forbidden mid'Rabanan. This is a decree due to a stone floor, or lest there is a stone floor underneath. Mishbetzos Zahav (15) connotes like this (he says that one is lashed if it is on a brick floor).

Rema (ibid): One should do so on Yom Kipur when we fall on the face, if (or) they spread grass to separate from the floor. This is the custom.

Beis Yosef (DH v'Chasav OD): The Mordechai says that this is why on Yom Kipur we cover the floor of the Beis ha'Keneses with grass, for people fall on their faces when they say "veha'Kohanim veha'Am."

Magen Avraham (22): If they spread grass to separate from the floor, it suffices to tilt. Some texts say or they spread grass to separate (people) from the floor. According to this, one need not tilt. We forbid without tilting only over the ground, for perhaps it was built over a stone floor, and the ground is not a Hefsek. The ground of a house is like the house until the depths (Ohalos 15:5). However, grass is a Hefsek. The Rambam says so. This is correct, unlike the Rivash (412). The Shulchan Aruch does not require grass for Rosh Hashanah, for we do not fall on the face, just we bow and prostrate in Aleinu, but on Yom Kipur we fall on the face in the Avodah.

Kaf ha'Chayim (116): Toras Chatas says that there is no problem on a wooden floor. Even so, the custom is to put grass on the floor. Perhaps we are stringent not to distinguish between different kinds of floors.

Kaf ha'Chayim (117): If there is no grass on the floor, one uses the corner of his Talis to separate his face from the floor.

Mishnah Berurah (40): The Torah forbids prostrating with spread hands and feet on an Even Maskis; a stone floor is just the same. Chachamim forbid when one of these applies, i.e. Kidah (without spreading hands and feet) on a stone floor, or spreading hands and feet on a floor not of stone. They did not forbid Kidah on other floors. We also permit on a stone floor if it is not full Derech Kidah, e.g. he leans a little on his side, or not on a stone floor if it is not full Hishtachava'ah, e.g. he leans a little on his side.