Hubungan desain pemodelan grafik dengan budaya

Desain pemodelan grafis adalah suatu ilmu yang mempelajari tentang membuat dan menciptakan obyek baru berupa seni terapan, arsitektur, dan berbagai pencapaian kreatif lainnya yang direkayasa perangkat lunak merupakan suatu hal yang dilakukan di tahapan awal untuk pembuatan,penyimpanan,dan manipulasi model dan citra.

Faktor budaya memberikan pengaruh paling luas dan dalam pada perilaku konsumen. Pengiklan harus mengetahui peranan yang dimainkan oleh budaya, subbudaya dan kelas sosial pembeli. Budaya adalah penyebab paling mendasar dari keinginan dan perilaku seseorang. Budaya merupakan kumpulan nilai-nilai dasar, persepsi, keinginan dan perilaku yang dipelajari oleh seorang anggota masyarakat dari keluarga dan lembaga penting lainnya.

Setiap kebudayaan terdiri dari sub-budaya – sub-budaya yang lebih kecil yang memberikan identifikasi dan sosialisasi yang lebih spesifik untuk para anggotanya. Sub-budaya dapat dibedakan menjadi empat jenis: kelompok nasionalisme, kelompok keagamaan, kelompok ras, area geografis. Banyak subbudaya membentuk segmen pasar penting dan pemasar sering kali merancang produk dan program pemasaran yang disesuaikan dengan kebutuhan konsumen.

Contoh lambang agama Shinto di bawah ini Yin dan Yang menggunakan grafis warna hitam dan putih dalam mengaplikasikan simbolnya, yang bermakna kebaikan dan keburukan merupakan suatu keseimbangan.

Dalam rangka untuk berhasil dalam hal ini sangat kompetitif lingkungan, produk dan jasa yang dirancang untuk memberikan karakter dan individualitas, dan untuk menanamkan penjualan banding. Ini berarti bahwa desain mewakili suatu produk menjadi semakin canggih, yang dapat mengakibatkan bentrokan antara prinsip-prinsip estetika desainer dan rasa masyarakat umum atau kelompok sasaran. Hal ini dapat mengajukan pertanyaan filosofis tentang apakah itu adalah tugas desainer untuk memberikan masyarakat apa yang diinginkan atau apa yang mereka tidak tahu yang mereka butuhkan.

Kelas-kelas sosial adalah masyarakat yang relatif permanen dan bertahan lama dalam suatu masyarakat, yang tersusun secara hierarki dan keanggotaannya mempunyai nilai, minat dan perilaku yang serupa. Kelas sosial bukan ditentukan oleh satu faktor tunggal, seperti pendapatan, tetapi diukur dari kombinasi pendapatan, pekerjaan, pendidikan, kekayaan dan variable lain.

Sarana Analisis atau Means End Analysis

Sarana-Ends Analysis (MEA) adalah teknik yang digunakan dalam Artificial Intelligence untuk mengontrol pencarian dalam memecahkan masalah program komputer.

Ini juga merupakan teknik yang digunakan setidaknya sejak tahun 1950-an sebagai alat kreativitas, yang paling sering disebutkan dalam buku-buku teknik pada metode desain. Sarana-Ends Analysis juga merupakan cara untuk menjernihkan pikiran seseorang ketika memulai sebuah bukti matematis .

Sebuah aspek penting dari perilaku cerdas seperti dipelajari dalam AI adalah tujuan berbasis pemecahan masalah, sebuah kerangka di mana solusi dari masalah dapat dijelaskan dengan menemukan urutan tindakan yang mengarah ke tujuan yang diinginkan. Sebuah sistem pencari tujuan seharusnya terhubung ke lingkungan luar dengan saluran sensorik melalui yang menerima informasi tentang lingkungan dan saluran motor melalui yang bekerja pada lingkungan. (Istilah "aferen" digunakan untuk menggambarkan "ke dalam" arus sensorik, dan "eferen" digunakan untuk menggambarkan "keluar" perintah motorik.) Selain itu, sistem memiliki beberapa cara untuk menyimpan dalam memori informasi tentang keadaan lingkungan (informasi aferen) dan informasi tentang tindakan (informasi eferen). Kemampuan untuk mencapai tujuan tergantung pada membangun asosiasi, sederhana atau kompleks, antara perubahan tertentu di negara-negara dan tindakan tertentu yang akan membawa perubahan-perubahan tentang. Pencarian adalah proses penemuan dan perakitan urutan tindakan yang akan memimpin dari negara yang diberikan kepada keadaan yang diinginkan. Meskipun strategi ini mungkin cocok untuk belajar mesin dan pemecahan masalah, hal ini tidak selalu disarankan untuk manusia (misalnya beban kognitif teori dan implikasinya).

Teknik MEA adalah strategi untuk mengontrol pencarian dalam memecahkan masalah. Mengingat keadaan saat ini dan negara tujuan, suatu tindakan yang dipilih akan mengurangi perbedaan antara keduanya. Tindakan ini dilakukan pada keadaan saat ini untuk menghasilkan negara baru, dan proses ini secara rekursif diterapkan untuk negara baru dan negara tujuan.

Perhatikan bahwa, agar MEA menjadi efektif, tujuan-sistem mencari harus memiliki sarana bergaul untuk setiap jenis perbedaan terdeteksi tindakan-tindakan yang relevan untuk mengurangi perbedaan itu. Hal ini juga harus memiliki cara untuk mendeteksi kemajuan itu adalah keputusan (perubahan perbedaan antara aktual dan negara yang diinginkan), karena beberapa urutan mencoba tindakan mungkin gagal dan, karenanya, beberapa urutan alternatif mungkin dicoba.

Ketika pengetahuan tersedia mengenai pentingnya perbedaan, perbedaan yang paling penting adalah dipilih pertama untuk lebih meningkatkan kinerja rata-rata MEA atas lain brute force strategi pencarian. Namun, bahkan tanpa pemesanan perbedaan menurut kepentingan, meningkatkan MEA atas heuristik pencari lainnya (lagi dalam kasus rata-rata) dengan fokus pemecahan masalah tentang perbedaan yang sebenarnya antara negara saat ini dan bahwa tujuan.

Teknik MEA sebagai strategi pemecahan masalah pertama kali diperkenalkan pada 1963 oleh Allen Newell dan Herbert Simon di komputer mereka memecahkan masalah Program Umum Problem Solver (GPS). Dalam implementasi itu, korespondensi antara perbedaan dan tindakan , juga disebut operator, disediakan apriori sebagai pengetahuan dalam sistem. (Dalam GPS pengetahuan ini adalah dalam bentuk tabel koneksi.)

Ketika aksi dan efek samping menerapkan operator yang ditembus, pencarian dapat memilih operator yang relevan dengan inspeksi dari operator dan melakukan tanpa tabel koneksi. Kasus yang terakhir, yang contoh kanonik adalah strip , sebuah perencanaan otomatis program komputer, memungkinkan tugas-independen korelasi perbedaan dengan operator yang mengurangi mereka.

Prodigy, masalah pemecah dikembangkan dalam sebuah proyek perencanaan yang lebih besar belajar-dibantu otomatis dimulai di Carnegie Mellon University oleh Jaime Carbonell, Steven Minton dan Craig Knoblock, adalah sistem lain yang digunakan MEA.

Profesor Morten Lind, di Technical University of Denmark telah mengembangkan alat yang disebut aliran MFM pemodelan bertingkat. Ini berarti melakukan penalaran diagnostik-end berbasis kontrol industri dan sistem otomatisasi.

Kendala kepuasan atau Constraint Satisfaction

Dalam kecerdasan buatan dan riset operasi , kepuasan kendala adalah proses menemukan solusi untuk satu set kendala yang memaksakan kondisi bahwa variabel harus memuaskan . Solusi Oleh karena itu vektor dari variabel yang memenuhi semua kendala.

Teknik yang digunakan dalam kepuasan kendala tergantung pada jenis kendala yang dipertimbangkan. Sering digunakan adalah kendala pada domain yang terbatas, ke titik yang kendala masalah kepuasan biasanya diidentifikasi dengan masalah berdasarkan kendala pada domain yang terbatas. Masalah seperti ini biasanya dipecahkan melalui pencarian , khususnya bentuk kemunduran ataupencarian lokal . propagasi Kendala metode lain digunakan pada masalah tersebut, kebanyakan dari mereka tidak lengkap pada umumnya, yaitu, mereka dapat memecahkan masalah atau membuktikannya unsatisfiable, namun tidak selalu. Kendala metode propagasi juga digunakan dalam hubungannya dengan pencarian untuk membuat soal yang diberikan sederhana untuk memecahkan. Jenis lain dianggap kendala berada pada bilangan real atau rasional; pemecahan masalah pada kendala-kendala dilakukan melalui eliminasi variabel atau algoritma simpleks .

Kendala kepuasan berasal dari bidang kecerdasan buatan pada tahun 1970 (lihat misalnya ( Laurière 1978 )). Selama 1980-an dan 1990-an, embedding kendala menjadi bahasa pemrograman yang dikembangkan. Bahasa sering digunakan untuk pemrograman kendala adalah Prolog dan C + + .

Sebagai awalnya didefinisikan dalam kecerdasan buatan, kendala menghitung nilai yang mungkin satu set variabel dapat mengambil. Informal, domain terbatas adalah himpunan berhingga elemen sewenang-wenang. Sebuah kepuasan kendala masalah pada domain seperti berisi satu set variabel yang nilainya hanya dapat diambil dari domain, dan satu set kendala, kendala masing-masing menetapkan nilai diperbolehkan untuk sekelompok variabel. Sebuah solusi untuk masalah ini adalah evaluasi dari variabel-variabel yang memenuhi semua kendala. Dengan kata lain, solusi adalah cara untuk menetapkan nilai untuk setiap variabel sedemikian rupa sehingga semua kendala dipenuhi oleh nilai-nilai ini.

Dalam praktek, kendala yang sering diekspresikan dalam bentuk yang kompak, daripada enumerasi semua nilai dari variabel yang akan memuaskan kendala. Salah satu kendala yang paling sering digunakan adalah salah satu menetapkan bahwa nilai-nilai dari variabel-variabel yang terkena harus semua berbeda.

Masalah yang dapat dinyatakan sebagai masalah kepuasan kendala adalah teka-teki ratu Delapan , yang Sudoku pemecahan masalah, yang masalah satisfiability Boolean , penjadwalan masalah dan berbagai masalah pada grafik seperti grafik mewarnai masalah.

Meskipun biasanya tidak termasuk dalam definisi di atas dari masalah kepuasan kendala, aritmatika persamaan dan ketidaksetaraan terikat nilai-nilai dari variabel yang dikandungnya dan karenanya dapat dianggap sebagai bentuk kendala. Domain mereka adalah himpunan nomor (baik bilangan bulat, rasional, atau nyata), yang tak terbatas: oleh karena itu, hubungan ini kendala mungkin tak terbatas serta, misalnya, X = Y + 1 memiliki jumlah tak terbatas pasang memuaskan nilai-nilai. Aritmatika persamaan dan ketidaksamaan sering tidak dianggap dalam definisi "masalah kepuasan kendala", yang terbatas pada domain yang terbatas. Namun mereka sering digunakan dalam pemrograman kendala .

Masalah kepuasan kendala pada domain yang terbatas biasanya dipecahkan dengan menggunakan bentuk pencarian . Teknik yang paling digunakan adalah varian dari kemunduran , propagasi kendala , dan pencarian lokal . Teknik ini digunakan pada masalah dengan nonlinier kendala.

Variabel eliminasi dan algoritma simpleks digunakan untuk memecahkan linier dan polinomial persamaan dan kesenjangan, dan masalah yang mengandung variabel dengan domain yang tak terbatas.Ini biasanya dipecahkan sebagai optimasi masalah di mana fungsi dioptimalkan adalah jumlah kendala dilanggar.

Memecahkan masalah kendala kepuasan pada domain terbatas adalah NP lengkap masalah. Penelitian telah menunjukkan sejumlah penurut sub kasus, beberapa membatasi hubungan kendala diperbolehkan, beberapa membutuhkan lingkup kendala untuk membentuk pohon, mungkin dalam versi dirumuskan dari masalah. Penelitian juga membentuk hubungan dari masalah kepuasan kendala dengan masalah di daerah lain seperti teori model terbatas .


Kendala pemrograman adalah penggunaan kendala sebagai bahasa pemrograman untuk mengkodekan dan memecahkan masalah. Hal ini sering dilakukan oleh embedding kendala menjadi bahasa pemrograman , yang disebut host language. Pemrograman kendala berasal dari formalisasi kesetaraan istilah dalam Prolog II , yang mengarah ke kerangka umum untuk embedding kendala menjadilogika pemrograman bahasa. Bahasa host yang paling umum adalah Prolog , C + + , dan Java , namun bahasa lainnya telah digunakan juga.

Sebuah program logika kendala adalah logika program yang berisi kendala dalam tubuh klausa. Sebagai contoh, klausa A(X):-X>0,B(X) adalah klausa yang mengandung kendala X>0 dalam tubuh.Kendala juga dapat hadir dalam tujuan. Kendala dalam tujuan dan dalam klausa digunakan untuk membuktikan tujuan diakumulasikan ke dalam satu set disebut toko kendala . Set ini berisi kendala penafsir telah diasumsikan satisfiable dalam rangka untuk melanjutkan dalam evaluasi tersebut. Akibatnya, jika set ini terdeteksi unsatisfiable, yang backtracks penerjemah. Persamaan istilah, seperti yang digunakan dalam pemrograman logika, yang dianggap sebagai bentuk khusus dari kendala yang dapat disederhanakan dengan menggunakan unifikasi . Akibatnya, toko kendala dapat dianggap sebagai perpanjangan dari konsep substitusi yang digunakan dalam pemrograman logika biasa. Jenis yang paling umum digunakan dalam pemrograman kendala kendala kendala logika lebih dari bilangan bulat / bilangan rasional / nyata dan kendala atas domain yang terbatas.

Kendala logika pemrograman konkuren bahasa juga telah dikembangkan. Mereka secara signifikan berbeda dari non-logika pemrograman konkuren kendala dalam bahwa mereka ditujukan untuk pemrograman proses konkuren yang tidak dapat mengakhiri. Kendala aturan penanganan dapat dilihat sebagai bentuk kendala logika pemrograman konkuren, tetapi juga kadang-kadang digunakan dalam kendala non-bersamaan logika bahasa pemrograman. Mereka memungkinkan untuk menulis ulang kendala atau untuk menyimpulkan yang baru berdasarkan kebenaran kondisi.

Kendala kepuasan toolkit perangkat lunak perpustakaan untuk bahasa pemrograman imperatif yang digunakan untuk mengkodekan dan memecahkan masalah kepuasan kendala.

• Pemecah kendala Kasuari adalah sebuah open source proyek untuk kepuasan kendala (dapat diakses dari C, Java, Python dan bahasa lainnya).
• Komet , sebuah bahasa pemrograman komersial dan toolkit
• Gecode , sebuah toolkit open source portabel yang ditulis dalam C + + dikembangkan sebagai pelaksanaan produksi berkualitas dan sangat efisien dari latar belakang teoritis lengkap.
• JaCoP (pemecah) open source Java kendala pemecah
• Koalog solver berbasis Java kendala komersial.
• logilab-kendala kendala open source pemecah ditulis dengan Python murni dengan algoritma propagasi kendala.
• Minion kendala open source solver ditulis dalam C + +, dengan bahasa kecil untuk tujuan menetapkan model / masalah.
• ZDC adalah sebuah program open source yang dikembangkan dalam Proyek Computer-Aided Kepuasan Kendala untuk pemodelan dan memecahkan masalah kendala kepuasan.

Kendala toolkit adalah cara untuk embedding kendala menjadi bahasa pemrograman imperatif . Namun, mereka hanya digunakan sebagai perpustakaan eksternal untuk encoding dan memecahkan masalah. Suatu pendekatan di mana kendala yang diintegrasikan ke dalam bahasa pemrograman imperatif diambil dalam bahasa pemrograman Kaleidoscope .

Kendala juga telah tertanam ke dalam bahasa pemrograman fungsional .

Pengurangan (kompleksitas) atau Problem Reduction Dalam Teknik Pencarian Heuristik

Dalam teori komputabilitas dan teori kompleksitas komputasi , pengurangan adalah transformasi dari satu masalah ke masalah lain.Tergantung pada transformasi yang digunakan ini dapat digunakan untuk mendefinisikan kelas kompleksitas pada serangkaian masalah.

Secara intuitif, masalah A ke B direduksi masalah jika solusi ke B ada dan memberikan solusi ke A setiap kali A memiliki solusi. Jadi, pemecahan A tidak bisa lebih sulit daripada memecahkan B. Kita menulis A ≤ _m B, biasanya dengan subskrip pada ≤ untuk menunjukkan jenis pengurangan yang digunakan (m: pengurangan pemetaan, p: reduksi polinomial).

Sering kali kita menemukan diri kita berusaha untuk memecahkan masalah yang mirip dengan masalah kita sudah dipecahkan. Dalam kasus ini, sering merupakan cara cepat untuk memecahkan masalah baru untuk mengubah setiap contoh dari masalah baru ke contoh dari masalah lama, memecahkan ini menggunakan solusi yang ada, dan kemudian menggunakan ini untuk mendapatkan solusi akhir kami. Ini mungkin adalah penggunaan paling jelas dari pengurangan.

Penggunaan lain, lebih halus adalah ini: misalkan kita punya masalah yang kami telah terbukti sulit untuk memecahkan, dan kami memiliki masalah baru yang sama. Kita mungkin menduga bahwa hal ini juga, sulit untuk memecahkan. Kami berpendapat dengan kontradiksi: rasa masalah baru mudah untuk memecahkan. Kemudian, jika kita dapat menunjukkan bahwa setiap instance dari masalah lama dapat diselesaikan dengan mudah dengan mengubahnya menjadi contoh dari masalah baru dan memecahkan mereka, kami memiliki kontradiksi. Ini menetapkan bahwa masalah baru juga keras.

Sebuah contoh yang sangat sederhana dari pengurangan adalah dari perkalian untuk mengkuadratkan. Misalkan semua kita tahu bagaimana melakukannya adalah untuk menambah, mengurangi, mengambil kotak, dan dibagi dengan dua. Kita dapat menggunakan pengetahuan ini dikombinasikan dengan rumus berikut, untuk memperoleh produk dari dua angka:

Kami juga memiliki penurunan arah lain, jelas, jika kita dapat mengalikan dua angka, kita bisa persegi nomor. Hal ini tampaknya menyiratkan bahwa dua masalah sama-sama keras. Semacam ini pengurangan sesuai dengan pengurangan Turing .

Namun, pengurangan menjadi jauh lebih sulit jika kita menambahkan pembatasan bahwa kita hanya dapat menggunakan fungsi mengkuadratkan satu kali, dan hanya di akhir. Dalam hal ini, bahkan jika kami diizinkan untuk menggunakan semua operasi aritmatika dasar, termasuk perkalian, pengurangan tidak ada pada umumnya, karena kita mungkin harus menghitung suatu bilangan irasionalseperti  dari nomor rasional. Pergi ke arah lain, bagaimanapun, kita pasti bisa persegi nomor hanya dengan satu perkalian, hanya di akhir. Menggunakan bentuk terbatas pengurangan, kami telah menunjukkan hasil mengejutkan bahwa perkalian lebih sulit secara umum dari mengkuadratkan. Hal ini sesuai dengan banyak-satu pengurangan .

Diberikan dua himpunan bagian A dan B dari N dan satu set fungsi F dari N ke N yang tertutup di bawah komposisi , A disebut direduksi ke B di bawah F jika

Kami menulis

Misalkan S adalah subset dari P (N) dan pengurangan ≤, maka S disebut tertutup di bawah ≤ jika

Subset A N disebut sulit bagi S jika

Subset A N disebut lengkap untuk S jika A sulit untuk S dan A adalah S.

Reduksi adalah preordering , yang merupakan refleksif dan transitif relasi , pada P (N) × P (N), di mana P (N) adalah kekuatan diatur dari alam nomor .

Seperti dijelaskan dalam contoh di atas, ada dua jenis utama yang digunakan dalam pengurangan kompleksitas komputasi, banyak pengurangan-satu dan pengurangan Turing . Banyak-salah satucontoh peta pengurangan satu masalah terhadap kasus lain; turing pengurangan menghitung solusi untuk satu masalah, dengan asumsi masalah lainnya adalah mudah untuk dipecahkan. Penurunan banyak-satu adalah lebih lemah dari pengurangan Turing. Pengurangan lemah lebih efektif dalam memisahkan masalah, tetapi mereka memiliki lebih sedikit daya, membuat pengurangan sulit untuk desain.

Masalahnya adalah lengkap untuk kelas kompleksitas jika setiap masalah di kelas mengurangi masalah itu, dan juga di kelas itu sendiri. Dalam pengertian ini mewakili masalah kelas, karena setiap solusi untuk itu bisa, dalam kombinasi dengan pengurangan, digunakan untuk memecahkan setiap masalah di kelas.

Namun, untuk menjadi berguna, pengurangan harus mudah. Sebagai contoh, itu sangat mungkin untuk mengurangi sulit-untuk-mengatasi NP-lengkap masalah seperti masalah satisfiability booleanuntuk masalah sepele, seperti menentukan jika nomor sama dengan nol, dengan memiliki mesin reduksi memecahkan masalah dalam waktu eksponensial dan output nol hanya jika ada solusi.Namun, hal ini tidak mencapai banyak, karena meskipun kita dapat memecahkan masalah baru, melakukan pengurangan hanya sekeras memecahkan masalah lama. Demikian pula, penurunan komputasi fungsi noncomputable dapat mengurangi suatu masalah diputuskan untuk satu decidable. Seperti Michael Sipser menunjukkan dalam Pengantar Teori Perhitungan: "Penurunan harus mudah, relatif terhadap kompleksitas masalah-masalah khas di kelas [...] Jika pengurangan itu sendiri sulit untuk menghitung, solusi mudah untuk menyelesaikan masalah tidak akan selalu menghasilkan sebuah solusi mudah untuk mengurangi masalah untuk itu. "

Oleh karena itu, gagasan yang sesuai pengurangan tergantung pada kelas kompleksitas sedang dipelajari. Ketika mempelajari kompleksitas kelas NP dan kelas keras seperti hirarki polinomial ,polinomial-waktu pengurangan digunakan. Ketika mempelajari kelas-kelas dalam P seperti NC dan NL , log-ruang pengurangan digunakan. Penurunan juga digunakan dalam teori komputabilitas untuk menunjukkan apakah masalah atau tidak dipecahkan oleh mesin sama sekali, dalam hal ini, pengurangan dibatasi hanya untuk fungsi dihitung .

Dalam hal optimasi (memaksimalkan atau minimisasi) masalah, kita sering berpikir dalam hal pendekatan-melestarikan pengurangan. Misalkan kita memiliki masalah optimasi dua seperti bahwa kasus-kasus satu masalah dapat dipetakan ke kasus yang lain, dengan cara yang hampir-solusi yang optimal terhadap kasus masalah terakhir dapat diubah kembali untuk menghasilkan solusi optimal untuk hampir-mantan. Dengan cara ini, jika kita memiliki algoritma optimasi (atau algoritma aproksimasi ) yang menemukan dekat-optimal (atau optimal) solusi untuk contoh dari B masalah, dan pengurangan pendekatan-melestarikan efisien dari A ke B masalah masalah, dengan komposisi kita memperoleh optimasi algoritma yang menghasilkan solusi yang optimal dekat terhadap kasus masalah A. Pendekatan-melestarikan pengurangan sering digunakan untuk membuktikan kekerasan pendekatan hasil: jika beberapa masalah optimasi adalah sulit untuk perkiraan (di bawah beberapa asumsi kompleksitas) dalam faktor lebih baik dari α untuk beberapa α, dan ada β-pendekatan-melestarikan pengurangan dari masalah A B masalah untuk, kita dapat menyimpulkan bahwa B masalah adalah sulit untuk perkiraan dalam faktor α / β.

Contoh

• Untuk menunjukkan bahwa masalah keputusan P diputuskan kita harus menemukan pengurangan dari masalah keputusan yang sudah diketahui diputuskan untuk fungsi pengurangan P. Itu harus menjadi fungsi dihitung . Secara khusus, kita sering menunjukkan bahwa P Masalahnya diputuskan dengan menunjukkan bahwa masalah menghentikan mengurangi ke P.
• Kelas kompleksitas P , NP dan PSPACE yang tertutup di bawah polinomial-waktu pengurangan .
• Kelas kompleksitas L , NL , P , NP dan PSPACE yang tertutup di bawah log-ruang pengurangan .

Contoh rinci

Contoh berikut menunjukkan bagaimana menggunakan pengurangan dari masalah terputus-putus untuk membuktikan bahwa bahasa adalah diputuskan. Misalkan H (M, w) adalah masalah menentukan apakah yang diberikan mesin Turing M menghentikan (dengan menerima atau menolak) pada string input w. Bahasa ini dikenal diputuskan. Misalkan E (M) adalah masalah menentukan apakah bahasa mesin Turing diberikan M menerima kosong (dengan kata lain, apakah menerima setiap string M sama sekali). Kami menunjukkan bahwa E diputuskan oleh penurunan dari H.

Untuk mendapatkan kontradiksi, misalkan R adalah penentu untuk E. Kami akan menggunakan ini untuk menghasilkan penentu S untuk H (yang kita tahu tidak ada). Mengingat masukan M dan w(mesin Turing dan beberapa string masukan), mendefinisikan S (M, w) dengan perilaku berikut: S N Turing menciptakan mesin yang menerima hanya jika string masukan ke N adalah w dan Mperhentian pada input w , dan tidak menghentikan sebaliknya. Penentuan S sekarang dapat mengevaluasi R (N) untuk memeriksa apakah bahasa yang diterima oleh N kosong. Jika R menerima N,maka bahasa yang diterima oleh N kosong, sehingga dalam M tertentu tidak menghentikan pada input w, sehingga S dapat menolak. Jika R menolak N, maka bahasa yang diterima oleh N tidak kosong, sehingga M tidak menghentikan pada input w, sehingga S dapat menerima. Jadi, jika kita memiliki R penentu untuk E, kita akan mampu menghasilkan penentu S untuk masalah Hmenghentikan (M, w) untuk setiap M mesin dan masukan w. Karena kita tahu bahwa seperti S tidak dapat ada, maka bahasa bahwa E juga diputuskan.