Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Belirlenimsiz Turing makinesi, bulunduğu durumdan sonraki durum için birden fazla seçenek Turing makinasıdır. Makina aşağıdaki bileşenlerden oluşur:
- Bir veya birkaç şerit
- Şerit(ler)i okumak için kafa(lar)
- Geçiş tablosunu ve Turing makinesinin o anki durumunu içeren bir iç mantık
Belirlenimli Turing makinasından farklı olarak, belirlenimsiz Turing makinesi aynı durum için birkaç adım arasından seçim yapabilir. Başka bir deyişle, geçiş tablosunda aşağıdaki gibi girdiler olabilir:
| Güncel durum | Okunan simge | İşlem | Yeni durum |
|---|---|---|---|
| d0 | 1 | Sağa git | d2 |
| d0 | 1 | Sola git | d1 |
Bu durumda, ilgili Turing makinesi d0 durumundayken ve 1 sembolünü görürken ister sağa ister sola gidebilir. İki çeşit belirlenimsizlik vardır:
- Melekimsi belirlenimsizlik: Bu tip bir belirlenimsizlikte, makine birkaç seçim arasından her zaman "doğru" olanı seçer.
- Şeytanî belirlenimsizlik: Bu tip belirlenimsizlikte ise makine birkaç seçim arasından her zaman "yanlış" olanı seçer.
Belirlenimsiz Turing makinesi, melekimsi bir belirlenimsizlik kullanır ve dolayısıyla her zaman kendini sonuca yaklaştıran seçimi yapacaktır. Melekimsi belirlenimsiz bir Turing makinasıyla polinomsal zamanda çözülebilen problemler NP kümesini oluşturur. Belirlenimsiz makina, belirlenimli bir Turing makinası ile simüle edilebileceği için belirlenimsiz makinanın çözebildiği problemler kümesi, belirlenimli makinanın çözebildiği problemler kümesine eşittir.
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Belirlenimsiz Turing makinesi bulundugu durumdan sonraki durum icin birden fazla secenek Turing makinasidir Makina asagidaki bilesenlerden olusur Bir veya birkac serit Serit ler i okumak icin kafa lar Gecis tablosunu ve Turing makinesinin o anki durumunu iceren bir ic mantik Belirlenimli Turing makinasindan farkli olarak belirlenimsiz Turing makinesi ayni durum icin birkac adim arasindan secim yapabilir Baska bir deyisle gecis tablosunda asagidaki gibi girdiler olabilir Guncel durum Okunan simge Islem Yeni durumd0 1 Saga git d2d0 1 Sola git d1 Bu durumda ilgili Turing makinesi d0 durumundayken ve 1 sembolunu gorurken ister saga ister sola gidebilir Iki cesit belirlenimsizlik vardir Melekimsi belirlenimsizlik Bu tip bir belirlenimsizlikte makine birkac secim arasindan her zaman dogru olani secer Seytani belirlenimsizlik Bu tip belirlenimsizlikte ise makine birkac secim arasindan her zaman yanlis olani secer Belirlenimsiz Turing makinesi melekimsi bir belirlenimsizlik kullanir ve dolayisiyla her zaman kendini sonuca yaklastiran secimi yapacaktir Melekimsi belirlenimsiz bir Turing makinasiyla polinomsal zamanda cozulebilen problemler NP kumesini olusturur Belirlenimsiz makina belirlenimli bir Turing makinasi ile simule edilebilecegi icin belirlenimsiz makinanin cozebildigi problemler kumesi belirlenimli makinanin cozebildigi problemler kumesine esittir