Palindrom: Perbedaan antara revisi

 

Istilah ''palidrom'' pertama kali diperkenalkan oleh [[Henry Peacham (lahir 1578)|Henry Peacham]] pada 1638.<ref>Henry Peacham, ''The Truth of our Times Revealed out of One Mans Experience'', 1638, [https://quod.lib.umich.edu/cgi/t/text/pageviewer-idx?cc=eebo;c=eebo;idno=a09207.0001.001;node=A09207.0001.001:5;seq=134;submit=Go;type=simple;vid=14563;q1=palindrome;page=root;view=text hlm. 123]</ref> Kata tersebut berasal dari akar kata {{lang|grc|πάλιν}} 'palin' dalam bahasa Yunani yang berarti "lagi" dan {{lang|grc|δρóμος}} 'dromos' yang berarti "arah". Sementara itu, καρκινικός 'karsinik' ({{abbr|har.|secara harfiah berarti}} ''mirip-kepiting'') juga menjadi sebutan lain untuk gaya penulisan huruf per huruf yang menghasilkan sebuah kata ataupun kalimat yang dapat dibaca secara terbalik ataupun tidak.<ref>{{Cite web|url=http://www.greek-language.gr/greekLang/modern_greek/tools/lexica/search.html?lq=%CE%BA%CE%B1%CF%81%CE%BA%CE%B9%CE%BD%CE%B9%CE%BA%CF%8C%CF%82&dq=|title=Combined word search for καρκινικός|last=Triantaphylides Dictionary|first=Portal for the Greek Language|website=www.greek-language.gr|access-date=6 May 2019}}</ref><ref>[[William Martin Leake]], ''Researches in Greece'', 1814, hlm. 85</ref>

== Teori komputasi ==

Dalam [[teori automata]], suatu [[himpunan (matematika)|himpunan]] dari semua palindrom dalam komposisi [[alfabet]] yang dimasukkan bukan merupakan komponen [[bahasa reguler]], melainkan sebuah contoh tipikal dari [[bahasa formal|formal]] yang memiliki [[bahasa konteks bebas|konteks bebas]]. Hal ini berarti, mustahil bagi sebuah komputer atau mesin komputasi lainnya dengan [[automaton terhingga|kapasitas memori terbatas]] dapat melakukan palindrom dengan benar. <!-- (Must say "on one pass" because, if it were allowed random access to the data, the test becomes trivial: simply check data[n] == data[L-n] for all n up to L/2 where L is the length.) --><!-- The preceding comment does not take into account that if the memory (including registers) is only M bits, the computer can only represent these values of n from 0 to 2^M-1, so consider the problem when L >= 2^M. --> <!--(For practical purposes with modern computers, this limitation would apply only to impractically long letter-sequences.)-->