Ausweisung, hat sich ergeben:
A.- Der türkische Staatsangehörige A._, geboren 1947, reiste 1985 als Asylbewerber in die Schweiz ein. Sein Asylgesuch wurde am 7. November 1986 erstinstanzlich abgewiesen; während des hängigen Beschwerdeverfahrens heiratete er am 14. April 1989 die Schweizer Bürgerin B._ und erhielt in der Folge eine auf ein Jahr befristete Aufenthaltsbewilligung zum Verbleib bei der Ehefrau. Die Aufenthaltsbewilligung wurde jährlich erneuert, letztmals bis zum 14. April 1995.
A._ musste sich in den Jahren 1987 und 1995 zwei Herzklappenersatzoperationen unterziehen. Mit Verfügung der IV-Stelle Basel-Stadt vom 12. Oktober 1994 wurde ihm rückwirkend ab 1. September 1992 eine monatliche halbe IV-Rente zugesprochen. Für seine in der Türkei lebenden vier Kinder aus erster Ehe, die 1984 geschieden worden war, erhielt er ebenfalls rückwirkend auf den 1. September 1992 Zusatzrenten. Am 5. März 1996 wurde ihm rückwirkend per
1. Juni 1995 eine ganze einfache Invalidenrente zugesprochen, die mit Wirkung ab 1. Januar 1998 durch monatliche Ergänzungsleistungen zur IV komplettiert wurde.
Seit Ende 1989/Anfang 1990 war A._ wiederholt arbeitslos und bezog Arbeitslosentaggelder. Ab dem
14. Februar 1992 musste das Ehepaar A._-B. _ auch vom Fürsorgeamt unterstützt werden. 1993 trennten sich die Ehegatten. Ihre Ehe wurde am 17. März 1995 geschieden; das Urteil erwuchs am 28. März 1995 in Rechtskraft.
B.- Die Kantonale Fremdenpolizei Basel-Stadt (im Folgenden:
Fremdenpolizei) verwarnte A._ am 2. Januar 1995 gestützt auf Art. 10 Abs. 1 lit. d des Bundesgesetzes über Aufenthalt und Niederlassung der Ausländer vom 26. März 1931 (ANAG, SR 142. 20) wegen "Schuldenmacherei und Bezug von Fürsorgeleistungen" und drohte ihm den Widerruf bzw. die Nichterneuerung der Aufenthaltsbewilligung an. Am 20. Oktober 1995 verweigerte sie ihm die Erneuerung der Aufenthaltsbewilligung bzw. die Erteilung einer Niederlassungsbewilligung und setzte eine 30-tägige Frist zur Ausreise ab Erhalt der Verfügung. A._ rekurrierte hiergegen erfolglos an das Polizei- und Militärdepartement und dann an das Appellationsgericht (als Verwaltungsgericht) des Kantons Basel-Stadt.
C.- Mit Verwaltungsgerichtsbeschwerde vom 2. März 2000 hat A._ beim Bundesgericht beantragt, das Urteil des Appellationsgerichtes des Kantons Basel-Stadt als Verwaltungsgericht vom 30. Dezember 1999 aufzuheben und ihm die Niederlassungsbewilligung zu erteilen. Eventualiter sei die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
Im Weiteren beantragt er, der Verwaltungsgerichtsbeschwerde die aufschiebende Wirkung zuzuerkennen und ihm die unentgeltliche Prozessführung und Verbeiständung zu bewilligen.
Das Appellationsgericht (als Verwaltungsgericht) und das Polizei- und Militärdepartement des Kantons Basel-Stadt stellen den Antrag, die Beschwerde abzuweisen. Ebenso schliesst das Bundesamt für Ausländerfragen in seiner Vernehmlassung vom 18. April 2000 auf Abweisung der Beschwerde.
D.- Der Abteilungspräsident hat der Beschwerde am 27. März 2000 aufschiebende Wirkung zuerkannt.
E.- Das Polizei- und Militärdepartement des Kantons Basel-Stadt übermittelte dem Bundesgericht am 18. Mai 2000 Kopien des dem Beschwerdeführer für die Dauer vom 24. Mai bis zum 23. Juni 2000 aus gesundheitlichen Gründen erteilten Rückreisevisums für die Türkei sowie eines entsprechenden Arztzeugnisses von Dr.med. X._, Basel, vom 15. Mai 2000.

Das Bundesgericht zieht in Erwägung:
1.- a) Nach Art. 100 Abs. 1 lit. b Ziff. 3 OG ist die Verwaltungsgerichtsbeschwerde auf dem Gebiete der Fremdenpolizei unzulässig gegen die Erteilung oder Verweigerung von Bewilligungen, auf die das Bundesrecht keinen Anspruch einräumt.
Gemäss Art. 4 ANAG entscheidet die zuständige Behörde, im Rahmen der gesetzlichen Vorschriften und der Verträge mit dem Ausland, nach freiem Ermessen über die Bewilligung von Aufenthalt oder Niederlassung. Es besteht damit grundsätzlich kein Anspruch auf Erteilung einer Aufenthaltsbewilligung, es sei denn, der Ausländer könne sich auf eine Sondernorm des Bundesrechts oder eines Staatsvertrags berufen (<ref-ruling> E. 2a S. 291, 361 E. 1a S. 363/364; <ref-ruling> E. 1b S. 147, je mit Hinweisen).
b) Der ausländische Ehegatte eines Schweizer Bürgers hat nach Art. 7 ANAG (in der Fassung vom 23. März 1990) Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung (Abs. 1 Satz 1) sowie nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren auf Erteilung der Niederlassungsbewilligung (Abs. 1 Satz 2). Der Anspruch erlischt, wenn ein Ausweisungsgrund vorliegt (Abs. 1 Satz 3). Kein Anspruch besteht, wenn die Ehe eingegangen worden ist, um die Vorschriften über Aufenthalt und Niederlassung von Ausländern und namentlich jene über die Begrenzung der Zahl der Ausländer zu umgehen (Abs. 2). Für die Eintretensfrage ist im Zusammenhang mit Art. 7 ANAG einzig darauf abzustellen, ob formell eine eheliche Beziehung besteht; anders als bei Art. 8 EMRK ist nicht erforderlich, dass die Ehe intakt ist und tatsächlich gelebt wird (<ref-ruling> E. 1b S. 292; <ref-ruling> E. 2 S. 100/101; <ref-ruling> E. 2b S. 18).
c) Der Beschwerdeführer wurde von seiner schweizerischen Ehefrau am 17. März 1995 geschieden. Die Ehegatten waren seit dem 15. Mai 1993 gerichtlich getrennt; da der Beschwerdeführer sich jedoch vor der rechtskräftigen Scheidung während mehr als fünf Jahren ordnungsgemäss in der Schweiz aufhielt, hat er gestützt auf Art. 7 Abs. 1 Satz 2 ANAG einen Anspruch auf Niederlassungsbewilligung erworben, welcher mit der Scheidung nicht erloschen ist (BGE <ref-ruling> E. 4c S. 104/105). Die Frage, ob die Bewilligung zu verweigern sei, weil einer der in Art. 7 ANAG vorgesehenen Ausnahmetatbestände gegeben ist, betrifft nicht das Eintreten, sondern bildet Gegenstand der materiellen Beurteilung (<ref-ruling> E. 2b S. 291; <ref-ruling> E. 1d S. 294; <ref-ruling> E. 2b S. 18; <ref-ruling> E. 2d S. 419; <ref-ruling> E. 3d S. 151). Auf die Verwaltungsgerichtsbeschwerde ist somit einzutreten.
2.- a) Nach Art. 7 Abs. 1 Satz 3 ANAG erlischt der Anspruch auf eine Niederlassungsbewilligung, wenn ein Ausweisungsgrund vorliegt. Ob dem Beschwerdeführer die Niederlassungsbewilligung zu erteilen oder aber zu verweigern sei, beurteilt sich folglich danach, ob er aus der Schweiz ausgewiesen werden könnte, was wiederum im Lichte der Ausweisungsgründe von Art. 10 ANAG zu beurteilen ist. Nicht massgebend sind dagegen die Gründe, welche nach den Vorschriften des ANAG zu einem Widerruf der Aufenthaltsbewilligung Anlass geben können (Art. 9 Abs. 2 ANAG). Der Beschwerdeführer hat grundsätzlich Anspruch auf Erteilung der Niederlassungsbewilligung; nur ein Verhalten, das die Ausweisung (Art. 10 ANAG) und damit das Erlöschen der Niederlassungsbewilligung (Art. 9 Abs. 3 lit. b ANAG) zur Folge hat, kann die Verweigerung der Bewilligung rechtfertigen (<ref-ruling> E. 3b S. 367/368).
b) Gemäss Art. 10 Abs. 1 ANAG kann ein Ausländer ausgewiesen werden, wenn er wegen eines Verbrechens oder Vergehens gerichtlich bestraft wurde (lit. a) oder wenn sein Verhalten im allgemeinen und seine Handlungen darauf schliessen lassen, dass er nicht gewillt oder nicht fähig ist, sich in die im Gaststaat geltende Ordnung einzufügen (lit. b). Der letztgenannte Ausweisungsgrund wird in Art. 16 Abs. 2 der Vollziehungsverordnung vom 1. März 1949 zum ANAG (ANAV, SR 142. 201) näher umschrieben. Danach kann die Ausweisung nach Art. 10 Abs. 1 lit. b ANAG namentlich als begründet erscheinen bei schweren oder wiederholten Verstössen gegen gesetzliche Vorschriften oder behördliche Verfügungen, grober Verletzung allgemeiner Gebote der Sittlichkeit, fortgesetzter böswilliger oder liederlicher Nichterfüllung der öffentlichrechtlichen oder privatrechtlichen Verpflichtungen oder sonstiger fortgesetzter Liederlichkeit oder Arbeitsscheu (Art. 16 Abs. 2 ANAV). Sodann kann ein Ausländer ausgewiesen werden, wenn er oder eine Person, für die er zu sorgen hat, der öffentlichen Wohltätigkeit fortgesetzt und in erheblichem Masse zur Last fällt (Art. 10 Abs. 1 lit. d ANAG). Die Ausweisung soll aber nur verfügt werden, wenn sie nach den gesamten Umständen angemessen erscheint (Art. 11 Abs. 3 ANAG). Hierbei sind namentlich die Schwere des Verschuldens des Ausländers, die Dauer seiner Anwesenheit in der Schweiz sowie die ihm und seiner Familie drohenden Nachteile zu berücksichtigen (Art. 16 Abs. 3 ANAV). Die Beurteilung der "Angemessenheit", d.h. der Verhältnismässigkeit, der Ausweisung ist eine Rechtsfrage, die vom Bundesgericht im Verfahren der Verwaltungsgerichtsbeschwerde frei überprüft werden kann (Art. 104 lit. a OG; vgl. <ref-ruling> E. 2a S. 523; <ref-ruling> E. 2b S. 356/357).
3.- a) Im Fremdenpolizeirecht stellt das Bundesgericht dann nicht auf die aktuellen tatsächlichen und rechtlichen Umständen ab, wenn - wie hier - eine richterliche Behörde als Vorinstanz entschieden hat. Diesfalls gelangt Art. 105 Abs. 2 OG zur Anwendung, wonach das Bundesgericht an die Feststellung des Sachverhalts gebunden ist, wenn die richterliche Vorinstanz diesen nicht offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen erhoben hat (<ref-ruling> E. 2a S. 365, mit Hinweisen).
b) Soweit das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht (im Folgenden: Verwaltungsgericht) die Verweigerung der Niederlassungsbewilligung auch damit begründet, der Beschwerdeführer habe übermässig Alkohol konsumiert und der Spielleidenschaft gefrönt, ist (trotz Art. 105 Abs. 2 OG) fraglich, ob das Bundesgericht an die betreffenden Feststellungen gebunden ist, da die Beweise (Behauptung der Ehefrau in der Scheidungsklage, Ausführungen im türkischen Scheidungsurteil aus dem Jahre 1984) äusserst dürftig sind und die Gegenbeweismittel des Beschwerdeführers ohne nähere Begründung nicht abgenommen wurden. Wie es sich damit im Einzelnen verhält, kann indessen dahingestellt bleiben, da die dem Beschwerdeführer vorgeworfene Spielleidenschaft und der damit in Zusammenhang stehende Alkoholkonsum nur dann den Schluss zulassen, er sei nicht fähig oder nicht willens, sich in die in der Schweiz geltende Ordnung einzufügen, wenn die genannten Laster sich in irgendeiner Weise negativ auf sein soziales Leben auswirken.
Darüber fehlen im angefochtenen Entscheid aber jegliche Feststellungen. Der damit verbundene Vorwurf der Liederlichkeit des Beschwerdeführers muss daher entfallen.
c) Das Verwaltungsgericht hat die Nichterteilung der Niederlassungsbewilligung - anders als noch das Polizei- und Militärdepartement des Kantons Basel-Stadt in seinem Entscheid vom 13. Januar 1999 - nur noch mit dem Vorwurf der Nichterfüllung öffentlichrechtlicher und privatrechtlicher Verpflichtungen (namentlich Nichtbezahlung von Steuerschulden und Krankenkassenprämien) und des Missbrauchs von Unterstützungsleistungen durch den Beschwerdeführer begründet.
Im Wesentlichen wird dazu Folgendes ausgeführt:
aa) Betreffend den Ausweisungsgrund von Art. 10 Abs. 1 lit. d ANAG (Bedürftigkeit) wird festgestellt, seit anfangs 1998, d.h. seit dem Beschwerdeführer eine ganze einfache Invalidenrente sowie monatliche Ergänzungsleistungen ausgezahlt werden, sei davon auszugehen, dass er der Fürsorge nicht mehr zur Last falle. Auch bestünden keine Anhaltspunkte für die Vermutung, der Beschwerdeführer werde sich weiterhin verschulden.
Nach diesen verbindlichen Feststellungen der Vorinstanz lässt sich dessen Ausweisung somit nicht - mehr - auf Art. 10 Abs. 1 lit. d ANAG stützen.
bb) Weiter wird festgehalten, der Ausweisungsgrund von Art. 10 Abs. 1 lit. b ANAG (fehlende Einfügung in die im Gaststaat geltende Ordnung) sei bezüglich der lange dauernden Arbeitslosigkeit des Beschwerdeführers nicht erfüllt, da diese nicht auf "fortgesetzte Arbeitsscheu", sondern hauptsächlich auf dessen schlechte gesundheitliche Situation und auf die Verhältnisse des hiesigen Arbeitsmarktes zurückzuführen sei. Hingegen habe der Beschwerdeführer den genannten Ausweisungsgrund insoweit verwirklicht, als die Art und Weise seiner Schuldenmacherei als fortgesetzte liederliche Nichterfüllung der öffentlichrechtlichen oder privatrechtlichen Verpflichtungen im Sinne von Art. 16 Abs. 2 ANAV zu bezeichnen sei. Gegen den Beschwerdeführer beständen 25 Verlustscheine im Gesamtbetrag von Fr. 51'318. 85, wovon sich Fr. 42'201. 90 auf Steuerschulden und Fr. 5'038. 40 auf ausstehende Prämien und Selbstbehalte der Krankenkassen bezögen.
Ins Gewicht falle namentlich, dass der Beschwerdeführer bereits in den Jahren 1988 und 1989, als er noch in einem festen Arbeitsverhältnis gestanden habe, für Steuerschulden habe betrieben werden müssen. Auch habe er sich nicht darum bemüht, das starke Anwachsen von Verlustscheinsforderungen einzudämmen. Statt sich mit der Verwaltung über einen allfälligen Erlass der Steuerschulden zu verständigen, habe er für die Bezugsjahre 1990 und 1991 nicht einmal mehr die Steuererklärungen ausgefüllt, weshalb er mit einer empfindlichen Busse von Fr. 460.-- habe belegt werden müssen, die schliesslich von der Fürsorge übernommen worden sei. Zudem habe der Beschwerdeführer Krankenkassenprämien von über Fr. 5'000.-- zu einer Zeit nicht bezahlt, als ihm dies grösstenteils noch aus eigenem Verdienst möglich gewesen wäre. Sodann müsse es als grobes Verschulden qualifiziert werden, dass er, obwohl er als Teil der Unterstützungsleistungen auch die Kosten für seine Krankenkasse habe beziehen können, davon rund Fr. 1'000.-- nicht bestimmungsgemäss weitergeleitet habe. Desgleichen habe er einmal Fürsorgegeld, das er für die Miete erhalten habe, für sich selber verwendet. Weiter habe der Beschwerdeführer die ihm irrtümlicherweise für die Monate Februar und März 1992 ausbezahlten Arbeitslosengelder behalten, obwohl er eine Zessionserklärung zu Gunsten des Fürsorgeamtes unterschrieben habe. Das diesbezügliche Verhalten des Beschwerdeführers lasse auf die Unwilligkeit schliessen, sich der hiesigen Ordnung zu unterwerfen.
d) Zu prüfen bleibt, ob dem Beschwerdeführer aufgrund dieser Feststellungen die Erteilung der Niederlassungsbewilligung verweigert werden durfte.
4.- a) Das Bundesgericht hat sich in einem unveröffentlichten Entscheid vom 9. Juli 1998 i.S. N. mit der Schuldenmacherei als Ausweisungsgrund im Sinne von Art. 10 Abs. 1 lit. b ANAG befasst und dabei betreffend die Interessenabwägung festgestellt, im Vergleich zu einem ausländischen Straftäter oder auch der Belastung des öffentlichen Haushaltes durch fortgesetzte Fürsorgebedürftigkeit erscheine das öffentliche Interesse an der Fernhaltung eines Ausländers, das einzig dem Schutz potentieller Gläubiger zu dienen vermöge, doch von wesentlich geringerem Gewicht, soweit die Schuldenwirtschaft nicht auch strafrechtliche Folgen nach sich gezogen habe (E. 3e des zitierten Urteils). Sodann seien die Anforderungen, welche an eine zulässige Ausweisung gestellt würden, im Falle einer langen Anwesenheitsdauer in der Schweiz streng und würden nach der Rechtsprechung beim Ausweisungsgrund der Fürsorgeabhängigkeit noch strenger gehandhabt. Das Gleiche müsse auch gelten, wenn einem Ausländer Schulden zum Vorwurf gemacht würden (E. 3c des zitierten Urteils unter Hinweis auf <ref-ruling> E. 2c S. 436 und 119 Ib 1 E. 4 S. 7/8).
b) Der Beschwerdeführer lebt seit rund 15 Jahren in der Schweiz. Gemäss Erhebungen des Informationsdienstes der kantonalen Fremdenpolizei vom 5. Dezember 1994 im Hinblick auf die Verlängerung der Aufenthaltsbewilligung bzw. der Erteilung der Niederlassungsbewilligung bestanden zu diesem Zeitpunkt gegen den Beschwerdeführer Verlustscheine im Betrag von Fr. 50'925.--. Dessen Schulden belaufen sich nach den Feststellungen des Verwaltungsgerichts insgesamt auf Fr. 51'318. 85, sodass davon ausgegangen werden kann, er habe sich seit Ende 1994 nicht bzw. nur noch im Umfang von rund Fr. 400.-- weiter verschuldet. Das Verwaltungsgericht stellt dem Beschwerdeführer diesbezüglich denn auch eine günstige Prognose und hält fest, es sei "kein Anhaltspunkt vorhanden für die Vermutung, er werde sich auch weiterhin verschulden".
Auf diesem Hintergrund erscheinen die Ausführungen des Beschwerdeführers, dass seine hohe Verschuldung grösstenteils - wenn offenbar auch nicht nur - in Zusammenhang mit seiner sich anfangs der Neunzigerjahre verschlimmernden Herzkrankheit gestanden habe, die schliesslich zu seiner vollständigen Invalidität führte, nicht als unglaubwürdig.
Damit ist ein überwiegendes öffentliches Interesse, dem Beschwerdeführer die Niederlassungsbewilligung zu verweigern, nicht ohne weiteres ersichtlich; seine Ausweisung würde weder den öffentlichen Haushalt entlasten, da er nicht mehr fürsorgeabhängig ist, noch kann der Schutz potentieller Gläubiger im Vordergrund stehen, da es ihm bereits seit mehreren Jahren gelingt, mit den ihm zur Verfügung stehenden finanziellen Mitteln auszukommen. Auch wenn berücksichtigt wird, dass der Beschwerdeführer in der Vergangenheit verschiedentlich Mühe bekundete, sich in die hier geltende Ordnung einzufügen, und er namentlich wegen Nichteinreichung der Steuererklärung sogar gebüsst werden musste, vermag sein Verhalten insgesamt - gerade auch mit Blick auf seine lange Anwesenheitsdauer - eine Ausweisung nicht zu rechtfertigen (vgl. hierzu Alain Wurzburger, La jurisprudence récente du Tribunal fédéral en matière de police des étrangers, Bern 1997, S. 42). Demnach darf dem Beschwerdeführer die Niederlassungsbewilligung nicht verweigert werden. Die gegenteilige Auffassung der Vorinstanz verletzt Bundesrecht.
5.- Die Verwaltungsgerichtsbeschwerde erweist sich damit als begründet. Das angefochtene Urteil vom 30. Dezember 1999 des Appellationsgerichtes des Kantons Basel-Stadt als Verwaltungsgericht ist deshalb aufzuheben und die kantonale Fremdenpolizei anzuweisen, dem Beschwerdeführer die Niederlassungsbewilligung zu erteilen.
Entsprechend diesem Verfahrensausgang sind keine Kosten zu erheben (Art. 156 Abs. 2 OG). Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren zu entschädigen (Art. 159 Abs. 1 und 2 OG).
Dessen Gesuch um unentgeltliche Prozessführung und Verbeiständung wird damit gegenstandslos. Für die Festsetzung der Parteientschädigung im Verfahren vor den kantonalen Behörden, welche sich nach kantonalem Recht richtet, sind die Akten an die Vorinstanz zurückzuweisen.

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird gutgeheissen, das Urteil vom 30. Dezember 1999 des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht aufgehoben und die kantonale Fremdenpolizei angewiesen, dem Beschwerdeführer die Niederlassungsbewilligung zu erteilen.
2.- Es werden keine Kosten erhoben.
3.- Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen. Die Akten gehen zur Festlegung der Parteientschädigung für das kantonale Verfahren an das Verwaltungsgericht zurück.
4.- Dieses Urteil wird dem Beschwerdeführer, dem Polizei- und Militärdepartement sowie dem Appellationsgericht als Verwaltungsgericht des Kantons Basel-Stadt und dem Bundesamt für Ausländerfragen schriftlich mitgeteilt.
_
Lausanne, 16. Juni 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Die Gerichtsschreiberin: