Özyinelemeli küme

Gelen Hesaplama teorisi , bir özyinelemeli grubu veya Karar verilebilen grubu a, dizi arasında bir tamsayı olan (tam sayı ya da kolayca kodlanabilir elemanları) karakteristik fonksiyonu a, özyinelemeli fonksiyon anlamında matematiksel mantık .

Başka bir deyişle, bir küme , yalnızca ve ancak, herhangi bir tamsayının içinde olup olmadığını sonlu zamanda belirlemeye izin veren bir Turing makinesi (bir bilgisayar programı ) varsa, özyinelemelidir . E{\ displaystyle E} T{\ displaystyle T}E{\ displaystyle E}

∀değil∈DEĞİL{\ displaystyle \ forall n \ in \ mathbb {N}}
T(değil)=ÖUben Eğer değil∈E{\ displaystyle T (n) = EVET \ {\ mbox {si}} \ n \ E’de}
T(değil)=DEĞİLÖDEĞİL Eğer değil∉E{\ displaystyle T (n) = HAYIR \ {\ mbox {si}} \ n \ notin E}

Setin Bu tür bir karşılık gelen gerçek kavram ve John R. Myhill kapsamlı ve açık bir şekilde tanımlanabilir kavramları vardır. Özyinelemeli olarak numaralandırılabilir (özyinelemeli olmayan) bir küme kavramı , daha ziyade yapıcı bir kavramdır , içeriği zamanla daha net, daha iyi ve daha iyi anlaşılırken, onu tamamen tanımlamak hiçbir zaman mümkün değildir.

Resmi sistem açısından tanım

Biçimsel sistemlerin terminolojisinde , aşağıdaki tanım eşdeğerdir:

E{\ displaystyle E}ancak ve ancak formun " içinde  " ve formun "  içinde değil " ifadeleri için doğru ve eksiksiz bir biçimsel sistem varsa yinelemelidir   .değil{\ displaystyle n}E{\ displaystyle E}değil{\ displaystyle n}E{\ displaystyle E}

Özellikleri

• Bir dizi A ve ancak eğer özyinelemelidir A ve tamamlayıcısı olan ardışık enumerable .
• Eğer A ve B özyinelemeli, o zaman A ∩ B ve A ∪ B özyinelemeli bulunmaktadır.

Örnekler

Aşağıdaki kümeler özyinelemelidir:

• herhangi bir sonlu küme (boş küme ∅ önemsiz bir örnektir);
• bir tamsayının katları kümesi (tam sayılar, çift sayılar, vb.);k{\ displaystyle k}
• asal sayılar kümesi;
• belirli bir Diophantine denkleminin çözüm kümesi .

Aşağıdaki kümeler özyinelemeli olarak numaralandırılabilir ancak özyinelemeli değildir:

• tamsayı çözüme sahip Diophantine denklemleri seti;
• durduran tüm programlar (süresiz olarak çalışmayan programlar): bkz. "  Sorunu durdurma  ".

Syracuse terimlerinin çoklu kümesinin ilk terimin herhangi biri için özyinelemeli olup olmadığı şu anda bilinmemektedir (ima edilen: tamsayı). Syracuse varsayım aksini iddia eden, ancak bu güne kadar kalıntıları undemonstrated. Öte yandan, tanım gereği özyinelemeli olarak numaralandırılabilir. sen0=k{\ displaystyle u_ {0} = k}k>0{\ displaystyle k> 0}k{\ displaystyle k}

Notlar ve referanslar

1. Jean-Paul Delahaye , Bilgi, Karmaşıklık ve Şans , Hermes Science Publishing,1999( ISBN  2-7462-0026-0 )s. 74.

Ayrıca görün

İlgili Makaleler

• Karar verilebilir sorun
• Onuncu Hilbert Problemi

Dış bağlantı

Özyineleme kursu