decidable - Given the encoding of a specific Turing machine, can it be decided if it will halt on a specific input? -


say have universal turing machine encoding of specific turing machine t. have encoding of specific input s. question of whether t halts on s decidable? can simulating running t on s used reach answer?

this problem decidable in instances. specific, fixed tm either halts or doesn't on specific, fixed input, assuming moment excluded middle not want challenge here. specific instance of problem fixing tm , input, tm should either halt-accept inputs (not specific, fixed input parameterizing problem, typical input tm solve our parameterized problem) if specific instance if problem has tm halting on supplied input, or should halt-reject if specific instance has tm fails halt.

the difficulty specific instance of problem, know specific tm either halts or doesn't given specific input, don't have computationally effective way know case. 1 or other (again, whether accept excluded middle larger discussion) , therefore specific instance of problem decidable - regular, - doesn't much, except understand computability little better.

note there lots of instances of problem know of 2 cases holds; instance, not hard produce tms halt, or fail halt, on or inputs. instances of problem not decidable , regular, know decidable/regular languages are.


Comments

Post a Comment

Popular posts from this blog

php - Vagrant up error - Uncaught Reflection Exception: Class DOMDocument does not exist -

i've set bento/ubuntu-16.04 vagrant box using php 5.6, , getting following error quite few times when try , run shell script: "uncaught reflection exception: class domdocument not exist". i've tried adding following top of script (not together), each no success: "sudo apt-get install php5.6-xml", "sudo apt-get install php5-xml", "sudo apt-get install php-dom" i've tried resetting server "sudo service apache2 restart". does have suggestions?
Read more

vue.js - Create hooks for automated testing -

Image
qa guys complained can't automate frontend testing. because our html looks same outside. lazy hack did this <template> <div :role="$options.name"> ... </div> </template> <script> export default { name: 'vmcomponentname' } </script> which takes name script , applies html. in browser get: <div role="vmcomponentname"> ... </div> line :role="$options.name" goes in every component. is there dry er solutions? please share. additional details i'll explain in details looking for. imagine have vmusercreate form creates user. test case can create user . to automatically test without role, have use following selector: .wrapper > .wrapper > .wrapper > .submit-button the test extremely brittle (will break lot). if use roles can use [role="vmusercreateform"] .submit-button selector. many folds less brittle. so basically, i'm ...
Read more

Add new key value to json node in java -

i have json file : { "id":1, "name":"abc", "addressdetails": { "city":"newyork" } } i wanted add 1 more key-value ("pincode" : "414141") node 'addressdetails'. i tried using : objectmapper mapper = new objectmapper(); jsonnode root = mapper.readtree(new file("d://test.json")); objectnode node = mapper.createobjectnode(); node.with("addressdetails").put("pincode", "414141"); but it's not getting added, there way can ? you can try you should modify file path objectmapper mapper = new objectmapper(); objectnode nodes = mapper.readvalue(new file("d:\\test.txt"), objectnode.class); nodes.with("addressdetails").put("pincode", "414141"); mapper.writer().writevalue(new file("d:\\test.txt"), nodes);
Read more