Halting prediction on busy beaver type Turing machines based on information entropy
Busy beaver türü Turing makinalarında bilgi entropisine dayalı sonlanma öngörüsü
- Tez No: 232853
- Danışmanlar: DOÇ. DR. MUHAMMED ULUDAĞ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2008
- Dil: İngilizce
- Üniversite: Galatasaray Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 66
Özet
Bu tezde Busy Beaver türü Turing Makinaları için asimptotik olarak tam bir sonlanma öngörüsü öneriyoruz. Aynı zamanda farklı sonlanma öngörüsü sistemlerini karşılaştırabilmek için bir verimlilik ölçümü sunuyoruz ve son olarak geçerli Turing Makinası tanımlarını topolojik anlamda temsil edebilecek Manhattan uzaklık fonksyonu türevi bir uzaklık fonksyonuna sahip metrik bir uzay ve bu uzaydaki komşulukları tanımlıyoruz.Sonlanma öngörüsü sistemimiz, benzetim geçmişindeki bir noktada Turing makina teybinin ziyaret edilmiş kısım uzunluğunun, teyp başlığının kaymalarına oranını, simülasyon geçmişinde o nokta için bilgi yoğunluğunun bir ölçümü olarak kullanarak simülasyon geçmişinin o anı için bir sayma sürecinin üretilip üretilemeyeceğini ispatlamaya dayanmaktadır. Busy Beaver Turing Makinalarının simülasyon geçmişlerinin her noktasında zamansal konumunu takip edebiliyor olması gerektiğini göstererek, önerdiğimiz bilgi yoğunluğu ölçütünü zamansal konum takibinin mümkünlüğünü test ederek takibin imkansızlığı halini sonlanmama öngörüsü kanıtı olarak kullanıyoruz. Normal makina benzetimine çok az bir hesapsal yük ekleyerek verimli bir erken sonlanma/sonlanmama öngörüsüne ulaşabiliyoruz.
Özet (Çeviri)
In this thesis we mainly propose a new asymptotically complete halting predictor for Turing Machines of Busy Beaver type which is defined by T.Rado in 1962. Also we propose an efficiency measure to benchmark different halting predictors and finally we propose a topological representation for space of valid Turing Machines as a metric space with a Manhattan like distance metric allowing us to define a neighborhood between Turing Machines.Our predictor uses the ratio of tape space explored to cycles taken during a point in simulation history as a measure of information density for that moment of simulation, which allows us to predict the unconstructability of a counting process in terms of number of cycles occurred till that point. We show that a halting Busy Beaver Turing Machine has to have the ability to keep track of its temporal position at each point of its simulation; and we construct a non-halting predictor using mentioned information density measure to show inability to track temporal position.Our method predicts non-halting of Busy Beaver Turing Machines by incurring negligible computational overhead to the regular simulation, while obtaining results very early on simulation; even for complicated machine configurations where conventional automated non-halting proving is ineffective or unfeasible.
Benzer Tezler
- Antikanser peptidlerin sınıflandırma algoritmaları ile tahmini
Prediction of anticancer peptides using by classification algorithms
RANA SU
Yüksek Lisans
Türkçe
2023
BiyokimyaMimar Sinan Güzel Sanatlar Üniversitesiİstatistik Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BİLGE ÖZLÜER BAŞER
- İstanbul Boğazı'nda seyir emniyetini etkileyen meteorolojik faktörlerin analizi
Analysis of meteorological factors affecting the safety of navigation in the İstanbul Strai̇t
ALİ CAN SUR
Yüksek Lisans
Türkçe
2024
Deniz Bilimleriİstanbul Üniversitesi-CerrahpaşaDeniz Ulaştırma İşletme Mühendisliği Ana Bilim Dalı
PROF. DR. GÖKHAN KARA
- Elektrikli araç bataryalarının döngüsel ekonomi kapsamında incelenmesi
Examination of lithium ion battery recycling process within the scope of circular economy
RABİA DİŞÇİOĞLU
Yüksek Lisans
Türkçe
2022
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ŞEYDA SERDAR ASAN
- Vakum borulu kollektörlerin İstanbul şartlarında teorik analizi
Analysis of different of types vacuum tubular collectors for the condition of İstanbul
NAZAN YARGICI
- Computability-theoretic limitations of qualitative simulation
Nitel benzetimin hesaplanabilirlik kuramına dayalı sınırları
ÖZGÜR YILMAZ
Yüksek Lisans
İngilizce
2005
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEM SAY