Palindrom

Palindrom merupakan sebuah kata, bilangan, frasa, atau susunan karakter lain yang serupa jika dibaca dengan urutan terbalik ataupun tidak, seperti dalam kakak ataupun apa. Selain itu, terdapat juga bilangan palindrom yang dapat dibaca dengan cara serupa. Sebagai contoh, susunan waktu dan tanggal tertentu seperti 11/11/11 11:11 ataupun Selasa, 22 Februari 2022 tergolong sebagai hari palindrom (dengan format hh-bb-tttt), karena dapat dibaca dari kiri ke kanan ataupun sebaliknya. Unsur penulisan seperti kapitalisasi, tanda baca, dan batas kata tidak diperhatikan dalam palindrom yang memiliki panjang setara dengan sebuah kalimat.

Menulis karya sastra dalam bentuk palindrom adalah contoh dari tulisan cangkupan terbatas.

Istilah palidrom pertama kali diperkenalkan oleh Henry Peacham pada 1638. Kata tersebut berasal dari akar kata  'palin' dalam bahasa Yunani yang berarti "lagi" dan  'dromos' yang berarti "arah". Sementara itu, καρκινικός 'karsinik' ( 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.

Teori komputasi 
Dalam teori automata, suatu himpunan dari semua palindrom dalam komposisi alfabet yang dimasukkan bukan merupakan komponen bahasa reguler, melainkan sebuah contoh tipikal dari formal yang memiliki konteks bebas. Hal ini berarti, mustahil bagi sebuah komputer atau mesin komputasi lainnya dengan kapasitas memori terbatas dapat melakukan palindrom dengan benar.  

Selain itu, kemampuan komputasinya diperparah dengan kemungkinan bahwa palindrom tidak dites penggunaannya oleh deterministic pushdown automaton, yang berarti mereka tidak termasuk dalam golongan fungsi parser LR(k) atau LL(k) yang dapat dkparserkan. Saat palindrom dibaca dari kiri ke kanan, secara esensial mustahil untuk menentukan lokasi "pusat" hingga seluruh kata atau kalimat dibaca utuh.

Akan tetapi, substring palindromik terpanjang dari input yang dimasukman masih mungkin ditemukan dengan metode waktu linear.

Kepadatan palindromik dari suatu kata tak terhingga w atas alfabet A memiliki nilai yang didefinisikan sebagai nol jika awalan berupa palindrom dan memiliki jumlah terhingga, jika tidak, misalkan awalan palindromik dapat melebar hingga sepanjang  untuk , maka penentuan nilai kepadatan didefinisikan sebagai

Diantara banyak kata aperiodik yang sudah ditemukan, kata Fibonacci memiliki kepadatan paling besar, yaitu sebesar , dengan  melambangkan rasio emas .

Palstar adalah gabungan dari sejumlah string palindrom, dan harus memiliki komposisi palindrom yang bukan terdiri dari satu huruf saja, jika tidak, semua string akan menjadi bentuk palstar.

Lihat pula 
 ambigram
 anagram
 pangram
 permainan kata
 Kata "Le-itiel" pada Amsal 30:1

Pranala luar 
 Pelincah lidah

Palindrom
Permainan kata