ALVIN B. RUBIN, Circuit Judge:
May a resident alien be denied naturalization because he was a homosexual at the time he was admitted to the United States? The district court, 538 F.Supp. 589, answered this question in the affirmative. We affirm its judgment that the petitioner is ineligible for naturalization because, being excludable on the ground of his homosexuality when he arrived here, he was not lawfully admitted to the United States.
I.
Richard John Longstaff, now forty-three, is a native and citizen of the United Kingdom of Great Britain and Northern Ireland. On November 14, 1965, he was admitted to the United States as a permanent resident. Before he arrived in the United States, Longstaff filled out a form entitled “Application for Immigrant Visa and Alien Registration.” To the question:
3(b) Are you now or have you ever been afflicted with psychopathic personality, epilepsy, mental defect, fits, fainting spells, convulsions or a nervous breakdown?
Longstaff answered, “No.” The question was based on a provision of the Immigration & Nationality Act (the Act), 8 U.S.C. § 1182(a) (1976 & Supp. V 1981), excluding persons thus “afflicted.” Congress intended the term “psychopathic personality” to designate homosexuals as well as persons having psychopathic disorders, as that term is generally understood. However, no evidence suggests that Longstaff knew or had reason to know that “psychopathic personality” was a term of art that included homosexuals and consequently excluded them from admission to the United States.1
[1441]*1441Longstaff eventually settled in Texas, where he established himself in business. He owns two shops, operated under the trade name Union Jack, selling clothing and offering hairdressing services to both men and women. He has never been charged with any offense other than traffic violations. Reputable witnesses testified that they believe him to be a person of good moral character.
In his fifteenth year of residence, Long-staff sought naturalization as a citizen of the United States. He was recommended by the naturalization examiner, but the district court denied naturalization because it found that Longstaff had violated the Texas Penal Code by engaging in homosexual activity, had exhibited a lack of candor in answering questions about his sexual activities, and had failed to carry his burden of establishing good moral character as required by 8 U.S.C. § 1427(a)(3) (1976). We affirmed on appeal solely on the ground that Longstaff had failed to discharge his burden of proof. In re Longstaff, 631 F.2d 731 (5th Cir.1980) (per curiam). We remanded, however, to afford Longstaff an opportunity to adduce additional evidence of his good moral character. In re Long-staff, 634 F.2d 629 (5th Cir.1980) (on rehearing)-.
Thereafter, pursuant to the district court’s pretrial order, an examiner for the Immigration and Naturalization Service (the INS) interrogated Longstaff. The examiner concluded that Longstaff had met his burden of establishing good moral character; nevertheless, he recommended denial of the petition because Longstaff had engaged in homosexual activity before entering the United States in 1965. He concluded that Longstaff (1) had been excludable under the Act; (2) had not been “lawfully admitted,” as the Act requires for naturalization, and (3) could not be naturalized. After a trial de novo, the district court again denied Longstaff’s petition for naturalization on this basis.2
II.
No person may be naturalized unless he has been lawfully admitted to the United States for permanent residence in accordance with all applicable provisions of the Act.3 The applicant has the burden of proving that he entered the United States lawfully.4 Longstaff argues that, because he was granted a visa and admitted in procedurally regular fashion, he is eligible for naturalization even if, for any reason, he should have been excluded.
That narrow reading of the term “lawfully admitted” distorts its meaning. Admission is not lawful if it is regular only in form. The term “lawfully” denotes compliance with substantive legal requirements, not mere procedural regularity, as the definition provided by Congress plainly establishes: “the term ‘lawfully admitted for permanent residence’ means the status of having been lawfully accorded the privilege of residing permanently in the United States as an immigrant in accordance with the immigration laws, such status not having changed.5 Section 1429’s added requirement “in accordance with all applicable provisions of [the Act]” is not merely redundant, but emphatic and embracive.
The provisions concerning deportation demonstrate that what is essential is lawful status, not regular procedure. An alien is subject to deportation if “at the time of entry [he] was within one or more of the classes of aliens excludable by the law ex[1442]*1442isting at the time of such entry.”6 This clause overlaps the provision for deportation of any person who “is in the United States in violation of [the Act] or in violation of any other law of the United States.”7 By providing for the deportation of excludable aliens, the Act implies that such persons, though present in the United States, were not “lawfully admitted.”
The Act lists thirty-three classes of persons who'are “ineligible to receive visas and shall be excluded from admission into the United States.”8 It would be paradoxical if a person who was ineligible to receive a visa and should have been excluded from admission became lawfully admitted simply because, by error, he was not excluded. We decline to read a congressional enactment so absurdly. We turn, therefore, to Long-staff’s argument that he was not excludable at entry.
III.
Among the classes of aliens ineligible to receive visas and excluded from lawful admission to the United States by the Act are “aliens afflicted with psychopathic personality.”9 Before the statute in terms referred to “sexual deviation,” as it now does, the Supreme Court held in Boutilier v. Immigration & Naturalization Service, 387 U.S. 118, 120, 87 S.Ct. 1563, 1565 , 18 L.Ed.2d 661, 664 (1967): “The legislative history of the Act indicates beyond a shadow of a doubt that the Congress intended the phrase ‘psychopathic personality’ to include homosexuals ....”10 Because Congress has plenary power over the admission of aliens, the Act was constitutional even if the term “psychopathic personality” did not give fair warning to the ordinary person that the phrase included homosexuals.11 Furthermore, the Court held that the statute was constitutional because it applied to characteristics the alien possessed “at the time of his entry” and was not a sanction proscribing later conduct.12
Congress has unbounded power to exclude aliens from admission to the United States.13 Our national immigration policy was for many years based on national origin quotas that reflected racial and ethnic prejudice. Congress can bar aliens from entering the United States for discriminatory and arbitrary reasons, even those that might be condemned as a denial of equal protection or due process if used for purposes other than immigration policy to draw distinctions among people physically present within the borders of the United States.14 The constraints of rationality im[1443]*1443posed by tbe constitutional requirement of substantive due process and of nondiscrimination exacted by the equal protection component of the due process clause15 do not limit the federal government’s power to regulate either immigration or naturalization.16 Thus, the Constitution does not require our national immigration policy to be consistent with the prohibition of discrimination by federal agencies17 and by state governments and private persons.18
Longstaff does not question any of these elementary principles. He contends that the Act does not exclude homosexuals on the basis that they are determined judicially to have such a sexual preference or even on the basis that they state that they have this preference, but that it is designed to exclude only those persons declared by a Public Health Service (PHS) medical officer to be “afflicted” with “psychopathic personality” or “sexual deviation.” He premises his argument on the Act’s separation of medical from other reasons for exclusion. Because the exclusion of those afflicted with psychopathic personality is contained in a clause enumerating medical bases for exclusion,19 Longstaff argues, excludibility for homosexuality must be determined in the same fashion and by the same procedures as excludability for affliction with a mental defect or a dangerous contagious disease. Because these conditions are “subject to medical determination,” he contends that only a medical officer has the power to determine whether any of them exists.
The Public Health Service, in a report to the House of Representatives on the medical aspects of the House bill that later became the Immigration and Nationality Act of 1952, suggested grouping together excludable “conditions related to the field of mental disorders and subject to medical determination.”20 For a number of years [1444]*1444thereafter, Public Health Service medical officers issued certificates declaring that aliens were excludable for homosexuality as well as for the other conditions listed in the part of the statute dealing with medical conditions.
The Surgeon General announced in 1979 that the PHS would no longer consider homosexuality a mental disease or defect because current medical standards classify homosexuality as simply a form of sexual behavior, not by itself a psychotic disorder, and because the determination that a person engages in homosexual activities is not made through a medical, diagnostic procedure.21 Therefore, he advised INS officers to stop referring aliens to the PHS for mental examinations solely to determine whether they were homosexuals.22
The Act provides that arriving aliens may be detained at the border while immigration and medical officers examine them for “physical and mental defects or disabilities” that warrant exclusion.23 It also requires that the physical and mental examination of arriving aliens be conducted by medical officers of the United States Public Health Service or if PHS officers are unavailable, by civil surgeons employed on terms prescribed by the Attorney General.24 These physicians “shall conduct all medical examinations and shall certify, for the information of the immigration officers and the special inquiry officers, any physical and mental defect or disease observed by such medical officers in any such alien.”25
Longstaff urges the court to infer from the use of the word “shall” that an applicant may not be excluded for medical reasons unless the basis for exclusion is determined by a physician. He supports this argument by reference both to the past administrative practice and to the Act’s declaration that a medical certificate is conclusive evidence of medical excludability.26 Accordingly, he argues, a medical certificate is the sole type of evidence an immigration judge may consider.27 He adds that the 1917 Act, which the 1952 Act replaced, was also construed to give conclusive effect to a medical certificate of excludability.28 [1445]*1445To evaluate this argument, we examine the history and structure of the Act and the procedure that must be followed by an alien who seeks to immigrate to the United States.
IV.
Homosexuals were first statutorily excluded from entry by the Immigration Act of 1917, which prohibited the admission of “persons of constitutional psychopathic inferiority” certified by a physician to be “mentally ... defective.”29 The Immigration and Nationality Act of 1952, which repealed the 1917 Act, excluded homosexuals from entry as persons with “psychopathic personality.”30 In 1965, shortly before Longstaff was admitted, the Act was amended to delete the word “epilepsy,” which had previously been included in clause (4), and to substitute “sexual deviation.” See supra note 8. That clause, as amended, excluded “[a]liens afflicted with psychopathic personality, sexual deviation, or a mental defect”31 at the time of Long-staff’s admission, as it now still does.
When a visa was issued to Longstaff, the procedure employed, which appears not to have changed substantially, was as follows: an alien seeking admission for permanent residence in the United States was required to apply to a consular official outside of the United States for a visa. Issuing visas was the responsibility of the State Department, while examining aliens for admissibility to the United States was the duty of the INS, an arm of the Justice Department. Before the consular officer could issue the visa, the alien was required to complete an application form and to submit to physical and mental examination by a PHS officer or a designated physician.32
The consular officer was forbidden to issue a visa if it appeared from statements in the alien’s application or from the papers submitted with it that the alien was ineligible to receive a visa, hence excludable, or if the consular officer knew or had reason to believe that this was the case.33 Thus, in the usual course of events, an alien who was excludable never received a visa. Presumably, if an applicant for a visa answered “yes” to the psychopathic personality question, he would be denied a visa. If he answered “no” but were found by the PHS officer conducting the pre-visa physical and mental examination to have such a personality, he would also be denied a visa.
Because the immigrant visa was valid for only four months,34 the PHS officer at the port of entry usually did not make another physical or mental examination. Unless there was some reason to suspect that the alien had suffered a change in health or that the prior examination was erroneous, the domestic PHS officer merely reviewed the medical report attached to the visa.35 An immigration officer inspected the visa and determined whether the alien was to be [1446]*1446admitted.36 Unless his decision was challenged by another immigration officer, the alien was admitted. The immigration officer might require the alien’s sworn statements and other evidence regarding “any matter which is material and relevant to the enforcement of [the Act],” including the production of books, papers, and documents; and the testimony, under subpoena, of witnesses.37 Any alien who “may not appear to the examining immigration officer at the point of arrival to be clearly and beyond a doubt entitled to land shall be detained for further inquiry to be conducted by [an immigration judge].”38 That judge made the decision concerning admission.39
Former INS immigration officers testified that, because of the procedure for issuing visas, they made no inquiry about the sexual preference of aliens arriving with a visa.40 One former immigration officer testified that they spent an average of only 38 seconds examining each alien and his papers and that ordinarily the PHS officers merely inspected the pre-visa medical certificate to be certain that it was in order.
There is no evidence in the record regarding the procedure followed when an alien who arrived in the United States with a visa affirmatively disclosed at that time that he was a homosexual. Presumably, such a person would have been referred to a PHS medical officer for a determination of his admissibility.
As Longstaff asserts, the statute provides that the medical officer’s certification of “any mental disease, defect, or disability which would bring such alien within any of the classes excluded from admission” is conclusive evidence of excludability.41 This does not necessarily mean, however, that the absence of certification is conclusive evidence of admissibility. The Act also requires that medical officers be provided with suitable facilities for the detention and examination of all arriving aliens who are suspected of being excludable on the basis of physical or mental condition.42 But this does not necessarily mean that such an examination is ordinarily conducted or that aliens may be excluded for medical reasons only after such an examination.
Apparently the administrative practice has been to exclude for homosexuality only those persons for whom a certificate was issued.43 Longstaff’s position that no person may be excluded absent such a certificate is also supported by Lesbian/Gay Freedom Day Committee, Inc. v. Immigration & Naturalization Service, 541 F.Supp. 569, [1447]*1447577-80 (N.D.Cal.1982), affirmed, 714 F.2d 1470 (9th Cir.1983).
Evaluating the extent to which this customary procedure establishes a binding precedent, we look to the statute. The Boutilier Court inferred from the statute clear congressional intent to exclude persons who are homosexuals at the time they seek entry into the United States. Even if we were not bound by Boutilier, Congress declared its intention unmistakeably by amending the statute to bar “sexual deviates.” We need not search committee reports or read legislative debates to learn the congressional mandate. The one question that remains is whether Congress ordered the exclusion of everyone it considered sexual deviates or only persons so classified at any given time by the PHS medical officer or some other physician.
If only certification of homosexuality by a medical officer could warrant exclusion of homosexuals, then the Surgeon General would have effectively checkmated Congressional policy. Confronted with the problem raised by the Surgeon General’s abdication of the power he had sought from Congress, the INS initially allowed all suspected homosexuals to enter the United States under parole status while it sought counsel from the Justice Department’s Office of Legal Counsel on whether it was still obligated to exclude homosexuals.44 The Office of Legal Counsel informed the INS that it was still required to do so45 The opinion of the Ninth Circuit in Lesbian/Gay Freedom Day Committee, supra, reads the Act as requiring it to do so only when homosexuality is certified by a medical officer. Because the statute requires medical examination to be conducted by medical officers of the Public Health Service, the Surgeon General’s refusal to allow these officers to make such certification precludes the exclusion of anyone for homosexuality. We cannot, however, conclude that a medical certificate was indispensable to bar a professed homosexual from entry to the United States in 1965 or that obtaining such a certificate now is a prerequisite to denying naturalization.
Although the term “homosexual” is not a scientific designation, and studies indicate that many males have homosexual experiences, there can be no doubt that Longstaff both knew what the term meant and was not uncertain about his sexual preferences. He stated that he had been a homosexual “as far back as [he could] remember in [his] life.” He testified that he had engaged in “homosexual activities” before his entry into the United States. He defined a homosexual experience as “going to bed with a person of the same sex, ... in other words, sexual relations.” He admitted having “deviate sexual intercourse” as defined in the Texas statute “at least a dozen times in the State of Texas.” He had previously lived in Oklahoma and said he had “committ[ed] homosexual activity in Oklahoma.” When asked “when did you first enter into such activities?” he answered, “I’ve always been a homosexual, ... from birth.” He considers himself “now a known homosexual in the community.”46
A certificate that an alien is suffering from a medical condition that requires him to be excluded is conclusive. See, e.g., United States ex rel. Johnson v. Shaughnessy, 336 U.S. 806, 69 S.Ct. 921, 93 L.Ed. 1054 [1448]*1448(1949); United States ex rel Wulf v. Esperdy, 277 F.2d 537 (2d Cir.1960). The statute and these decisions might well lead to the conclusion that a medical determination by a PHS officer that the alien is not suffering from such a condition is also conclusive. But neither the premise nor the inference leads to the conclusion that non-excludability is conclusively established by the absence of any examination at all.
The procedural protections built into the exclusion process demonstrate Congress’s intent that only competent evidence of medical excludability be adduced in exclusion proceedings. But there is no reason why an informed applicant’s admission that he falls within an excludable class is not competent evidence on which to base an exclusion decision. Section 1226(d) of the United States Code is not to the contrary. That section specifies that, if an immigration judge in an exclusion hearing is presented with a medical certificate “that an alien is afflicted ... with any mental disease, defect, or disability,” his decision “shall be based solely on such certification.” It merely makes clear that the petitioner has no right to introduce evidence rebutting the certificate.47 It does not expressly forbid an immigration judge to find an applicant excludable on the basis of evidence other than a medical certificate.
Although in Boutilier, the Public Health Service had issued a class A medical certificate stating that in the opinion of the subscribing physicians the petitioner “was afflicted with a class A condition, namely, psychopathic personality, sexual deviate” at the time of his admission, there is no indication in the opinion that the INS would have been required to ignore an admission by Boutilier that he was a homosexual. Boutilier v. INS, 387 U.S. at 120, 87 S.Ct. at 1565, 18 L.Ed.2d at 664. Likewise in Kovacs, the Second Circuit noted that a medical certificate had been prepared. Kovacs v. United States, 476 F.2d 843, 844 n. 1 (2d Cir.1973). These decisions indicate only that, in the past, after an alien has been admitted, the INS has obtained a class A certificate as a means of proving deportability. They do not establish that the certificate is indispensable.
To remand the case for a medical determination of homosexuality would appear to be to ask for a certification of the obvious. It is patent that sexual preference cannot be determined by blood test or physical examination; even doctors must reach a decision by interrogation of the person involved or of others professing knowledge about that person. To require the INS to disregard the most reliable source of information, the statements of the person involved, would be to substitute secondary evidence for primary.
Longstaff contends alternatively that the fact that he was admitted to the United States bars inquiry into his excludability eighteen years ago. This argument will not bear scrutiny. As Longstaff concedes, a previously admitted alien may be deported if it is determined that he should have been excluded on any of the numerous nonmedical bases stated in the Act, such as criminal conviction or anarchy.48 He asserts, however, that the PHS officer’s failure to detect an excluding mental or physical condition is definitive.
Administrative practice and judicial precedent both disclose the error of this argument. In Boutilier, for example, the question of excludability for homosexuality arose nine years after the alien’s admission. In numerous other cases, aliens have been deported on the basis of post-admission determinations that they should have been excluded because of physical or mental [1449]*1449problems.49 The Ninth Circuit affirmed an order of deportation based on petitioner’s admissions and conflicting testimony of two psychiatrists because the alien was a homosexual when admitted from Canada in LaVoie v. Immigration and Naturalization Service, 418 F.2d 732 (9th Cir.1969), cert. denied, 400 U.S. 854, 91 S.Ct. 72, 27 L.Ed.2d 92 (1970). We affirmed a deportation order based on an alien’s homosexuality without making clear whether she had been certified as a homosexual when admitted in Quiroz v. Neelly, 291 F.2d 906 (5th Gir. 1961). In several cases, the sufficiency of the evidence at a deportation hearing has been questioned.50 To reach that question, the Board of Immigration Appeals and various courts had to assume that an alien’s admissibility at the time of entry may be reconsidered.
In considering appeals from deportation orders issued on the basis of a charge that the alien was a homosexual when admitted, the Board of Immigration Appeals has remanded cases for a medical determination, stating that neither the immigration judge nor the Board has “the expertise or the authority” to determine medical admissibility.51 In all of these appeals the grounds for medical excludability were disputed. If the alien admits the facts determining his ex-cludability, the Board, other immigration officials, and the courts may assuredly act on the basis of that admission.52
In response to the refusal of the PHS to make medical determinations of homosexuality and the determination of the office of legal counsel that the INS was nonetheless obliged to exclude homosexuals, the INS has adopted a new policy, “Guidelines and Procedures for the Inspection of Aliens Who Are Suspected of Being Homosexual.” 53 This statement provides that an arriving alien will not be asked any questions regarding his sexual preference.54 If an [1450]*1450alien “makes an unambiguous oral or written admission of homosexuality” (which does not include exhibition of buttons, literature, or other similar material), or if a third person who is also presenting himself for inspection “voluntarily states, without prompting or prior questioning, that an alien who arrived in the United States at the same time ... is a homosexual,” the alien may be examined privately by an immigration officer and asked to sign a statement that he is a homosexual. That statement forms the evidentiary basis for exclusion.
Thus, the administrative agency charged with enforcement of the Act has interpreted it as not requiring a medical certificate as a condition for the exclusion of homosexuals. This interpretation is entitled to deference.55
That homosexuality is no longer considered a psychopathic condition is established by the opinion of the government’s highest medical officer, the Surgeon General. We are bound, nonetheless, by Boutilier’s ruling that the phrase “psychopathic personality,” is a term of art, not dependent on medical definition,56 and by the congres[1451]*1451sional bar against persons “afflicted with ... sexual deviation.” Homosexuality can now be demonstrated in INS proceedings only by an alien’s unambiguous admission or by the voluntary statement of a third person, made without either prompting or questioning. Longstaff is thus barred from naturalization by his own truthful statements that he was excludable as a homosexual at the time of his entry, and, therefore, was not lawfully admitted for permanent residence.57 There is no evidence that, when he sought a visa eighteen years ago, he was asked any question that would indicate to him or to any other intelligent layman that his sexual preferences might affect the issuance of a visa, or that he knowingly gave a false answer to any question asked of him. In the eighteen years of his residence, he has led a constructive life. We are, however, bound to decide according to a law made in the exercise of a power that is plenary. If Congress’s policy is misguided, Congress must revise that policy. If the result achieved by the policy is unfair to a deserving person who desires to become a citizen, the injustice must be corrected by lawmakers.
Based on the finding that Longstaff was a homosexual when he entered the United States, the district court correctly decided that he was then excludable, that his ex-cludability may now be proved, and that, being excludable, he may not be naturalized.58 Therefore, its judgment is AFFIRMED.