ماشین مبدل دودویی یک عدد دودویی با $n$ رقم را از ورودی می گیردو با فشار دادن یکی از دو دکمه ی آن، یکی از دو تبدیل زیر را روی عدد ورودی انجام می دهد.

1. دکمه ی یک: سمت راست ترین رقم را از 0 به 1 و از 1 به 0 تغییر می دهد.

2. دکمه دو: سمت راست ترین رقم 1 را پیدا می کند و رقم سمت چپ آن را از 0 به 1 و از 1 به 0 تغییر می دهد. دقت کنید در صورتی که سمت راست ترین 1 در سمت چپ ترین مکان باشد یا رشته تمام 0 باشد، تغییری انجام نمی دهد.

برای مثال با استفاده از ماشین مبدل دودویی می توان عدد 001001 را به 011001 تبدیل کرد. روش تبدیل به این صورت است که ابتدا دکمه یک ، سپس دکمه دو و در انتها دکمه یک را فشار می دهیم. ثابت کنید با استفاده از ماشین مبدل دودویی می توان هر عدد دودویی با $n$رقم را به هر عدد دودویی با $n$ رقم تبدیل کرد.

• سوال بعد